GA principles, conditions and parameters explained

Basically I divided the topic as a whole into 4 parts: 

• Principles , conditions and parameters
• Test results
• Presentation of an implementation of the virtual class in C++
• Presentations of the class definition

GA results with gnuplot

Tests are done on a MAC book pro (2.3G dual core) and iMac (3G dual core) 


With small population sizes and target reached at 98% execution time < 5 seconds.


Notice here that only with small populations we have several fallbacks on strength and a very unstable curve due to greater impact of stochastic mutations and crossovers on the intermediate average strength:





With medium population sizes and target reached at 98%:(execution time < 1 minute)


Here you can see that evolution stands still for a number of generations and only by a random mutation in time evolution starts climbing again:

With large population sizes and target reached at 98%:(execution time < 2 hour)

Remarkable here is that in the first 100 generations evolution is going to 90% of the target with no fallback at all!

Psize = 10      => [ 2 .. 10 ] seconds to execute 
                => order of generations needed [ 10000 - 80000 ]
Psize = 400     => [ 30 .. 60 ] seconds to execute 
                => order of generations needed [ 300 - 1000 ] 
Psize = 1000    => [ 120 .. 300]  seconds to execute 
                => order of generations needed [ 100 - 300 ] 
Psize = 100000  => [ 6000 .. 10000 ] seconds te execute

                => order of generations needed [ 100 - 300 ] 
Below you can see this exponential increase of the execution time vs the population size:





Also the generations needed decrease exponentially with an increase of the population size:

GA simple implementation code

This is the code that implements the class. Explanations can be found in the comments:

   
 // C/C++ libs includes  
 #include <time.h>  
 #include <algorithm>  
 #include <bitset>  
 #include <iostream>  
 #include <cstdlib>  
 #include <cmath>  
 #include <algorithm>  
   
 // my own project includes  
 #include "ga_basics.h"  
 #include "random.h"  
   
 // avoid qualifiers  
 using namespace std;  
   
 // *********************************************************  
 // IntegerPopulation implements pure virtual Population  
 // *********************************************************  
   
 void IntegerPopulation::CalculateAverageStrength (){  
     // ensure we can cope with large values 64 bit  
     unsigned long long avg = 0;  
       
     for (int i = 0 ; i < size ; i++)  
         avg += thePopulation[i];  
       
     averageStrength = (unsigned int) (avg/size);  
       
 }  
   
 void IntegerPopulation::ClearIntermediatePopulation(){  
     for (int i=0; i < size ; i++) {  
         breedPopulation[i] = DEAD;  
     }  
 }  
   
 // no constructor is used here  
 void IntegerPopulation::create (size_t n){  
       
     // size must always be even  
     if ( n % 2 ) n++;  
       
     // instantiate the populations  
     thePopulation    = new unsigned int[n];  
     breedPopulation = new unsigned int[n];  
     size = n;  
       
     // seed the radom with clock cycle  
     srand(clock());  
 }  
   
 // complexity is a factor between [0..1] and serves as minimum treshold  
 void IntegerPopulation::initialize(double complexity){  
       
     // fill the population with random values  
     for (int i=0; i < size ; i++) {  
         double treshold = complexity * TARGET;  
         unsigned int gene = rand();  
   
         // with respect to the initial complexity  
         while (gene > treshold) {  
             gene = rand();  
         }  
           
         thePopulation[i] = gene;  
         breedPopulation[i] = DEAD;  
     }  
       
     // must recalculate the average strength now  
     CalculateAverageStrength();  
 }  
   
 // destructor   
 IntegerPopulation::~IntegerPopulation(){  
     delete [] thePopulation;  
     delete [] breedPopulation;  
 }  
   
 // return the size   
 size_t IntegerPopulation::returnSize(){  
     return size;  
 }  
   
 // return a pointer to the population  
 unsigned int * IntegerPopulation::returnThePopulation(){  
     return thePopulation;  
 }  
   
 // return a pointer to intermidiate breed population  
 unsigned int * IntegerPopulation::returnBreedPopulation(){  
     return breedPopulation;  
 }  
   
 // return the average strength  
 unsigned int IntegerPopulation::returnAverageStrength(){  
     return averageStrength;  
 }  
   
 // in case we need to see the values  
 void IntegerPopulation::show(){  
     for (int i=0; i < size; i++) {  
         cout << hex << thePopulation[i] << endl;  
     }  
     cout << endl;  
 }  
   
 // *********************************************************  
 // ValueTarget implements pure virtual Target  
 // *********************************************************  
   
 bool ValueTarget::reached (Population * p , double weight){  
       
     // cast the base type  
     IntegerPopulation * iP = dynamic_cast<IntegerPopulation*> (p);  
       
     // after each new generation calculate the new average strength  
     iP->CalculateAverageStrength();  
       
     // solution weigth  
     double w = weight * TARGET;  
       
     if ( iP->returnAverageStrength() > w )  
         return true;  
       
     return false;  
 }  
   
 // *********************************************************  
 // ValueFitness implements pure virtual Fitness  
 // *********************************************************  
   
 void ValueFitness::run (Population * p){  
   
     // cast the base type  
     IntegerPopulation * iP = dynamic_cast<IntegerPopulation*> (p);  
       
     double    fractionPart;  
     double    integerPart;  
     int        amountOfCopies;  
     int        odds;  
     int        breedIndex=0;  
       
     // check the fitness against the average  
     for (int i = 0 ; i < iP->returnSize() ; i++){  
           
         // cast to double to get double precision for the fractional part  
         double avg = (double)(iP->returnThePopulation()[i] / (double) iP->returnAverageStrength());  
           
         // divide integer and fraction  
         fractionPart = modf(avg, &integerPart);  
           
         // calculate the copies and change to copy  
         amountOfCopies = integerPart;  
         odds = fractionPart * 100;  
           
         // start copying in function of the strength  
         while (amountOfCopies--) {  
             iP->returnBreedPopulation()[breedIndex++] = iP->returnThePopulation()[i];  
         }  
           
         // when breed population is full abort   
         if (breedIndex == iP->returnSize())    return;  
           
         // start a copy in function of the odds of the fractional part  
         if ( Odds(odds) ){  
             iP->returnBreedPopulation()[breedIndex++] = iP->returnThePopulation()[i];  
         }  
   
         // when breed population is full abort   
         if (breedIndex == iP->returnSize()) return;  
     }  
 }  
   
 // *********************************************************  
 // SimpleBreed implements pure virtual Breed  
 // *********************************************************  
   
 void SimpleBreed::crossover (Population &p, CROSSOVER c){  
       
     // cast the base type  
     IntegerPopulation * iP = dynamic_cast<IntegerPopulation*> (&p);  
       
     // create the individuals as bitset to ease the crossover  
     bitset <GENE_SIZE> male,female,child1,child2;  
       
     int size = iP->returnSize();  
     int index = size;  
       
     while (index) {  
           
         // take only the copies not the empty slots at random  
         while ( (male = iP->returnBreedPopulation()[rand()%size]) == DEAD );  
         while ( (female = iP->returnBreedPopulation()[rand()%size]) == DEAD);  
           
         // start with full inheritance  
         child1 = male;  
         child2 = female;  
           
         // continue with crossover  
         if (c == SINGLE_POINT){  
               
             // calculate point random  
             int point = rand() % GENE_SIZE;  
               
             // crossover bits  
             for (int LSB = 0 ; LSB < point; LSB++) {  
                 child1.set(LSB, female.test(LSB));  
                 child2.set(LSB, male.test(LSB));  
             }  
               
             // assign the bitsets  
             iP->returnThePopulation()[index--] = child1.to_ulong();  
             iP->returnThePopulation()[index--] = child2.to_ulong();  
         }  
         else if( c == TWO_POINT ) {  
               
             // calculate two points random with p2 > p1  
             int point2 = rand() % GENE_SIZE;  
             int point1 = rand() % (point2+1);  
           
             // crossover bits  
             for (int LSB = point1 ; LSB < point2; LSB++) {  
                 child1.set(LSB, female.test(LSB));  
                 child2.set(LSB, male.test(LSB));  
             }  
               
             // assign  
             iP->returnThePopulation()[index--] = child1.to_ulong();  
             iP->returnThePopulation()[index--] = child2.to_ulong();  
               
         }              
     }  
       
     // clear out the intermediate for the next run  
     iP->ClearIntermediatePopulation();  
 }  
   
 void SimpleBreed::mutate (Population &p, int odds ){  
       
     // cast the base type      
     IntegerPopulation * iP = dynamic_cast<IntegerPopulation*> (&p);  
       
     // consider the gene as bitset  
     bitset<GENE_SIZE> gene;  
       
     int index = iP->returnSize();  
       
     while (index--) {  
           
         // Only with a probabilty of odds in percent do the mutation  
         if ( Odds(odds) ) {  
               
             // we just a flip a random bit with no distance limitations  
             gene = iP->returnThePopulation()[index];  
             gene.flip(rand() % gene.size());  
             iP->returnThePopulation()[index] = gene.to_ulong();  
         }  
     }  
       
 }  
   

GA simple implementation header

This is the header file of the canonical implementation derived from the virtual interface:

 #include "ga.h"  
 #define TARGET    0xFFFFFFFF  
 #define DEAD      0  
 #define GENE_SIZE 32   
 //************ The population  
 class IntegerPopulation:public Population {  
 private:  
     unsigned int *    thePopulation;  
     unsigned int *    breedPopulation;  
     unsigned int      averageStrength;  
     size_t size;  
 public:  
     void create (size_t n);  
     void initialize (double complexity = 0.2);  
     size_t returnSize();  
     void show();  
     unsigned int * returnThePopulation();  
     unsigned int * returnBreedPopulation();  
     void CalculateAverageStrength();  
     unsigned int returnAverageStrength();  
     void ClearIntermediatePopulation();  
     ~IntegerPopulation ();  
 };  
 //************* The target  
 class ValueTarget:public Target{  
 public:  
     bool reached (Population * p,double weight = 0.95);  
 };  
 //************* The fitness  
 class ValueFitness:public Fitness{  
 public:  
     void run (Population * p);  
 };  
 //************* The breed  
 class SimpleBreed:public Breed{  
 public:  
     void mutate (Population &p, int odds=1);  
     void crossover (Population &p, CROSSOVER c = SINGLE_POINT);  
 };  

GA virtual interface

I will use C++ as language to implement the canonical genetic algorithm.

 #include <unistd.h>  
 enum CROSSOVER {  
     SINGLE_POINT,TWO_POINT  
 };  
 class Population{  
     virtual void create (size_t n)=0;  
     virtual void initialize (double complexity = 0.2)=0;  
 };  
 class Target{  
     virtual bool reached (Population * p , double weight = 0.99)=0;  
 };  
 class Fitness{  
     virtual void run (Population * p)=0;  
 };  
 class Breed{  
     virtual void mutate (Population &p, int odds=1)=0;  
     virtual void crossover (Population &p, CROSSOVER c = SINGLE_POINT)=0;  
 };  
 class Result{  
     virtual void intermidiate (void)=0;  
     virtual void totalize (void)=0;  
 };  

 For those interested in the link to insert code snippets into your blog here is the link:

http://codeformatter.blogspot.com/