Basic genetic algorithm

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:

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;
}