Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

# Tools/Evolution/Population.h

Go to the documentation of this file.

    00001 /**
    00002 * @file Population.h
    00003 *
    00004 * Declaration of class Population
    00005 *
    00006 * @author <a href=mailto:dueffert@informatik.hu-berlin.de>Uwe Düffert</a>
    00007 */
    00008
    00009 #ifndef __Population_h_
    00010 #define __Population_h_
    00011
    00012 #include "Tools/Math/Common.h"
    00013 #include "Tools/Streams/InOut.h"
    00014 #include "Platform/GTAssert.h"
    00015 #include "Tools/Debugging/Debugging.h"
    00016
    00017 /**
    00018 * @class Population
    00019 *
    00020 * Contains a population of parameter sets derived from class Individual.
    00021 */
    00022 template<class T, int siz> class Population
    00023 {
    00024 public:
    00025   /** Constructor. */
    00026   Population()
    00027   {
    00028     for (int i=0;i<siz;i++)
    00029     {
    00030       individual[i]=new T;
    00031     }
    00032   }
    00033
    00034   /** Destructor. */
    00035   ~Population()
    00036   {
    00037     for (int i=0;i<siz;i++)
    00038     {
    00039       delete(individual[i]);
    00040     }
    00041   }
    00042
    00043   /** returns the next individual thats fitness was not tested before, or NULL if all individuals have a fitness */
    00044   T* getNextIndividualWithoutFitness()
    00045   {
    00046     for (int i=0;i<siz;i++)
    00047     {
    00048       if (individual[i]->fitness<0)
    00049       {
    00050         return individual[i];
    00051       }
    00052     }
    00053     return 0;
    00054   }
    00055
    00056   /** returns fitness of the best individual */
    00057   double getBestFitness()
    00058   {
    00059     double best=0;
    00060     for (int i=0;i<siz;i++)
    00061     {
    00062       if (individual[i]->fitness>best)
    00063       {
    00064         best= individual[i]->fitness;
    00065       }
    00066     }
    00067     return best;
    00068   }
    00069
    00070   /** outputs best fitness, average better half fitness and average fitness of individuals with fitness greater 0
    00071   * @param file if an OutTextRawFile is given, output will be appended there too
    00072   */
    00073   void outputStatistics(OutTextRawFile* file=0)
    00074   {
    00075     int* individualIndex=new int[siz];
    00076     int i,j;
    00077     for (i=0;i<siz;i++)
    00078     {
    00079       individualIndex[i]=i;
    00080     }
    00081     //bubblesort for fitness:
    00082     for (i=0;i<siz-1;i++)
    00083     {
    00084       for (j=0;j<siz-i-1;j++)
    00085       {
    00086         if (individual[individualIndex[j]]->fitness<individual[individualIndex[j+1]]->fitness)
    00087         {
    00088           int tmp=individualIndex[j];
    00089           individualIndex[j]=individualIndex[j+1];
    00090           individualIndex[j+1]=tmp;
    00091         }
    00092       }
    00093     }
    00094     //calculate averages:
    00095     double best=individual[individualIndex[0]]->fitness;
    00096     double better=0,avg=0;
    00097     int betterCount=0,avgCount=0;
    00098     for (i=0;i<siz;i++)
    00099     {
    00100       if (individual[individualIndex[i]]->fitness<=0)
    00101       {
    00102         break;
    00103       }
    00104       avg += individual[individualIndex[i]]->fitness;
    00105       avgCount++;
    00106       if (betterCount<siz/2)
    00107       {
    00108         better += individual[individualIndex[i]]->fitness;
    00109         betterCount++;
    00110       }
    00111     }
    00112     if (betterCount>0)
    00113     {
    00114       better /= betterCount;
    00115     }
    00116     if (avgCount>0)
    00117     {
    00118       avg /= avgCount;
    00119     }
    00120     OUTPUT(idText,text,"Population: best=" << best << ", betterHalf=" << better << ", avg=" << avg);
    00121     if (file)
    00122     {
    00123       *file << "Population: best=" << best << ", betterHalf=" << better << ", avg=" << avg << "\n";
    00124     }
    00125   }
    00126
    00127   /** does one step in evolution, you can use normal or uniform distributed noise for mutation */
    00128   void evolve(double offspringrate=0.45, double crossormuta=0.4, double mutarate=0.3, double mutastrength=0.2, bool uniformNoise=false)
    00129   {
    00130     //we could add parameter for choosing of child/parent
    00131     int* individualIndex=new int[siz];
    00132     int i,j;
    00133     for (i=0;i<siz;i++)
    00134     {
    00135       individualIndex[i]=i;
    00136     }
    00137     //bubblesort potential parents for fitness:
    00138     for (i=0;i<siz-1;i++)
    00139     {
    00140       for (j=0;j<siz-i-1;j++)
    00141       {
    00142         if (individual[individualIndex[j]]->fitness<individual[individualIndex[j+1]]->fitness)
    00143         {
    00144           int tmp=individualIndex[j];
    00145           individualIndex[j]=individualIndex[j+1];
    00146           individualIndex[j+1]=tmp;
    00147         }
    00148       }
    00149     }
    00150     //replace the worst offspringrate*siz individuals with mutations + crossings of the rest
    00151     //so 0...lastParent remain parents and lastParent+1...siz-1 are replaced by mutations + crossings
    00152     int lastParent=(int)((1.0-offspringrate)*siz-0.5);
    00153     if (lastParent>=siz-1)
    00154     {
    00155       lastParent=siz-2;
    00156     }
    00157     else if (lastParent<=0)
    00158     {
    00159       lastParent=1;
    00160     }
    00161     //replace the bad individuals with mutations/crossings of good ones
    00162     for (i=lastParent+1;i<siz;i++)
    00163     {
    00164       int parent1=random(lastParent+1);
    00165       if (random()<crossormuta)
    00166       {
    00167         int parent2;
    00168         do
    00169         {
    00170           parent2=random(lastParent+1);
    00171         }
    00172         while (parent1==parent2);
    00173         individual[individualIndex[i]]->crossingOverOf(individual[individualIndex[parent1]],individual[individualIndex[parent2]]);
    00174       }
    00175       else
    00176       {
    00177         individual[individualIndex[i]]->mutationOf(individual[individualIndex[parent1]],mutarate,mutastrength,uniformNoise);
    00178       }
    00179     }
    00180     delete(individualIndex);
    00181   }
    00182
    00183   T* individual[siz];
    00184 };
    00185
    00186 /**
    00187  * Streaming operator that reads a Population<T,siz> from a stream
    00188  * @param stream The stream from which is read.
    00189  * @param population The Population object.
    00190  * @return The stream.
    00191  */
    00192 template<class T, int siz> In& operator>>(In& stream,Population<T,siz>& population)
    00193 {
    00194   int s;
    00195   stream >> s;
    00196   ASSERT(s==siz);
    00197   for (int i=0;i<siz;i++)
    00198   {
    00199     stream >> *(T*)population.individual[i];
    00200     stream >> population.individual[i]->fitness;
    00201   }
    00202   return stream;
    00203 }
    00204
    00205 /**
    00206  * Streaming operator that writes a Population<T,siz> to a stream.
    00207  * @param stream The stream to write on.
    00208  * @param population The Population object.
    00209  * @return The stream.
    00210  */
    00211 template<class T, int siz> Out& operator<<(Out& stream, const Population<T,siz>& population)
    00212 {
    00213   int s=siz;
    00214   stream << s;
    00215   for (int i=0;i<siz;i++)
    00216   {
    00217     stream << *(T*)population.individual[i];
    00218     stream << population.individual[i]->fitness;
    00219   }
    00220   return stream;
    00221 }
    00222
    00223 #endif //__Population_h_