Tools/Evolution/Population.h

Go to the documentation of this file.

/**
* @file Population.h
* 
* Declaration of class Population
*
* @author <a href=mailto:dueffert@informatik.hu-berlin.de>Uwe Düffert</a>
*/ 

#ifndef __Population_h_
#define __Population_h_

#include "Tools/Math/Common.h"
#include "Tools/Streams/InOut.h"
#include "Platform/GTAssert.h"
#include "Tools/Debugging/Debugging.h"

/**
* @class Population
*
* Contains a population of parameter sets derived from class Individual.
*/ 
template<class T, int siz> class Population
{
public:
  /** Constructor. */
  Population()
  {
    for (int i=0;i<siz;i++)
    {
      individual[i]=new T;
    }
  }
  
  /** Destructor. */
  ~Population()
  {
    for (int i=0;i<siz;i++)
    {
      delete(individual[i]);
    }
  }
  
  /** returns the next individual thats fitness was not tested before, or NULL if all individuals have a fitness */
  T* getNextIndividualWithoutFitness()
  {
    for (int i=0;i<siz;i++)
    {
      if (individual[i]->fitness<0)
      {
        return individual[i];
      }
    }
    return 0;
  }
  
  /** returns fitness of the best individual */
  double getBestFitness()
  {
    double best=0;
    for (int i=0;i<siz;i++)
    {
      if (individual[i]->fitness>best)
      {
        best= individual[i]->fitness;
      }
    }
    return best;
  }
  
  /** outputs best fitness, average better half fitness and average fitness of individuals with fitness greater 0
  * @param file if an OutTextRawFile is given, output will be appended there too
  */
  void outputStatistics(OutTextRawFile* file=0)
  {
    int* individualIndex=new int[siz];
    int i,j;
    for (i=0;i<siz;i++)
    {
      individualIndex[i]=i;
    }
    //bubblesort for fitness:
    for (i=0;i<siz-1;i++)
    {
      for (j=0;j<siz-i-1;j++)
      {
        if (individual[individualIndex[j]]->fitness<individual[individualIndex[j+1]]->fitness)
        {
          int tmp=individualIndex[j];
          individualIndex[j]=individualIndex[j+1];
          individualIndex[j+1]=tmp;
        }
      }
    }
    //calculate averages:
    double best=individual[individualIndex[0]]->fitness;
    double better=0,avg=0;
    int betterCount=0,avgCount=0;
    for (i=0;i<siz;i++)
    {
      if (individual[individualIndex[i]]->fitness<=0)
      {
        break;
      }
      avg += individual[individualIndex[i]]->fitness;
      avgCount++;
      if (betterCount<siz/2)
      {
        better += individual[individualIndex[i]]->fitness;
        betterCount++;
      }
    }
    if (betterCount>0)
    {
      better /= betterCount;
    }
    if (avgCount>0)
    {
      avg /= avgCount;
    }
    OUTPUT(idText,text,"Population: best=" << best << ", betterHalf=" << better << ", avg=" << avg);
    if (file)
    {
      *file << "Population: best=" << best << ", betterHalf=" << better << ", avg=" << avg << "\n";
    }
  }
  
  /** does one step in evolution, you can use normal or uniform distributed noise for mutation */
  void evolve(double offspringrate=0.45, double crossormuta=0.4, double mutarate=0.3, double mutastrength=0.2, bool uniformNoise=false)
  {
    //we could add parameter for choosing of child/parent
    int* individualIndex=new int[siz];
    int i,j;
    for (i=0;i<siz;i++)
    {
      individualIndex[i]=i;
    }
    //bubblesort potential parents for fitness:
    for (i=0;i<siz-1;i++)
    {
      for (j=0;j<siz-i-1;j++)
      {
        if (individual[individualIndex[j]]->fitness<individual[individualIndex[j+1]]->fitness)
        {
          int tmp=individualIndex[j];
          individualIndex[j]=individualIndex[j+1];
          individualIndex[j+1]=tmp;
        }
      }
    }
    //replace the worst offspringrate*siz individuals with mutations + crossings of the rest
    //so 0...lastParent remain parents and lastParent+1...siz-1 are replaced by mutations + crossings
    int lastParent=(int)((1.0-offspringrate)*siz-0.5);
    if (lastParent>=siz-1)
    {
      lastParent=siz-2;
    }
    else if (lastParent<=0)
    {
      lastParent=1;
    }
    //replace the bad individuals with mutations/crossings of good ones
    for (i=lastParent+1;i<siz;i++)
    {
      int parent1=random(lastParent+1);
      if (random()<crossormuta)
      {
        int parent2;
        do
        {
          parent2=random(lastParent+1);
        }
        while (parent1==parent2);
        individual[individualIndex[i]]->crossingOverOf(individual[individualIndex[parent1]],individual[individualIndex[parent2]]);
      }
      else
      {
        individual[individualIndex[i]]->mutationOf(individual[individualIndex[parent1]],mutarate,mutastrength,uniformNoise);
      }
    }
    delete(individualIndex);
  }
  
  T* individual[siz];
};

/**
 * Streaming operator that reads a Population<T,siz> from a stream
 * @param stream The stream from which is read.
 * @param population The Population object.
 * @return The stream.
 */ 
template<class T, int siz> In& operator>>(In& stream,Population<T,siz>& population)
{
  int s;
  stream >> s;
  ASSERT(s==siz);
  for (int i=0;i<siz;i++)
  {
    stream >> *(T*)population.individual[i];
    stream >> population.individual[i]->fitness;
  }
  return stream;
}
 
/**
 * Streaming operator that writes a Population<T,siz> to a stream.
 * @param stream The stream to write on.
 * @param population The Population object.
 * @return The stream.
 */ 
template<class T, int siz> Out& operator<<(Out& stream, const Population<T,siz>& population)
{
  int s=siz;
  stream << s;
  for (int i=0;i<siz;i++)
  {
    stream << *(T*)population.individual[i];
    stream << population.individual[i]->fitness;
  }
  return stream;
}

#endif //__Population_h_

/*
* Change log :
* 
* $Log: Population.h,v $
* Revision 1.1.1.1  2004/05/22 17:36:14  cvsadm
* created new repository GT2004_WM
*
* Revision 1.11  2004/03/26 09:17:22  dueffert
* selection bug fixed
*
* Revision 1.10  2004/03/24 13:44:49  dueffert
* support for uniform noise mutation readded
*
* Revision 1.9  2004/03/19 09:19:50  dueffert
* output improved
*
* Revision 1.8  2004/03/10 09:56:56  dueffert
* statistics added
*
* Revision 1.7  2004/03/09 13:57:05  dueffert
* missing header readded
*
* Revision 1.6  2004/03/09 13:30:14  dueffert
* streaming operator and logic improved
*
* Revision 1.5  2004/03/09 11:40:55  wachter
* included Platform/GTAssert.h
*
* Revision 1.4  2004/02/27 12:51:47  dueffert
* streaming operator added
*
* Revision 1.3  2004/01/07 11:23:34  dueffert
* selection implemented
*
* Revision 1.2  2003/10/28 13:25:26  dueffert
* spelling improved
*
* Revision 1.1  2003/09/26 11:40:40  juengel
* - sorted tools
* - clean-up in DataTypes
*
* Revision 1.4  2003/09/01 15:57:42  dueffert
* Genom and Individual merged
*
* Revision 1.3  2003/08/08 15:43:25  dueffert
* some evolution implementation added
*
* Revision 1.2  2003/08/08 14:27:07  dueffert
* implementation added
*
* Revision 1.1.1.1  2003/07/02 09:40:22  cvsadm
* created new repository for the competitions in Padova from the 
* tamara CVS (Tuesday 2:00 pm)
*
* removed unused solutions
*
* Revision 1.1  2003/02/10 15:26:58  dueffert
* self made GA stuff
*
*/

---