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