Basic genetic algorithm


// generic GA
// single linear binary chromosome
// interpretation of it is up to the program - no interpretation is made here




// I thought of randomising all objects in their constructors,
// but this is probably unnecessary half the time
// (and could even perhaps lead to infinite loops).
// Instead, I have a hierarchy of randomising,
// so calling the randomise() function on a Population
// randomises all the individuals within it, etc.

const int l = 30;		// length of chromosome
const int n = 50;		// size of population (should be even)
const double pc = 0.8;		// probability of crossover
const double pm = 0.005;	// probability of mutation

A Chromosome:


typedef Boolean Allele;		// alphabet is 0,1 (k=2)



// my own array, with 1..n indexing:

class AlleleArray
{
public:
 Allele secret[l];
 Allele& operator[] ( int i ) { return secret[i-1]; }
  // return reference because x[] might appear on lhs of equation
};



class Chromosome : public AlleleArray
{
public: 
 Chromosome& operator= ( Chromosome& c )
 { 
  for ( int i=1; i<=l; i++ )
    { (*this)[i] = c[i]; }
  return *this;		
 }

 randomise()
 { 
  for ( int i=1; i<=l; i++ )
    { (*this)[i] = r.flip(0.5); }	// a fair toss
 } 

 friend ostream& operator<< ( ostream& stream, Chromosome& c)
 {
  for ( int i=1; i<=l; i++ ) 
  { 
   Boolean b = c[i];
   stream << b;
  } 
  return stream;
 }
};

The main, problem-specific, forward declaration:


double positiveFitness ( Chromosome );	

	// how fit is this Chromosome?
	// the user application must return a positive fitness

An Individual:


class Individual
{
public:
 Chromosome 	a;		// a[1] .. a[l]
 int 		parent1;
 int		parent2;
 int 		crossoversite;
 double 	fitness;

 updateFitness()			// new chromosome..
 {
  fitness = positiveFitness(a);		// ask the application to rate it
  if ( fitness < 0 )
  {
	// return error 
  }
 }

 Individual& operator= ( const Individual& x )
 {
  a = x.a;
  parent1 = x.parent1;
  parent2 = x.parent2;
  crossoversite = x.crossoversite;
  updateFitness();
  return *this;
 }

 makeMe ( Chromosome c, int p1, int p2, int x )
 {
  a = c;
  parent1 = p1;
  parent2 = p2;
  crossoversite = x;
  updateFitness();
 }

 randomise()
 { 
  a.randomise();
  parent1 = 0;
  parent2 = 0;
  crossoversite = 0;
  updateFitness();
 }

 friend ostream& operator<< ( ostream& stream, Individual& x)
 {
  sprintf ( buf, "(%3d,%3d)", x.parent1, x.parent2 );
  stream << buf;
  if ( x.crossoversite == l )
    sprintf ( buf, ",  -   " );		// there was no crossover
  else
    sprintf ( buf, ", %3d  ", x.crossoversite );
  stream << buf;
  stream << x.a;
  sprintf ( buf, " %8.3f", x.fitness );
  stream << buf;
  return stream;
 }
};

A Population:


class IndividualArray
{
public:
  Individual secret[n];
  Individual& operator[] ( int i ) { return secret[i-1]; }
};



class Population : public IndividualArray
{
public:
 Population& operator= ( Population& p )
 {
  for ( int i=1; i<=n; i++ )
   { (*this)[i] = p[i]; } 
  return *this;
 }

 randomise()
 {
  for ( int i=1; i<=n; i++ )
   { (*this)[i].randomise(); } 
 }

 Population() 
 {
  if ( (n % 2) != 0 )
  {
	// return error 
  }
 }
};







class World
{
public:
 Population 	A;			// A[1] .. A[n]

// these statistics calculated by runStatistics:
 Individual	best;
 double 	worstFitness, averageFitness, sumFitness;


  		randomise() { A.randomise(); runStatistics(); }

 int 		select();		
 		crossover ( int, int );	// deposits output in:
 Individual 	child1,child2;	
 Allele 	mutate ( Allele );
};

Select a random individual for reproduction. Fittest most probable to be selected:

This uses simple summation of fitness (not Boltzmann), plus spin the weighted wheel.


int World :: select()
// actually called multiple times
// each time just selects one A[i] for reproduction
{
 double point = r.prob() * sumFitness; 
	// random point between 0 and sigma fitnesses ('spin the wheel')
	// find the individual intersecting this point
 double partial = 0.0;
 int i = 0;			
 while ( (partial<=point) && (i < n) )
 {
  i++;
  partial = partial + A[i].fitness;
 }
 // the loop has stopped because either partial has just crossed the line, or i=n.
 // either way:
 return(i);
}

Mix up the 2 parents' genes:


World :: crossover ( int parent1, int parent2 )
// writes output to child1,child2
{
// first build the chromosomes..
 Chromosome p1 = A[parent1].a;
 Chromosome p2 = A[parent2].a;
 Chromosome c1;
 Chromosome c2;
 int site,i;
 
 if ( r.flip(pc) ) 		// flip coin weighted with pc
   site = r.restricted(1,l-1);	// crossover - random cut, from after 1 to after l-1
 else 
   site = l;			// no crossover - 'cut' after l

// the cut comes after site,
// so elements 1 to site go to one side, site+1 to l into other:
 for ( i=1; i<=site; i++ ) 
 {
  c1[i] = mutate(p1[i]);
  c2[i] = mutate(p2[i]);
 }
 for ( i=site+1; i<=l; i++ ) 
 {
  c1[i] = mutate(p2[i]);
  c2[i] = mutate(p1[i]);
 }


// then build the individuals..
 child1.makeMe ( c1, parent1, parent2, site );
 child2.makeMe ( c2, parent1, parent2, site );
}

Certain probability of mutation:


Allele World :: mutate ( Allele a )
// mutate allele a with probability pm
{
 if ( r.flip(pm) )
  return (!a);
 else
  return (a);
}

Build a new population from the current one:


World :: next()
// replace population A
{
 runStatistics(); 	// just for safety, make sure we are up to date with A
 Population temp;
 for ( int i=1; i<=n-1; i=i+2 )		// build in pairs - temp(1,2), temp(3,4), .. temp(n-1,n)
 {
  crossover ( select(), select() );	// select two mates and build 2 new children
    temp[i] = child1;
  temp[i+1] = child2;
 }
// now we are finished with the old A. replace it:
 A = temp;
}


World :: runStatistics()
// update various statistics about myself
{
 best 		= A[1];
 worstFitness 	= A[1].fitness;
 sumFitness 	= A[1].fitness;
 for ( int i=2; i<=n; i++ )
 {
  double f = A[i].fitness;
  sumFitness = sumFitness + f;
  if ( f < worstFitness ) worstFitness = f;
  if ( f > best.fitness ) best = A[i];
 }
 // these all now fully calculated.
 // all that remains is:
 averageFitness = sumFitness / n;
}




// the GA library's statistical reports are only concerned with the GA internals.
// they only deal in concepts of 'string' and 'fitness'
// they have no idea why that string has that fitness,
// or what it means:

World :: detailedReport ( int t, ostream& stream )
{
 runStatistics();
 stream << "\n\n\n";
 stream << "t=" << t << "\n";
 stream << "  #  parents,xsite                          string  fitness \n";
 stream << "------------------------------------------------------------\n";
 for ( int i=1; i<=n; i++ )
 {
  sprintf ( buf, "%3d ", i );
  stream << buf << A[i];
  if ( A[i].fitness > averageFitness )
    stream << " +";
  stream << "\n";
 }
 stream << "------------------------------------------------------------\n";
}


World :: summaryReport ( int t, ostream& stream )
// (the outside world tells me what time (i.e. what generation) it is)
{
 runStatistics();
 sprintf ( buf, "t=%-3d worst=%0.3f average=%0.3f best=( ",
	    t, worstFitness, averageFitness );
 stream << buf;
 stream << best.a;
 sprintf ( buf, " , %0.3f ) \n",
	    best.fitness );
 stream << buf;
}