EvoFunc.h

Go to the documentation of this file.

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

#ifndef __EVOFUNC_H
#define __EVOFUNC_H

#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>
#include "map_functions/Map.h"
#include "Population.h"

using namespace std;

// allows you to have a "EvoView" class which has access to EvoFunc's members (see below)
class EvoView;  





template<class Traits, class ParTraits>
class EvoFunc
{

public:

  typedef typename Traits::SourceType SourceType;
  typedef typename Traits::TransformedSourceType TransformedSourceType;
  typedef typename Traits::TargetType TargetType;

  typedef typename Traits::MapType MapType;
  typedef typename Traits::ErrorType ErrorType;

  
  EvoFunc(SourceType& source, TargetType& target, const Traits& evo_traits);
  EvoFunc(SourceType& source, TransformedSourceType& transformed_source, TargetType& target, const Traits& evo_traits);
  ~EvoFunc() { delete pop_p; }

  void init();

  Population<ParTraits> *get_pop_p() { return pop_p; }
  
  void run(int max_nr_iterations = ParTraits::MAX_ITERATIONS);
  void run_2d_grid(int index[2], vector<vector<double> >& fitness_matrix);
  void run_1d_array(int index, vector<double>& fitness_array);

  double evaluate();
  double evaluate_individual(Indiv& ind);
  Indiv *get_best_indiv() { return (*pop_p)[pop_p->get_best_index()]; }
  int get_nr_iterations() { return current_iteration; }

  friend class EvoView;

  
private:

  SourceType& source;
  TransformedSourceType& transformed_source;
  TargetType& target;
  const Traits& evo_traits;

  MapType& map;      // to prevent calling of copy constructor
  ErrorType& error;
  
  Population<ParTraits> *pop_p;

  
  int check_terminate(double best_fitness);
  double prev_fitness;
  // after this number of steps we compute the average delta, and compare to TERMINATION_FITNESS_EPSILON
  static const int DELTA_WINDOW_SIZE = 5;
  double fitness_deltas[DELTA_WINDOW_SIZE];
  int current_iteration;

  static const int GRID_NR_STEPS = 50;
  static const int ARRAY_NR_STEPS = 50;

  
};  // EvoFunc class



//
// class definition
//

template<class Traits, class ParTraits>
EvoFunc<Traits, ParTraits>::EvoFunc(SourceType& source_ref, TransformedSourceType& transformed_source_ref,
                                    TargetType& target_ref, const Traits& evo_traits_ref) :
  source(source_ref),
  transformed_source(transformed_source_ref),
  target(target_ref),
  evo_traits(evo_traits_ref),
  map(evo_traits.map_object()),
  error(evo_traits.error_object())
{
  pop_p = 0;
  init();
  
}  // constructor



template<class Traits, class ParTraits>
EvoFunc<Traits, ParTraits>::EvoFunc(SourceType& source_ref, TargetType& target_ref, const Traits& evo_traits_ref) :
  source(source_ref),
  transformed_source(target_ref),
  target(target_ref),
  evo_traits(evo_traits_ref),
  map(evo_traits.map_object()),
  error(evo_traits.error_object())
{
  pop_p = 0;
  init();

}  // constructor with type of transformed source equal to type of target (old default)



template<class Traits, class ParTraits>         
void
EvoFunc<Traits, ParTraits>::init()
{
  if (pop_p) delete pop_p;
  pop_p = new Population<ParTraits>();

  //
  // initialize variables used in check_terminate
  //
  prev_fitness = 1e6;
  current_iteration = 0;
  
  // map constructor now already should have initialized ranges
  vector<double>& par_ranges = map.get_parameter_ranges();
  pop_p->init(par_ranges);

}  // EvoFunc::init

  

template<class Traits, class ParTraits>         
void
EvoFunc<Traits, ParTraits>::run(int max_nr_iterations)
{
  // init
  int t = 0;
  
  // call obj_func and see if we're done
  double best_fit = evaluate();
  if (check_terminate(best_fit)) return;
  
  int done = 0;
  
  while(!done) {

    //         t := t + 1;       // increase the time counter
    t++;
    current_iteration = t;
    
    //         P' := selectparents P (t);  // select sub-population for offspring production
    pop_p->select_parents();

    // Roland's algorithm randomly re-orders individuals, then each successive pair become parents
    //    pop_p->shuffle();
    
    //         recombine P' (t); // recombine the "genes" of selected parents
    pop_p->recombine();

    //         mutate P' (t);    // perturb the mated population stochastically
    pop_p->mutate();
    
    //         evaluate P' (t);  // evaluate its new fitness
    double best_fit = evaluate();
    
    //         P := survive P,P' (t);  // select the survivors from actual fitness
    pop_p->select_survivors();
    
    done = (t == max_nr_iterations) || check_terminate(best_fit);

    if (ParTraits::VERBOSITY)
      cout << "\rdone with iteration " << t << ", best error = " << best_fit << "        " << flush;
    
  }  // while


}  // EvoFunc::run



template<class Traits, class ParTraits>
double
EvoFunc<Traits, ParTraits>::evaluate()
{
  //  cout << "EvoFunc::evaluate" << endl;
  
  double best_fit = 1e9;
  int nr = pop_p->get_size();
  TransformedSourceType result;

  for(int i=0; i < nr; i++) {

    Indiv *ind_p = (*pop_p)[i];
    map(source, result, ind_p->get_pars());

    double err = error(result, target);
    ind_p->set_fitness(err);
    
    if (err < best_fit) {
      best_fit = err;
      pop_p->set_best_index(i);
    }

  }  // for each individual

  return best_fit;
  
}  // EvoFunc::evaluate



template<class Traits, class ParTraits>
int
EvoFunc<Traits, ParTraits>::check_terminate(double best_fitness)
{
  if (!finite(best_fitness)) {
    cout << "error: fitness value is not finite" << endl;
    return 1;
  }
  
  if (best_fitness < ParTraits::TERMINATION_FITNESS_CUTOFF) {
    if (ParTraits::VERBOSITY)
      cout << "terminating because fitness " << best_fitness << " < " << ParTraits::TERMINATION_FITNESS_CUTOFF << endl;
    return 1;
  }

  double delta = fabs(best_fitness - prev_fitness);
  prev_fitness = best_fitness;

  int delta_index = current_iteration % DELTA_WINDOW_SIZE;
  fitness_deltas[delta_index] = delta;

  if (current_iteration >= DELTA_WINDOW_SIZE) {
    double fitness_delta_sum = 0;
    for(int i=0; i < DELTA_WINDOW_SIZE; i++) fitness_delta_sum += fitness_deltas[i];
    
    double avg_delta = fitness_delta_sum / DELTA_WINDOW_SIZE;
    if (avg_delta < ParTraits::TERMINATION_FITNESS_EPSILON) {
      if (ParTraits::VERBOSITY) {
        cout << "terminating because average difference between consecutive fitness values over " << DELTA_WINDOW_SIZE
             << " steps < " << ParTraits::TERMINATION_FITNESS_EPSILON << endl;
      }
      return 1;
    }
  }  // if we've done at least DELTA_WINDOW_SIZE steps then our window is filled
  
  return 0;
  
}  // EvoAlg::check_terminate



template<class Traits, class ParTraits>
void
EvoFunc<Traits, ParTraits>::run_1d_array(int index, vector<double>& fitness_array)
{
  char output_filespec[80];
  sprintf(output_filespec, "array_%d.dat", index);
  ofstream *out = new ofstream(output_filespec);
  if (ParTraits::VERBOSITY)
    cout << "EvoFunc::run_1d_array, writing to [" << output_filespec << "]" << endl;

  // clear array
  fitness_array.clear();

  vector<double>& par_ranges = map.get_parameter_ranges();
  vector<double>& parameters = map.get_parameters();
  
  double p_start = par_ranges[index * 2];
  double p_end = par_ranges[index * 2 + 1];
  double p_delta = (p_end - p_start) / ARRAY_NR_STEPS;

  if (ParTraits::VERBOSITY)
    cout << "single loop running from " << p_start << " to " << p_end << ", step " << p_delta << endl;

  // use single individual to evaluate fitness function
  int nr_pars = parameters.size();
  Indiv ind(nr_pars);
  // copy parameters
  vector<double>& pars = ind.get_pars();
  for(int i=0; i < nr_pars; i++) pars[i] = parameters[i];

  // start single loop
  TransformedSourceType result;
  for(double p = p_start; p <= p_end; p += p_delta) {
    pars[index] = p;
    
    map(source, result, ind.get_pars());
    double err = error(result, target);
    ind.set_fitness(err);

    *out << p << " " << err << endl;
    fitness_array.push_back(err);
    
  }  // for
  
  out->close();
  delete out;

}  // EvoFunc::run_1d_array



template<class Traits, class ParTraits>
void
EvoFunc<Traits, ParTraits>::run_2d_grid(int index[2], vector<vector<double> >& fitness_matrix)
{
  char output_filespec[80];
  sprintf(output_filespec, "grid_%d%d.dat", index[0], index[1]);
  ofstream *out = new ofstream(output_filespec);
  if (ParTraits::VERBOSITY)
    cout << "EvoFunc::run_2d_grid, writing to [" << output_filespec << "]" << endl;
  
  // clear matrix
  for(unsigned int i=0; i < fitness_matrix.size(); i++) fitness_matrix[i].clear();
  fitness_matrix.clear();
  // fill matrix
  for(int i=0; i <= GRID_NR_STEPS; i++) {
    vector<double> temp;
    fitness_matrix.push_back(temp);
    for(int j=0; j <= GRID_NR_STEPS; j++) {
      fitness_matrix[i].push_back(0);
    }  // for
  }  // for, fill matrix

  vector<double>& par_ranges = map.get_parameter_ranges();
  vector<double>& parameters = map.get_parameters();
  
  // need parameter ranges and step size here
  double p_start[2], p_end[2], p_delta[2];
  for(int i=0; i < 2; i++) {
    p_start[i] = par_ranges[index[i] * 2];
    p_end[i] = par_ranges[index[i] * 2 + 1];
    p_delta[i] = (p_end[i] - p_start[i]) / GRID_NR_STEPS;
    if (ParTraits::VERBOSITY)
      cout << "loop " << i << " running from " << p_start[i] << " to " << p_end[i] << ", step " << p_delta[i] << endl;
  }  // for

  // use single individual to evaluate fitness function
  int nr_pars = parameters.size();
  Indiv ind(nr_pars);
  // copy parameters
  vector<double>& pars = ind.get_pars();
  for(int i=0; i < nr_pars; i++) pars[i] = parameters[i];
  
  // start double loop
  int i1 = 0;
  TransformedSourceType result;
  
  for(double p1 = p_start[0]; p1 <= p_end[0]; p1 += p_delta[0]) {
    pars[index[0]] = p1;

    int i2 = 0;
    for(double p2 = p_start[1]; p2 <= p_end[1]; p2 += p_delta[1]) {
      pars[index[1]] = p2;

      map(source, result, ind.get_pars());
      double err = error(result, target);
      ind.set_fitness(err);

      //      cout << ind << " : " << err << endl;
      *out << p1 << " " << p2 << " " << err << endl;
      fitness_matrix[i1][i2] = err;
      i2++;

    }  // for
    *out << endl;
    i1++;
   
  }  // for

  out->close();
  delete out;
  
}  // EvoFunc::run_2d_grid



template<class Traits, class ParTraits>
double
EvoFunc<Traits, ParTraits>::evaluate_individual(Indiv& ind)
{
  TransformedSourceType result;
  map(source, result, ind.get_pars());
  double err = error(result, target);
  ind.set_fitness(err);
  return err;
  
}  // EvoFunc::evaluate_individual



#endif

---