GENETIC ALGORITHM

Sample GA implementation - Maximise function f(x) over some interval

// forward declarations:
double decode ( Chromosome );
double normalise ( double );
// global variables:
World           w;              // the world (changes each generation)
Individual      bestever;       // the best solution ever seen over all the generations



//--- maximise this function: ------------------------------
double f ( double x )
{
 return ( sin(x)+sin(2*x)+sin(5*x)+cos(x) );
}
//--- over this interval: ----------------------------------
const double low  = 1.0;
const double high = 10.0;


// to graph the function,
// what y axis should the plot use? (rough guide)
const double lowy = -2.5;
const double highy = 4.0;
// add this to all y to make them positive:
const double cmin = 2.5;        

Interpret the Chromosome as a number x. Return f(x) as the fitness (except make sure it is positive):

double positiveFitness ( Chromosome a )
// what the chromosome means is entirely up to the application.
// here I interpret it as encoding a double in the range 0 to (2^l - 1),
// which I can normalise so that it encodes a double in the range I'm interested in.
// (what this means is that l is actually a measure of the number of decimal places)
{
 double x = decode(a);  
 double y = f(x);
// must return a positive fitness value.
// we can scale it/normalise it any way we like it
// only the GA library sees this
// (all the statistics routines in the application deal with f(x), not 'fitness' )
 return ( y + cmin );
}


double decode ( Chromosome a )
// a is the binary expression of a double
{
 double no = 0.0;
 double power = 1;              // power goes 2^0, 2^1, 2^2 ..
 for ( int i=l; i>=1; i-- )     // work right to left
 {
  if ( a[i] ) 
    no = no + power;
  power = power * 2;
 }
 // we now have a number no, in the range 0 to (2^l - 1)
 // can interpret this as encoding a number in the range we're interested in:
 return ( normalise(no) );
}


// calculate these only once (more efficient):
const double max = (pow(2,l)-1);
const double interval = (high-low);
double normalise ( double no )
{                                       // no comes in as [0..max]..
 double p = no / max;                   // normalise it to [0..1]..
 double x = low + (p*interval);         // then normalise that to [low..high]
 return x;
}

Note there is no "encode" function - numbers are generated automatically at the string level, we never manually put them there. "decode" is only so that we can see what they've done.

User application reports:

// the application's statistical reports deal in concepts of x and f(x).
// they understand what the 'string' and 'fitness' actually mean.

detailedReport ( int t, ostream& stream )
{
 w.runStatistics();
 stream << "\n\n\n";
 stream << "t=" << t << "\n";
 stream << "  #                         string      x   f(x) \n";
 stream << "-------------------------------------------------\n";
 for ( int i=1; i<=n; i++ )
 {
  sprintf ( buf, "%3d ", i );
  Chromosome c = w.A[i].a;
  stream << buf << c;

  double x = decode(c); 
  sprintf ( buf, "  %0.3f  %0.3f", 
            x, f(x) );
  stream << buf;
  if ( w.A[i].fitness > w.averageFitness ) 
    stream << " +";
  stream << "\n";
 }
 stream << "-------------------------------------------------\n";
}




besteverPrint ( int t, ostream& stream )
{
 sprintf ( buf, "%10d  ", t );
 stream << buf;
 stream << bestever.a;

 double x = decode(bestever.a); 
 sprintf ( buf, "  %0.3f  %0.3f \n", 
           x, f(x) );
 stream << buf;
}

besteverHeader ( ostream& stream )
{
// a report that only the application can do,
// interpreting w in the light of what the strings actually mean ( x and f(x) )
 stream << "--- progressive list of best solutions found ----------- \n";
 stream << "generation                          string      x   f(x) \n";
 w.runStatistics();
 bestever = w.best;
 besteverPrint ( 1, stream );
}
Boolean newRecord()
{
  w.runStatistics();
  return ( w.best.fitness > bestever.fitness );
}

The main function:

main ( int argc, char **argv )
{
   int ARG = atoi ( argv[1] ); 

   w.randomise();
   besteverHeader ( cout );


   for ( int t=1; t<=ARG; t++ )         
   {
        if ( newRecord() )
        {
         bestever = w.best;
         besteverPrint ( t, cout );
        } 
//      detailedReport ( t, debugfile );
//      w.detailedReport ( t, debugfile );
//      w.summaryReport ( t, debugfile );

        w.next();
   }
}