gen.c

GENETIC ALGORITHM FOR NEURAL NETWORKS ON TRANSPUTERS (Source code and Reference)

/* Implementation of general genetic algorithms */

#include "defs.h"
#include "gen.h"
#include "ind.h"

/* Parameter Handling */

#define DEFMUTATE	60
#define DEFNMUTATE	AUTO
#define DEFCOPY		0
#define DEFDECIMATION	0
#define DEFHASH		AUTO

char *GenOptStr() {return "m:n:c:u:d:h:\0";}

char *GenUsage() {return	
  "Genetic Parameters:\n"
  "-m <percentage of mutations>:     60\n"
  "-n <n for 1..n point mutations>:  auto\n"
  "-c <percentage of copies>:        0\n"
  "-u <perc. of uniform selections>: 0\n"
  "-d <initial decimation factor>:   0\n"
  "-h <size of hashtable (0=off)>:   auto\n\0";}

/* set default values */

int Pcopy	=DEFCOPY;	/* % of indiv. to copy per gen. */
int Pmutate	=DEFMUTATE;	/* % of indiv. to mutate per gen.*/
int Puniform	=0;		/* % of indiv. selected by uniform distrib. */
int Nmutate	=DEFNMUTATE;	/* 1..Nmutate point mutations */
int Decimation	=DEFDECIMATION;	/* initial decimation factor */
int HashLen	=DEFHASH;	/* lenth of hashkey 9n bits */
int HashSize	=0;		/* size of hashtable */
int Nunique	=UNDEF;		/* no. of different indiv. */
int Nredundant	=UNDEF;		/* no. of redundant indiv. */
int Nmismatch	=UNDEF;		/* no. of mismatches */

ind *OldPop;	/* old population */
int HashMask;	/* HashSize-1 */
int *HashTab;
int Nuniform;

int handleGenOpt(char opt,char* arg)
{
  switch(opt)
  {
    case 'm': return (Pmutate	=getint(arg,0,100))<0;
    case 'n': return (Nmutate	=getint(arg,1,1000))<0;
    case 'c': return (Pcopy	=getint(arg,0,100))<0;
    case 'u': return (Puniform	=getint(arg,0,100))<0;
    case 'd': return (Decimation=getint(arg,0,100))<0;
    case 'h': return (HashLen	=getint(arg,0,16))<0;
    default: return 1;
  };
}

int initGen(int popsize,int popmem)
{
  int i,j,k,n,h,t;
  word *p;
  ind* pop;
  char s[128];

  GenCalcs=0;
  Pcrossover=100-Pmutate-Pcopy;
  if(Pcrossover<0) return 1;
  Nuniform=Puniform*(MAXRANDOM/100);
  
  if(HashLen==AUTO) HashLen=Pmutate>50 ? 0 : duallog(popsize)+1;
  if(HashLen)
  {
    if(popsize>(1<<HashLen)) return 1;
    HashSize=1 << HashLen;
    HashMask=HashSize-1;
    HashTab=(int*)malloc(HashSize*WORDLEN);
  };
  if(!(Pop=(ind*)malloc(popmem*INDLEN))) return 1;
  if(!(p=(word*)malloc(popmem*CrWords*WORDLEN))) return 1;
  for(i=0;i<popmem;i++) Pop[i]=p+i*CrWords;
  if(!(OldPop=(ind*)malloc(popmem*INDLEN))) return 1;
  if(!(p=(word*)malloc(popmem*CrWords*WORDLEN))) return 1;
  for(i=0;i<popmem;i++) OldPop[i]=p+i*CrWords;
  if(!(Err=(errtyp*)malloc(popmem*ERRLEN))) return 1;
  if(Decimation<=1) Decimation=0;
  if(Decimation)
  {
    h=HashLen; HashLen=0; 
    DecErrAvg=0; DecErrMin=MAXERROR;
    k=(popsize-1)/Decimation+1; n=0;
    while(n<popsize)
    {
      randomPop(popsize);
      calcerrors(popsize);
      if(DecErrMin>ErrMin) DecErrMin=ErrMin;
      DecErrAvg+=ErrAvg;
      for(i=0;i<k && n<popsize;i++) 
      {
        t=0;
        for(j=1;j<popsize;j++)
          if(Err[j]<Err[t]) t=j;
        copy(Pop[t],OldPop[n++]);
        Err[t]=MAXERROR;
      };
    };
    pop=Pop; Pop=OldPop; OldPop=pop;
    DecErrAvg/=Decimation;
    HashLen=h;
  } else {
    randomPop(popsize);
  };
  if(Nmutate==AUTO) Nmutate=CrBits/50+1;

  s[0]=0;
  if(HashLen) sprintf(s,", HashSize = %d",HashSize); 
  sprintf(GenParamStr,
    "Genetic:    Pcopy = %d %%, Pmutate(1..%d pt.) = %d %%, "
    "Pcrossover = %d %%%s\n"
    "            Selection %d %% linear, %d %% uniform\n",
    Pcopy,Nmutate,Pmutate,Pcrossover,s,100-Puniform,Puniform);
  if(Decimation)
  {
    sprintf(s,"Decimation: Factor = %d, PopSize = %d, "
      "MinErr=%6.2f, AvgErr=%6.2f\n",
      Decimation,popmem*Decimation,DecErrMin,DecErrAvg);
    strcat(GenParamStr,s);
  };
  return 0;
}

void randomPop(int popsize)
{
  int i,j;
  word m;
  byte *p;

  p=(byte*)Pop[0];
  for(i=0;i<popsize*CrWords*WORDLEN;i++) p[i]=getrand() & 0xff;
  j=CrBits % (8*WORDLEN);
  if(CrBits%(WORDLEN*8))
  {
    m=(1<<j)-1;
    for(i=0;i<popsize;i++)
      Pop[i][CrWords-1] &= m;
  };
}

void clearerrtab()
{
  int i;

  for(i=0;i<HashSize;i++) HashTab[i]=NOENTRY;
  Nunique=Nredundant=Nmismatch=0;
}

int hashfct(ind x)
{
  int i;
  word w=0;

  for(i=0;i<CrWords;i++) w+=x[i];
  w+=w>>HashLen;
  w+=w>>HashLen;
  w+=w>>HashLen;
  return (int)(w & HashMask);
}
  
errtyp geterr(int n) 
{
  int i,h,k;
  errtyp e;

  h=hashfct(Pop[n]);
mismatch:
  k=HashTab[h];
  if(k==NOENTRY)
  {
    e=Err[n]=calcerr(Pop[n]);
    HashTab[h]=n;
    Nunique++;
    return e;
  } else {
    for(i=0;i<CrWords;i++) 
      if(Pop[n][i]!=Pop[k][i])
      { 
	h=(h+1)&HashMask;
	Nmismatch++;
	goto mismatch;
      };
    e=Err[n]=Err[k];
    Nredundant++;
    return e;
  };
}    
  
void mutate(ind x0,ind x1)
{
  int i,k,m;
  for(i=0;i<CrWords;i++) x1[i]=x0[i]; 
  m=getrand()%Nmutate; 
  for(i=0;i<=m;i++)
  {
    k=getrand()%CrBits;
    x1[wordoffs(k)]^=1<<bitoffs(k);
  };
}

void crossover(ind x0,ind y0,ind x1,ind y1)
{
  int n,i,k;
  word m,xx0,xx1,yy0,yy1;

  n=getrand()%CrBits; n=67;
  k=wordoffs(n);
  for(i=0;i<k;i++)
  {
    x1[i]=y0[i]; y1[i]=x0[i];
  };
  m=(1<<bitoffs(n))-1;

  xx0=m & (x0[k]); xx1=(~m) & (x0[k]);
  yy0=m & (y0[k]); yy1=(~m) & (y0[k]);

  x1[k]=yy0|xx1;
  y1[k]=xx0|yy1;

  for(i=k+1;i<CrWords;i++)
  {
    x1[i]=x0[i]; y1[i]=y0[i];
  };

}

void copy(ind x0,ind x1)
{
  int i;
  
  for(i=0;i<CrWords;i++) x1[i]=x0[i];
}

void calcerrors(int popsize)
{
  int i;
  errtyp e,sum,min;

  sum=0; min=MAXERROR;
  if(HashLen)
  {
    clearerrtab();
    for(i=0;i<popsize;i++) 
    {
      e=geterr(i);
      sum+=e; 
      if(e<min) { min=e; TopInd=i; };
    };
  } else {
    for(i=0;i<popsize;i++) 
    {
      e=Err[i]=calcerr(Pop[i]);
      sum+=e;
      if(e<min) { min=e; TopInd=i; };
    };
  };
  ErrMin=(float)min;
  ErrAvg=((float)sum)/((float)popsize);
}


      
ind selectind(int popsize)
{
  int p,q;

  if(getrand()>=Nuniform)
  {
    p=getrand()%popsize;
    q=getrand()%popsize;
    return (Err[p]<=Err[q]) ? OldPop[p] : OldPop[q];
  } else {
    return OldPop[getrand()%popsize];
  };
}

void selection(int popsize)
{
  int i,j;
  ind *p;

  int ncopy,nmutate,ncrossover;

  ncopy=(popsize*Pcopy)/100;
  nmutate=(popsize*Pmutate)/100;
  ncrossover=popsize-ncopy-nmutate;
  if(ncopy==0)
  { 
    ncopy=1; 
    if(nmutate) nmutate--; else ncrossover--; 
  }
  if(ncrossover&1) { ncrossover--; nmutate++; };

  p=Pop; Pop=OldPop; OldPop=p; i=0;
  copy(OldPop[TopInd],Pop[i++]);
  for(j=1;j<ncopy;j++)
    copy(selectind(popsize),Pop[i++]);
  for(j=0;j<ncrossover;j+=2)
   crossover(selectind(popsize),selectind(popsize),Pop[i++],Pop[i++]);
  while(i<popsize)
    mutate(selectind(popsize),Pop[i++]);
}