Population.h

Go to the documentation of this file.

//
// $Id: Population.h,v 1.3 2004/11/29 14:37:10 min Exp min $
//

#ifndef __Population_h
#define __Population_h

#include <iostream>
#include <vector>
#include <assert.h>
#include "Indiv.h"
#include "MyRandom.h"

using namespace std;

// change to '#define EVODEBUG(x) x' to get runtime debugging info for this class
#define EVODEBUG(x)





template<class ParTraits>
class Population
{

public:

  Population();
  ~Population();

  void init(vector<double>& parameter_ranges);

  void add_indiv(Indiv *indiv_p);
  
  int get_size() { return indivs.size(); }

  void select_parents();
  void shuffle();

  void recombine();
  
  void make_children(Indiv *parent1, Indiv *parent2);

  void mutate();
  
  void select_survivors();
  
  int get_best_index() { return best_index; }
  void set_best_index(int new_index) { best_index = new_index; }
  
  inline Indiv * operator[](int index) const { return indivs[index]; }

  
private:

  std::vector<Indiv *> indivs;

  int nr_parameters;

  int best_index;
  
  
};  // Population class



//
// Population class definition
//

template<class ParTraits>
Population<ParTraits>::Population()
{

}  // constructor



template<class ParTraits>
Population<ParTraits>::~Population()
{
  int pop_size = indivs.size();
  for(int i=0; i < pop_size; i++) delete indivs[i];
  
}  // destructor



template<class ParTraits>
void
Population<ParTraits>::init(vector<double>& parameter_ranges)
{
  nr_parameters = parameter_ranges.size() / 2;
  
  if (ParTraits::VERBOSITY) {
    cout << "Population::init, creating " << ParTraits::POPULATION_SIZE << " individuals" << endl;
    cout << "  nr_parameters = " << nr_parameters << endl;
  }
  
  for(int i=0; i < ParTraits::POPULATION_SIZE; i++) {
    Indiv *ind_p = new Indiv(nr_parameters);
    ind_p->init(parameter_ranges);
    add_indiv(ind_p);
  }  // for
  
}  // Population::init



template<class ParTraits>
void
Population<ParTraits>::add_indiv(Indiv *indiv_p)
{
  indivs.push_back(indiv_p);

}  // Population::add_indiv



template<class ParTraits>
void
Population<ParTraits>::make_children(Indiv *parent1, Indiv *parent2)
{
  EVODEBUG(cout << "Population::make_children" << endl);
  
  for(int i=0; i < ParTraits::NR_CHILDREN; i++) {
    Indiv *ind_p = new Indiv(nr_parameters);
    add_indiv(ind_p);

    //
    // do the recombination here!
    //
    ind_p->recombine(parent1, parent2);
    
  }  // for

}  // Population::make_children



template<class ParTraits>
void
Population<ParTraits>::mutate()
{
  //  cout << "Population::mutate" << endl;
  for(unsigned int i=0; i < indivs.size(); i++) {
    indivs[i]->mutate(i == 0);
  }
  
}  // Population::mutate




template<class ParTraits>
void
Population<ParTraits>::select_survivors()
{
  EVODEBUG(cout << "Population::select_survivors" << endl);

  int pop_size = indivs.size();
  int *keep = new int[pop_size];
  for(int i=0; i < pop_size; i++) keep[i] = 0;
  
  // mu + lambda rule, find the mu best ones and keep those
  for(int i=0; i < ParTraits::POPULATION_SIZE; i++) {
    double best_fitness = 1e6;
    int cur_best_index = -1;
    for(int j=0; j < pop_size; j++) {
      double fitness = indivs[j]->get_fitness();
      if ((fitness < best_fitness) && !keep[j]) {
        best_fitness = fitness;
        cur_best_index = j;
      }
    }  // for
    keep[cur_best_index] = 1;
    if (i == 0) best_index = cur_best_index;  // keep overall best index
    
  }  // for

  int nr_removed = 0;
  int index = 0;
  for(int i=0; i < pop_size; i++) {
    if (keep[i]) {
      // swap them so they'll get properly deleted below
      Indiv *ind_p = indivs[index];
      indivs[index] = indivs[i];
      indivs[i] = ind_p;
      
      if (i == best_index) best_index = index;  // !!!
      index++;
    }
    else
      nr_removed++;
    
  }  // for

  delete[] keep;
  
  int new_size = ParTraits::POPULATION_SIZE;
  for(int i = new_size; i < pop_size; i++) delete indivs[i];
  indivs.erase(indivs.begin() + new_size, indivs.end());
  
  EVODEBUG(cout << "done, removed " << nr_removed << " individuals, population size now " << indivs.size() << endl);
  
}  // Population::select_survivors



template<class ParTraits>
void
Population<ParTraits>::select_parents()
{
  int pop_size = indivs.size();
  EVODEBUG(cout << "Population::select_parents, population size is " << pop_size << endl);
  for(int i=0; i < pop_size; i++) indivs[i]->set_parent(0);
  
  int nr_desired_parents = (int)(floor(pop_size * ParTraits::PARENTS_PERCENTAGE / 100.0 + 0.5));
  if ((nr_desired_parents % 2) == 1) {
    // make sure nr_desired_parents is even, and not larger than the population size
    if (nr_desired_parents < pop_size) nr_desired_parents++;
    else nr_desired_parents--;
  }

  // compute average fitness (used to compute a threshold below)
  double sum = 0;
  for(int i=0; i < pop_size; i++) sum += indivs[i]->get_fitness();
  double avg = sum / pop_size;
  //  cout << "  average fitness: " << avg << endl;

  int nr_selected = 0;

  // nr passes through the main while loop, used for the acceptance threshold below
  int nr_passes = 0;  
  while((nr_selected < nr_desired_parents) && (nr_passes < ParTraits::MAX_PARENT_SELECTION_PASSES)) {

    // first compute a random permutation of all parents
    int *candidates = new int[pop_size];
    for(int i=0; i < pop_size; i++) candidates[i] = i;
    for(int i=0; i < pop_size; i++) {
      int rand_index = rand() % pop_size;
      int temp = candidates[rand_index];
      candidates[rand_index] = candidates[i];
      candidates[i] = temp;
    }  // for

    // now try them all and pick each as parent depending on their fitness level

    for(int i=0; i < pop_size; i++) {
      if (!indivs[i]->is_parent()) {
        double value = indivs[i]->get_fitness();
        // threshold should now also depend on main loop index
        double threshold = value / (2 * avg);
        double random = MyRandom::uniform(0, 1) * (nr_passes + 1);
        if (random > threshold) {
          indivs[i]->set_parent(1);
          nr_selected++;
        }
      }  // if not parent yet
    }  // for each individual

    nr_passes++;  // increases the likelihood that a parent will be picked
    
  }  // while, still need to selected parents

  EVODEBUG(cout << "Population::select_parents: selected " << nr_desired_parents << " parents" << endl);

}  // Population::select_parents



template<class ParTraits>
void
Population<ParTraits>::shuffle()
{
  //  cout << "Population::shuffle" << endl;

  int pop_size = indivs.size();
  int nr_remaining = pop_size;
  for(int i=0; i < pop_size; i++) {
    int rand_index = rand() % nr_remaining + i;
    assert((rand_index >= 0) && (rand_index < pop_size));
    
    Indiv *temp_p = indivs[i];
    indivs[i] = indivs[rand_index];
    indivs[rand_index] = temp_p;

    nr_remaining--;
  }  // for
  
}  // Population::shuffle



template<class ParTraits>
void
Population<ParTraits>::recombine()
{
  //  cout << "Population::recombine" << endl;

  int p[2];
  int nr_parents = 0;
  
  int pop_size = indivs.size();
  for(int i=0; i < pop_size; i += 2) {

    if (indivs[i]->is_parent()) {
      p[nr_parents] = i;
      nr_parents++;
      // make children as soon as we find two parents
      if (nr_parents == 2) {
        make_children(indivs[p[0]], indivs[p[1]]);
        nr_parents = 0;
      }
    }  // if individual is a parent

  }  // for
  
}  // Population::recombine



#endif

---