Tools/Evolution/BB2004Evo.h

Go to the documentation of this file.

/**
* @file BB2004Evo.h
* 
* This file implements a general approach to Evolutionary Algorithms.
*
* @author <a href="mailto:roefer@tzi.de">Thomas Röfer</a>
*/

/**
*/

#ifndef __BB2004Evo_h__
#define __BB2004Evo_h__

#include <stdlib.h>

/**
* The class is the abstract base class for indiviuals.
* Concrete implementations only have to be derived from this class.
*/
class BBIndividual
{
public:
  /**
  * The function initializes the current individual with another one.
  * It has to be implemented in a derived class.
  * @param initial The other individual the current one is initialized with.
  */
  virtual void init(const BBIndividual& initial) = 0;
  
  /**
  * The function interpolates between the current individual and another one.
  * The result is stored in the current individual.
  * It has to be implemented in a derived class.
  * @param other The other individual the current one is interpolated with.
  */
  virtual void interpolate(const BBIndividual& other) = 0;

  /**
  * The function extrapolates between the current individual and another one.
  * It has to be implemented in a derived class.
  * @param other The other individual the current one is extrapolated with.
  */
  virtual void extrapolate(const BBIndividual& other) = 0;

  /**
  * The function mutates the current individual.
  * It has to be implemented in a derived class.
  */
  virtual void mutate() = 0;

  /**
  * The function calculates the fitness of the individual.
  * It has to be implemented in a derived class.
  * @return The fitness as a number >= 0. A higher result means a higher fitness.
  */
  virtual double getFitness() const = 0;
};

/**
* The class does some statistics on the number of individuals drawn.
*/
class Statistics
{
private:
  int size; /**< The number of entries in the histogram. */
  int* stats; /**< A histogram that counts how often each individual was drawn. */

  /** 
  * The function compares two integers as required for qsort.
  * @param i1 The address of the first integer.
  * @param i2 The address of the second integer.
  * @return -1 if the first integer is larger, 1 if it smaller, otherwise 0.
  *         Results in a descending order.
  */
  static int compare(const int* i1, const int* i2)
  {
    return *i1 > *i2 ? -1 : *i1 < *i2;
  }

public:
  /**
  * Constructor.
  * @param size The number of entries in the histogram.
  */
  Statistics(int size)
  {
    this->size = size;
    stats = new int[size];
    reset();
  }

  /**
  * Destructor.
  */
  ~Statistics() {delete [] stats;}

  /**
  * The function empties the histogram.
  */
  void reset()
  {
    for(int i = 0; i < size; ++i)
      stats[i] = 0;
  }

  /**
  * The function adds a single entry to the histogram.
  * @param index The index of the entry that is incremented by 1.
  */
  void add(int index) {++stats[index];}

  /**
  * The function analyzes the histogram and brings it into a compact form.
  * It removes all empty entries and sorts the others in descending order.
  * Please note that the function destoys the data in the histogram.
  * @return The number of entries remaining.
  */
  int analyze()
  {
    int dest = 0,
        src;
    for(src = 0; src < size; ++src)
      if(stats[src])
        stats[dest++] = stats[src];
    qsort(stats, dest, sizeof(int), (int (*)(const void*, const void*)) compare);
    return dest;
  }

  /**
  * The operator allows for accessing the entries in the histogram.
  * @param index The index of the entry to return.
  * @return The entry of the histogram with the given entry.
  */
  int operator[](int index) const {return stats[index];}
};

/**
* The template class represents a population of indiviuals.
* @param T The class of the individuals. It has to be derived from 
*          class BBIndividual.
*/
template<class T> class BBPopulation
{
private:
  Statistics statistics; /**< The object is used to do some statistics on drawing individuals. */
  T* current, /**< The current set of individuals. */
   * old; /**< The previous set of individuals. */
  int size; /**< The number of individuals in the population. */
  double* fitness; /**< The fitnesses of the individuals. */
  double* fitnessSum; /**< The accumulated fitnesses of the individuals. */
  double overallFitness; /**< The sum of fitness in the current population. */

  /**
  * The function provides random values.
  * @return A random value in the range of [0 ... 1[.
  */
  static double random() {return rand() / (double(RAND_MAX) + 1);}

  /**
  * The function draws an indiviual from the previous population.
  * The probability of being drawn is based on the ratio of the individual
  * fitness in relation to the overall fitness of the population.
  * @return The individual that has been drawn.
  */
  const T& drawIndividual()
  {
    double randomValue = random() * overallFitness;
    int low = 0,
      up = size;
    while(low != up - 1)
    {
      int middle = (low + up) / 2;
      if(randomValue < fitnessSum[middle])
        up = middle;
      else
        low = middle;
    }
    statistics.add(low);
    return old[low];
  }

  /**
  * The function updates the fitness of the whole population.
  * It also updates the overall fitness.
  */
  void updateFitness()
  {
    overallFitness = 0;
    for(int i = 0; i < size; ++i)
    {
      fitnessSum[i] = overallFitness;
      fitness[i] = current[i].getFitness();
      overallFitness += fitness[i];
    }
  }

  /**
  * The function mutates the half of the population if a single individual was drawn too often.
  */
  void mutate()
  {
    int i;
    for(i = 0; i < size && statistics[i] <= size; ++i)
      ;
    if(i < size)
      for(i = 0; i < size; i += 2)
        current[i].mutate();
  }

public:
  /**
  * Constructor.
  * @param size The number of individuals in the population.
  * @param initial The individual the population is initialized with.
  */
  BBPopulation(int size, const BBIndividual& initial)
  : statistics(size)
  {
    this->size = size;
    current = new T[size];
    old = new T[size];
    fitness = new double[size];
    fitnessSum = new double[size];
    for(int i = 0; i < size; ++i)
      current[i].init(initial);
  }

  /**
  * Destructor.
  */
  ~BBPopulation()
  {
    delete [] current;
    delete [] old;
    delete [] fitness;
    delete [] fitnessSum;
  }

  /**
   * The function returns the number of Individuals.
   * @return The number of individuals.
   */
  int getSize() const {return size;}

  /**
   * The operator provides access to the individuals.
   * @param index The index of the individual.
   * @return A reference to the individual with the index.
   */
  T& operator[](int index) {return current[index];}

  /**
   * The constant operator provides access to the individuals.
   * @param index The index of the individual.
   * @return A reference to the individual with the index.
   */
  const T& operator[](int index) const {return current[index];}

  /**
  * The function evolves the population.
  * @return The fittest individual.
  */
  void interpolate()
  {
    updateFitness();

    // current <-> old
    T* temp = old;
    old = current;
    current = temp;

    statistics.reset();
    for(int i = 0; i < size; ++i)
    {
      current[i] = drawIndividual();
      current[i].interpolate(drawIndividual());
    }
    mutate();    
  }

  void extrapolate()
  {
    updateFitness();

    // current <-> old
    T* temp = old;
    old = current;
    current = temp;

    statistics.reset();
    for(int i = 0; i < size; ++i)
    {
      current[i] = drawIndividual();
      current[i].extrapolate(drawIndividual());
    }
    mutate();
  }

  const BBIndividual& getFittest()
  {
    updateFitness();

    int fittest = 0;
    for(int i = 1; i < size; ++i)
      if(fitness[fittest] < fitness[i])
        fittest = i;
    return current[fittest];
  }

  Statistics& getStatistics() {return statistics;}
};

#endif // __BB2004Evo_h_

/*
* Change log :
* 
* $Log: BB2004Evo.h,v $
* Revision 1.1.1.1  2004/05/22 17:36:13  cvsadm
* created new repository GT2004_WM
*
* Revision 1.1  2004/03/03 21:17:11  roefer
* For the sake of consistency, renamed BB* to BB2004*
*
* Revision 1.4  2004/03/03 08:02:24  roefer
* Missing comments added
*
* Revision 1.3  2004/02/16 17:56:32  dueffert
* InvKin engine and parameters separated
*
* Revision 1.2  2004/01/02 13:37:26  roefer
* Handle if a single individual was drawn too often
*
* Revision 1.1  2003/12/29 15:48:54  roefer
* Bremen Byters evo walking added
*
*/

---