home *** CD-ROM | disk | FTP | other *** search
/ AI Game Programming Wisdom / AIGameProgrammingWisdom.iso / SourceCode / 11 Learning / 01 Manslow / GAPBILExample / CPBIL.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2001-10-09  |  7.6 KB  |  309 lines
  1. //GAPBILExample
  2. //Copyright John Manslow
  3. //29/09/2001
  4.  
  5. ////////////////////////////////////////////////////
  6. //Remove this include if not compiling under Windows
  7. #include "stdafx.h"
  8. #define new DEBUG_NEW
  9. ////////////////////////////////////////////////////
  10.  
  11. #include "CPBIL.h"
  12. #include "assert.h"
  13. #include "fstream.h"
  14.  
  15. CPBIL::CPBIL(
  16.          const unsigned long    ulNewPopulationSize,
  17.          const unsigned long    ulNewChromosomeLength
  18.          )
  19. {
  20.     //Check validity of arguments
  21.     assert(!(ulNewPopulationSize<1));
  22.     ulPopulationSize=ulNewPopulationSize;
  23.  
  24.     assert(!(ulNewChromosomeLength<1));
  25.     ulChromosomeLength=ulNewChromosomeLength;
  26.  
  27.     //Set default mutation and adaptation rates
  28.     dMutationRate=0.01/double(ulChromosomeLength);
  29.     dAdaptationRate=0.1;
  30.  
  31.     //Reset the fitness evaluation counter
  32.     ulIteration=0;
  33.  
  34.     //Allocate memory to store the population
  35.     AllocateMemory();
  36. }
  37.  
  38. CPBIL::~CPBIL()
  39. {
  40.     //Clean up
  41.     DeallocateMemory();
  42. }
  43.  
  44. void CPBIL::AllocateMemory(void)
  45. {
  46.     unsigned long i;
  47.  
  48.     //Create storage for the population
  49.     ppdGenes=new double*[ulPopulationSize];
  50.     for (i=0;i<ulPopulationSize;i++)
  51.     {
  52.         ppdGenes[i]=new double[ulChromosomeLength];
  53.     }
  54.  
  55.     //And for the fitnesses of the chromosomes within it
  56.     pdFitnesses=new double[ulPopulationSize];
  57.  
  58.     //Create storage for the gene probability vector
  59.     pdGeneProbabilities=new double[ulChromosomeLength];
  60.  
  61.     //Set gene probabilities to 0.5 so that initially, each gene is equally likely to be 0 or 1
  62.     for (i=0;i<ulChromosomeLength;i++)
  63.     {
  64.             pdGeneProbabilities[i]=0.5;
  65.     }
  66.  
  67.     //Declare stoarge for a copy of the best chromosome discovered so far and set its fitness to a large
  68.     //negative number so that it'll be overwritten immediately
  69.     pdBestChromosome=new double[ulChromosomeLength];
  70.     dBestFitness=-1e+100;
  71. }
  72.  
  73. void CPBIL::DeallocateMemory(void)
  74. {
  75.     unsigned long i;
  76.     delete []pdFitnesses;
  77.  
  78.     for (i=0;i<ulPopulationSize;i++)
  79.     {
  80.         delete []ppdGenes[i];
  81.     }
  82.     delete []ppdGenes;
  83.     delete []pdGeneProbabilities;
  84.     delete []pdBestChromosome;
  85. }
  86.  
  87. void CPBIL::CreatePopulation(void)
  88. {
  89.     //This function is called to create a population of chromosomes by sampling form the probability distribution
  90.     //given in pdGeneProbabilities. 
  91.     unsigned long i,j;
  92.  
  93.     //For each chromosome in the population
  94.     for (i=0;i<ulPopulationSize;i++)
  95.     {
  96.         //Reset its fitness
  97.         pdFitnesses[i]=0.0;
  98.  
  99.         //For each gene in the ith chromosome
  100.         for (j=0;j<ulChromosomeLength;j++)
  101.         {
  102.             //Set the gene to either 0 or 1 in accordance with the gene probability vector
  103.             if(double(rand())/double(RAND_MAX)>pdGeneProbabilities[j])
  104.             {
  105.                 ppdGenes[i][j]=0.0;
  106.             }
  107.             else
  108.             {
  109.                 ppdGenes[i][j]=1.0;
  110.             }
  111.         }
  112.     }
  113. }
  114.  
  115. void CPBIL::Mutate(void)
  116. {
  117.     //The mutate function resets a randomly selected element of the gene probability vector to 0.5. Mutation
  118.     //can usually be removed with the PBIL - provded that its population size is large and rate of adaptation is
  119.     //small. Mutation should have a much lower probability than in the GA
  120.     unsigned long i;
  121.     for (i=0;i<ulChromosomeLength;i++)
  122.     {
  123.         if(double(rand())/double(RAND_MAX)<dMutationRate)
  124.         {
  125.             pdGeneProbabilities[i]=0.5;
  126.         }
  127.     }
  128. }
  129.  
  130. double *CPBIL::pdGetChromosomeForEvaluation(void)
  131. {
  132.     //This function automatically selects each chromosome in the population, and once
  133.     //all have been evaluated, creates a new population
  134.     unsigned long i;
  135.  
  136.     //ff the chromosome selector (i.e. ulIteration%ulPopulationSize) indicates the first chromosome in the
  137.     //population needs to be evaluted, a new population needs to be created
  138.     if (ulIteration%ulPopulationSize==0)
  139.     {
  140.         CreatePopulation();
  141.     }
  142.  
  143.     //Set the working chromosome to the location of the chromosome in the population so that when SetFitness
  144.     //is called, we know which chromosome it refers to
  145.     ulWorkingChromosome=ulIteration%ulPopulationSize;
  146.  
  147.     //Create space for a copy of the chromosome that needs to be evaluated
  148.     double *pdChromosomeForEvaluation=new double[ulChromosomeLength];
  149.     for (i=0;i<ulChromosomeLength;i++)
  150.     {
  151.         //Copy the genes into it
  152.         pdChromosomeForEvaluation[i]=ppdGenes[ulWorkingChromosome][i];
  153.     }
  154.  
  155.     //Return it to the clling function
  156.     return pdChromosomeForEvaluation;
  157. }
  158.     
  159. void CPBIL::SetFitness(const double dNewFitness)
  160. {
  161.     //This function records the ftiness of the chromosome that has just beenevaluated. If the chromosome 
  162.     //selector (i.e. ulIteration%ulPopulationSize) has wrapped around to the start of the population, we have 
  163.     //evaluated the fitnesses of every individual in the population and hence can update the gene probability 
  164.     //vector.
  165.     unsigned long i;
  166.     double dHighestFitness=0.0;
  167.     unsigned long ulFittestChromosome=0;
  168.  
  169.     //Increment the counter of the number of fitness evaluations
  170.     ulIteration++;
  171.  
  172.     //Record the fitness
  173.     pdFitnesses[ulWorkingChromosome]=dNewFitness;
  174.  
  175.     //If its the best discovered so far take a copy of it
  176.     if(dNewFitness>dBestFitness)
  177.     {
  178.         dBestFitness=dNewFitness;
  179.         unsigned long i;
  180.         for(i=0;i<ulChromosomeLength;i++)
  181.         {
  182.             pdBestChromosome[i]=ppdGenes[ulWorkingChromosome][i];
  183.         }
  184.     }
  185.  
  186.     //If the chromosome selector has wrapped around to the start of the population
  187.     if(ulIteration%ulPopulationSize==0)
  188.     {
  189.         //Find the fittest chromosome in the population
  190.         for(i=0;i<ulPopulationSize;i++)
  191.         {
  192.             if(pdFitnesses[i]>dHighestFitness)
  193.             {
  194.                 dHighestFitness=pdFitnesses[i];
  195.                 ulFittestChromosome=i;
  196.             }
  197.         }
  198.  
  199.         //Update the gene probabilities by changing them to increase the chance that the best chromosome in
  200.         //this population is reproduced more frequenctly in future
  201.         for(i=0;i<ulChromosomeLength;i++)
  202.         {
  203.             pdGeneProbabilities[i]+=dAdaptationRate*(ppdGenes[ulFittestChromosome][i]-pdGeneProbabilities[i]);
  204.         }
  205.  
  206.         //Mutate the probability vector
  207.         Mutate();
  208.     }
  209. }
  210.  
  211. double *CPBIL::pdGetBestChromosome(void)
  212. {
  213.     //Return a pointer to the best chromosome. Its not a copy, so don't delete it!
  214.     return pdBestChromosome;
  215. }
  216.  
  217. double CPBIL::dGetBestPerformance(void)
  218. {
  219.     //Return the best fitness achieved so far
  220.     return dBestFitness;
  221. }
  222.  
  223. int CPBIL::Save(const char * const psFilename)
  224. {
  225.     //Save the PBIL's status
  226.     ofstream *pOut=new ofstream(psFilename);
  227.     unsigned long i,j;
  228.     if(!pOut || !pOut->is_open())
  229.     {
  230.         return 0;
  231.     }
  232.     pOut->precision(18);
  233.     *pOut<<ulPopulationSize;
  234.     *pOut<<"\n";
  235.     *pOut<<ulChromosomeLength;
  236.     *pOut<<"\n";
  237.     *pOut<<dMutationRate;
  238.     *pOut<<"\n";
  239.     *pOut<<ulIteration;
  240.     *pOut<<"\n";
  241.     *pOut<<ulWorkingChromosome;
  242.     *pOut<<"\n";
  243.     for (i=0;i<ulPopulationSize;i++)
  244.     {
  245.         for (j=0;j<ulChromosomeLength;j++)
  246.         {
  247.             *pOut<<ppdGenes[i][j];
  248.             *pOut<<"\t";
  249.         }
  250.         *pOut<<pdFitnesses[i];
  251.         *pOut<<"\n";
  252.     }
  253.     for (i=0;i<ulChromosomeLength;i++)
  254.     {
  255.         *pOut<<pdGeneProbabilities[i];
  256.         *pOut<<"\t";
  257.     }
  258.     *pOut<<"\n";
  259.     *pOut<<dBestFitness;
  260.     *pOut<<"\n";
  261.     for (j=0;j<ulChromosomeLength;j++)
  262.     {
  263.         *pOut<<pdBestChromosome[j];
  264.         *pOut<<"\t";
  265.     }
  266.     *pOut<<"\n";
  267.     pOut->close();
  268.     delete pOut;
  269.     return 1;
  270. }
  271.  
  272. int CPBIL::Load(const char * const psFilename)
  273. {
  274.     //Load the PBIL's status
  275.     ifstream *pIn=new ifstream(psFilename,ios::nocreate);
  276.     unsigned long i,j;
  277.     if(!pIn || !pIn->is_open())
  278.     {
  279.         return 0;
  280.     }
  281.     DeallocateMemory();
  282.     *pIn>>ulPopulationSize;
  283.     *pIn>>ulChromosomeLength;
  284.     AllocateMemory();
  285.     *pIn>>dMutationRate;
  286.     *pIn>>ulIteration;
  287.     *pIn>>ulWorkingChromosome;
  288.     for (i=0;i<ulPopulationSize;i++)
  289.     {
  290.         for (j=0;j<ulChromosomeLength;j++)
  291.         {
  292.             *pIn>>ppdGenes[i][j];
  293.         }
  294.         *pIn>>pdFitnesses[i];
  295.     }
  296.     for (i=0;i<ulChromosomeLength;i++)
  297.     {
  298.         *pIn>>pdGeneProbabilities[i];
  299.     }
  300.     *pIn>>dBestFitness;
  301.     for (j=0;j<ulChromosomeLength;j++)
  302.     {
  303.         *pIn>>pdBestChromosome[j];
  304.     }
  305.     pIn->close();
  306.     delete pIn;
  307.     return 1;
  308. }
  309.