gapopulation.cpp

遗传算法工具箱C++

// $Header$
/* ----------------------------------------------------------------------------
  population.C
  mbwall 11aug94
  Copyright (c) 1995 Massachusetts Institute of Technology
                     all rights reserved
---------------------------------------------------------------------------- */
#include <string.h>
#include <math.h>
#include "GAPopulation.h"
#include "GASelector.h"
#include "garandom.h"
#include "GABaseGA.h"		// for the sake of flaky g++ compiler

// windows is promiscuous in its use of min/max, and that causes us grief.  so
// turn of the use of min/max macros in this file.   thanks nick wienholt
#if !defined(NOMINMAX)
#define NOMINMAX
#endif

// This is the default population initializer.  It simply calls the initializer
// for each member of the population.  Then we touch the population to tell it
// that it needs to update stats and/or sort (but we don't actually force 
// either one to occur.
//   The population object takes care of setting/unsetting the status flags.
void 
GAPopulation::DefaultInitializer(GAPopulation & p){
  for(int i=0; i<p.size(); i++)
    p.individual(i).initialize();
}

//  The default evaluator simply calls the evaluate member of each genome in
// the population.  The population object takes care of setting/unsetting the 
// status flags for indicating when the population needs to be updated again.
void 
GAPopulation::DefaultEvaluator(GAPopulation & p){
  for(int i=0; i<p.size(); i++)
    p.individual(i).evaluate();
}



#define GA_POP_CHUNKSIZE 10	// allocate chrom ptrs in chunks of this many


/* ----------------------------------------------------------------------------
 Population

  The population class is basically just a holder for the genomes.  We also
keep track of statistics about the fitness of our genomes.  We don't care
what kind of genomes we get.  To create the population we call the clone 
method of the genome we're given.
  By default we do not calculate the population's diversity, so we set the
div matrix to NULL.
---------------------------------------------------------------------------- */
GAPopulation::GAPopulation() {
  csz = N = GA_POP_CHUNKSIZE;
  n = 0;
  while(N < n) N += csz;

  rind = new GAGenome * [N];
  sind = new GAGenome * [N];
  memset(rind, 0, N * sizeof(GAGenome*));
  memset(sind, 0, N * sizeof(GAGenome*));
//  indDiv = new float[N*N];
  indDiv = 0;

  neval = 0;
  rawSum = rawAve = rawDev = rawVar = rawMax = rawMin = 0.0;
  fitSum = fitAve = fitDev = fitVar = fitMax = fitMin = 0.0;
  popDiv = -1.0;
  rsorted = ssorted = evaluated = gaFalse;
  scaled = statted = divved = selectready = gaFalse;
  sortorder = HIGH_IS_BEST;
  init = DefaultInitializer;
  eval = DefaultEvaluator;
  slct = new DEFAULT_SELECTOR;
  slct->assign(*this);
  sclscm = new DEFAULT_SCALING;
  evaldata = (GAEvalData*)0;
  ga = (GAGeneticAlgorithm*)0;
}

GAPopulation::GAPopulation(const GAGenome & c, unsigned int popsize) {
  csz = N = GA_POP_CHUNKSIZE;
  n = (popsize < 1 ? 1 : popsize);
  while(N < n) N += csz;

  rind = new GAGenome * [N];
  sind = new GAGenome * [N];
  for(unsigned int i=0; i<n; i++)
    rind[i] = c.clone(GAGenome::ATTRIBUTES);
  memcpy(sind, rind, N * sizeof(GAGenome*));
//  indDiv = new float[N*N];
  indDiv = 0;

  neval = 0;
  rawSum = rawAve = rawDev = rawVar = rawMax = rawMin = 0.0;
  fitSum = fitAve = fitDev = fitVar = fitMax = fitMin = 0.0;
  popDiv = -1.0;
  rsorted = ssorted = evaluated = gaFalse;
  scaled = statted = divved = selectready = gaFalse;
  sortorder = HIGH_IS_BEST;
  init = DefaultInitializer;
  eval = DefaultEvaluator;
  slct = new DEFAULT_SELECTOR;
  slct->assign(*this);
  sclscm = new DEFAULT_SCALING;
  evaldata = (GAEvalData*)0;
  ga = (GAGeneticAlgorithm*)0;
}

GAPopulation::GAPopulation(const GAPopulation & orig){
  n = N = 0;
  rind = sind = (GAGenome**)0;
  indDiv = (float*)0;
  sclscm = (GAScalingScheme*)0; 
  slct = (GASelectionScheme*)0;
  evaldata = (GAEvalData*)0;
  copy(orig);
}

GAPopulation::~GAPopulation(){
  for(unsigned int i=0; i<n; i++)
    delete rind[i];
  delete [] rind;
  delete [] sind;
  delete [] indDiv;
  delete sclscm;
  delete slct;
  delete evaldata;
}


// Make a complete copy of the original population.  This is a deep copy of 
// the population object - we clone everything in the genomes and copy all of
// the population's information.
void
GAPopulation::copy(const GAPopulation & arg)
{
  unsigned int i;
  for(i=0; i<n; i++)
    delete rind[i];
  delete [] rind;
  delete [] sind;
  delete [] indDiv;
  delete sclscm;
  delete slct;
  delete evaldata;

  csz = arg.csz; N = arg.N; n = arg.n;
  rind = new GAGenome * [N];
  for(i=0; i<n; i++)
    rind[i] = arg.rind[i]->clone();
  sind = new GAGenome * [N];
  memcpy(sind, rind, N * sizeof(GAGenome*));

  if(arg.indDiv) {
    indDiv = new float[N*N];
    memcpy(indDiv, arg.indDiv, (N*N*sizeof(float)));
  }
  else {
    indDiv = 0;
  }

  sclscm = arg.sclscm->clone();
  scaled = gaFalse;
  if(arg.scaled == gaTrue) scale();

  slct = arg.slct->clone();
  slct->assign(*this);
  selectready = gaFalse;
  if(arg.selectready == gaTrue) prepselect();

  if(arg.evaldata) evaldata = arg.evaldata->clone();
  else evaldata = (GAEvalData*)0;

  neval = 0;			// don't copy the evaluation count!
  rawSum = arg.rawSum; rawAve = arg.rawAve; 
  rawMax = arg.rawMax; rawMin = arg.rawMin;
  rawVar = arg.rawVar; rawDev = arg.rawDev;
  popDiv = arg.popDiv;

  fitSum = arg.fitSum; fitAve = arg.fitAve; 
  fitMax = arg.fitMax; fitMin = arg.fitMin;
  fitVar = arg.fitVar; fitDev = arg.fitDev;

  sortorder = arg.sortorder;
  rsorted = arg.rsorted;
  ssorted = gaFalse;		// we must sort at some later point
  statted = arg.statted;
  evaluated = arg.evaluated;
  divved = arg.divved;

  init = arg.init;
  eval = arg.eval;
  ud = arg.ud;
  ga = arg.ga;
}


// Resize the population.  If we shrink, we delete the extra genomes.  If
// we grow, we clone new ones (and we DO NOT initialize them!!!).  When we
// trash the genomes, we delete the worst of the population!  We do not
// free up the space used by the array of pointers, but we do free up the
// space used by the genomes.
//   We do a clone of the genome contents so that we don't have to initialize
// the new ones (what if the population has a custom initilizer?).  We randomly
// pick which ones to clone from the existing individuals.  If the population
// contains no genomes, then we post an error message (since there are no
// individuals from which to clone the new ones).
//   If the population was evaluated, then we evaluate the new genomes.  We
// do not sort nor restat the population, and we tag the statted and sorted
// flags to reflect the fact that they are no longer valid.
//   Resizing to a bigger size is the same as a batch 'add'
int
GAPopulation::size(unsigned int popsize){
  if(popsize == n) return n;
  if(n == 0 && popsize > 0) {
    GAErr(GA_LOC, "GAPopuluation", "size", gaErrNoIndividuals);
    return n;
  }

  if(popsize > n){
    grow(popsize);
    for(unsigned int i=n; i<popsize; i++)
      rind[i] = rind[GARandomInt(0,n-1)]->clone(GAGenome::CONTENTS);
    rsorted = gaFalse;
  }
  else{
    for(unsigned int i=popsize; i<n; i++) // trash the worst ones (if sorted)
      delete rind[i];			  // may not be sorted!!!!
  }

  memcpy(sind, rind, N * sizeof(GAGenome*));
  ssorted = scaled = statted = divved = selectready = gaFalse;
  n = popsize;  

  if(evaluated == gaTrue) evaluate(gaTrue);

  return n;
}


// This is a private method for adjusting the size of the arrays used by the
// population object.  Unlike the size method, this method does not allocate
// more genomes (but it will delete genomes if the specified size is smaller
// than the current size).
//   This maintains the integrity of the diversity scores (but the new ones 
// will not have been set yet).
//   We return the total amount allocated (not the amount used).
int
GAPopulation::grow(unsigned int s) {
  if(s <= N) return N;

  int oldsize = N;
  while(N < s) N += csz;

  GAGenome ** tmp;

  tmp = rind;
  rind = new GAGenome * [N];
  memcpy(rind, tmp, oldsize*sizeof(GAGenome *));
  delete [] tmp;
  tmp = sind;
  sind = new GAGenome * [N];
  memcpy(sind, tmp, oldsize*sizeof(GAGenome *));
  delete [] tmp;

  if(indDiv) {
    float *tmpd = indDiv;
    indDiv = new float[N*N];
    for(int i=0; i<oldsize; i++)
      memcpy(&(indDiv[i*N]), &(tmpd[i*oldsize]), oldsize*sizeof(float));
    delete [] tmpd;
  }

  return N;
}


// Get rid of 'extra' memory that we have allocated.  We just trash the 
// diversity matrix and flag it as being invalid.  Return the amount
// allocated (which is also the amount used).
int
GAPopulation::compact()
{
  if(n == N) return N;

  GAGenome ** tmp;

  tmp = rind;
  rind = new GAGenome * [n];
  memcpy(rind, tmp, n*sizeof(GAGenome *));
  delete [] tmp;
  tmp = sind;
  sind = new GAGenome * [n];
  memcpy(sind, tmp, n*sizeof(GAGenome *));
  delete [] tmp;

//  if(indDiv) {
//    float *tmpd = indDiv;
//    indDiv = new float [n*n];
//    for(unsigned int i=0; i<n; i++)
//      memcpy(&(indDiv[i*n]), &(tmpd[i*N]), n*sizeof(float));
//    delete [] tmpd;
//  }

  if(indDiv) {
    delete [] indDiv;
    indDiv = 0;
  }

  return N = n;
}


GAPopulation::SortOrder
GAPopulation::order(GAPopulation::SortOrder flag) {
  if(sortorder == flag) return flag;
  sortorder = flag;
  rsorted = ssorted = gaFalse;
  return flag; 
}


// Sort using the quicksort method.  The sort order depends on whether a high 
// number means 'best' or a low number means 'best'.  Individual 0 is always
// the 'best' individual, Individual n-1 is always the 'worst'.
//   We may sort either array of individuals - the array sorted by raw scores
// or the array sorted by scaled scores.
void 
GAPopulation::sort(GABoolean flag, SortBasis basis) const {
  GAPopulation * This = (GAPopulation *)this;
  if(basis == RAW){
    if(rsorted == gaFalse || flag == gaTrue){
      if(sortorder == LOW_IS_BEST)
	GAPopulation::QuickSortAscendingRaw(This->rind, 0, n-1);
      else
	GAPopulation::QuickSortDescendingRaw(This->rind, 0, n-1);
      This->selectready = gaFalse;
    }
    This->rsorted = gaTrue;
  }
  else if(basis == SCALED){
    if(ssorted == gaFalse || flag == gaTrue){
      if(sortorder == LOW_IS_BEST)
	GAPopulation::QuickSortAscendingScaled(This->sind, 0, n-1);
      else
	GAPopulation::QuickSortDescendingScaled(This->sind, 0, n-1);
      This->selectready = gaFalse;
    }
    This->ssorted = gaTrue;
  }
}


// Evaluate each member of the population and store basic population statistics
// in the member variables.  It is OK to run this on a const object - it 
// changes to physical state of the population, but not the logical state.
//   The partial sums are normalized to the range [0,1] so that they can be
// used whether the population is sorted as low-is-best or high-is-best.  
// Individual 0 is always the best individual, and the partial sums are
// calculated so that the worst individual has the smallest partial sum.  All
// of the partial sums add to 1.0.
void
GAPopulation::statistics(GABoolean flag) const {
  if(statted == gaTrue && flag != gaTrue) return;
  GAPopulation * This = (GAPopulation *)this;

  if(n > 0) {
    float tmpsum;
    This->rawMin = This->rawMax = tmpsum = rind[0]->score();

    unsigned int i;
    for(i=1; i<n; i++){
      float scr = rind[i]->score();
      tmpsum += scr;
      This->rawMax = GAMax(rawMax, scr);
      This->rawMin = GAMin(rawMin, scr);
    }
    float tmpave = tmpsum / n;
    This->rawAve = tmpave;
    This->rawSum = tmpsum;	// if scores are huge we'll lose data here

    float tmpvar = 0.0;
    if(n > 1){
      for(i=0; i<n; i++){
	float s = rind[i]->score() - This->rawAve;
	s *= s;
	tmpvar += s;
      }
      tmpvar /= (n-1);
    }
    This->rawDev = (float)sqrt(tmpvar);
    This->rawVar = tmpvar;	// could lose data if huge variance
  }
  else {
    This->rawMin = This->rawMax = This->rawSum = 0.0;
    This->rawDev = This->rawVar = 0.0;
  }

  This->statted = gaTrue;
}