Dr. Mark Humphrys

School of Computing. Dublin City University.

Home      Blog      Teaching      Research      Contact

Search:

CA216      CA249      CA318

CA400      CA651      CA668


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



Feeds      w2mind.org

On Internet since 1987.