New SimpleGA with nElite

[Neal Richter]

Hello,

	I wrote a new class that is a modification of SimpleGA to use
elitism > 1.

Like SteadyState it contains methods nElitism(..) & pElitism(..)

The existing ga.elitist(gaTrue) still works, setting nElite = 1.

Calls to pElitism() set nElite to the rounded percentage value of
population size.

Note:  The step() method is altered from SimpleGA to:

1.)  'add' the highest nElite weight members of the oldPop to the 'new'
pop
2.)  call pop->evaluate
3.)  pop->destroy the lowest nElite from the new 'pop'

This new class is useful where the objective function evaluates
individuals based on a random sample of the possible inputs, ie. it is
better to retest elite individuals in each generation.  Please note that
in the random sample objective functions you may want to average
the old value of an individual (if available) with the new round of
testing.

If your objective function FULLY tests each individual, then I would
suggest using the SteadyState class with elitism, as it is not necessary
to retest elite individuals... ever.

Note 2:  This new class uses no inheritance from SimpleGA, it's simply a
modified copy of the SimpleGA source.

Please look it over and give me feedback.  I'd be happy to change it into
a class inherited from SimpleGA and submit it for inclusion in the library
if anyone finds it usefull.

Thanks

Neal Richter
Ph.D. Candidate, Computer Science, Montana State University
-------------- next part --------------
// $Header: /nfs/dsi/cvs/galib/ga/GASimpleEliteGA.C,v 1.1.1.1 1999/11/11 18:56:03 mbwall Exp $
/* ----------------------------------------------------------------------------
  gasimple.C
  mbwall 28jul94
  Copyright (c) 1995 Massachusetts Institute of Technology
                     all rights reserved

  Source file for the simple genetic algorithm object 

  Oct 2001  Neal Richter richter at cs.montana.edu
  Added nElitism & pElitism!  See step for details on how its done.
---------------------------------------------------------------------------- */
#include <ga/garandom.h>

#include "GASimpleEliteGA.h"

#define USE_PELITE 0
#define USE_NELITE 1


GAParameterList&
GASimpleEliteGA::registerDefaultParameters(GAParameterList& p) {
  GAGeneticAlgorithm::registerDefaultParameters(p);

  p.add(gaNelitism, gaSNelitism,
	GAParameter::BOOLEAN, &gaDefElitism);

  return p;
}

GASimpleEliteGA::GASimpleEliteGA(const GAGenome& c) : GAGeneticAlgorithm(c){
  oldPop = pop->clone();

  el = gaTrue;
  params.add(gaNelitism, gaSNelitism, GAParameter::BOOLEAN, &el);
}
GASimpleEliteGA::GASimpleEliteGA(const GAPopulation& p) : GAGeneticAlgorithm(p){
  oldPop = pop->clone();

  el = gaTrue;
  params.add(gaNelitism, gaSNelitism, GAParameter::BOOLEAN, &el);
}
GASimpleEliteGA::GASimpleEliteGA(const GASimpleEliteGA& ga) : GAGeneticAlgorithm(ga){
  oldPop = (GAPopulation *)0;
  copy(ga);
}
GASimpleEliteGA::~GASimpleEliteGA(){
  delete oldPop;
}
GASimpleEliteGA&
GASimpleEliteGA::operator=(const GASimpleEliteGA& ga){
  if(&ga != this) copy(ga); 
  return *this;
}
void 
GASimpleEliteGA::copy(const GAGeneticAlgorithm & g){
  GAGeneticAlgorithm::copy(g);
  const GASimpleEliteGA& ga = DYN_CAST(const GASimpleEliteGA&,g);
  el = ga.el;
  if(oldPop) oldPop->copy(*(ga.oldPop));
  else oldPop = ga.oldPop->clone();
  oldPop->geneticAlgorithm(*this);
}


int
GASimpleEliteGA::setptr(const char* name, const void* value){
  int status = GAGeneticAlgorithm::setptr(name, value);

  if(strcmp(name, gaNelitism) == 0 ||
     strcmp(name, gaSNelitism) == 0){
    el = (*((int*)value) != 0 ? gaTrue : gaFalse);
    status = 0;
  }
  return status;
}

int
GASimpleEliteGA::get(const char* name, void* value) const {
  int status = GAGeneticAlgorithm::get(name, value);

  if(strcmp(name, gaNelitism) == 0 || 
     strcmp(name, gaSNelitism) == 0){
    *((int*)value) = (el == gaTrue ? 1 : 0);
    status = 0;
  }
  return status;
}

void 
GASimpleEliteGA::objectiveFunction(GAGenome::Evaluator f){
  GAGeneticAlgorithm::objectiveFunction(f);
  for(int i=0; i<pop->size(); i++)
    oldPop->individual(i).evaluator(f);
}

void 
GASimpleEliteGA::objectiveData(const GAEvalData& v){
  GAGeneticAlgorithm::objectiveData(v);
  for(int i=0; i<pop->size(); i++)
    pop->individual(i).evalData(v);
}

const GAPopulation&
GASimpleEliteGA::population(const GAPopulation& p) {
  if(p.size() < 1) {
    GAErr(GA_LOC, className(), "population", gaErrNoIndividuals);
    return *pop;
  }

  GAGeneticAlgorithm::population(p);
  oldPop->copy(*pop->clone());
  oldPop->geneticAlgorithm(*this);

  return *pop;
}

int 
GASimpleEliteGA::populationSize(unsigned int n) {
  GAGeneticAlgorithm::populationSize(n);
  oldPop->size(n);
  return n;
}

// If we get a value of 0 for either of these, this means to use the other
// measure instead.
float
GASimpleEliteGA::pElitism(float value){
  if(value == pElite) return pElite;
  if(value <= 0 || value > 1)
  {
    GAErr(GA_LOC, className(), "pElite", gaErrBadPRepl);
    params.set(gaNpElite, pElite);	// force it back
    return pElite;
  }

  params.set(gaNpElite, (double)value);
  pElite = value;

  int temp_nElite = (int)((value*(float)pop->size()) + 0.5);

  nElite = (unsigned int)((temp_nElite < 1) ? 1 : temp_nElite);

  params.set(gaNpElite, (unsigned int)nElite);
  
  which = USE_PELITE;

  elitist(gaTrue);

  return pElite;
}

int
GASimpleEliteGA::nElitism(unsigned int value){
  if(value == nElite) return nElite;
  if(value == 0 || value > (unsigned int)(pop->size())){
    GAErr(GA_LOC, className(), "nElite", gaErrBadNRepl);
    params.set(gaNnElite, nElite);	// force it back
    return nElite;
  }

  params.set(gaNnElite, (unsigned int)value);
  nElite = value;
    
  pElite = (float)nElite / (float)pop->size();
  params.set(gaNpElite, (double)pElite);
    
  which = USE_NELITE;

  elitist(gaTrue);
  
  return nElite;
}

GABoolean 
GASimpleEliteGA::elitist(GABoolean flag)
{
    params.set(gaNelitism, (int)flag); 

    if(nElite == 0)
       nElite = 1;
    //else its has already been set!
    
    return el=flag;
}


int 
GASimpleEliteGA::minimaxi(int m) { 
  GAGeneticAlgorithm::minimaxi(m);
  if(m == MINIMIZE)
    oldPop->order(GAPopulation::LOW_IS_BEST);
  else
    oldPop->order(GAPopulation::HIGH_IS_BEST);
  return minmax;
}


// Initialize the population, set the random seed as needed, do a few stupidity
// checks, reset the stats.  We must initialize the old pop because there is no
// guarantee that each individual will get initialized during the course of our
// operator++ operations.  We do not evaluate the old pop because that will 
// happen as-needed later on.
void
GASimpleEliteGA::initialize(unsigned int seed)
{
  GARandomSeed(seed);

  pop->initialize();
  pop->evaluate(gaTrue);	// the old pop will get it when the pops switch
//  oldPop->initialize();

  stats.reset(*pop);

  if(!scross) 
    GAErr(GA_LOC, className(), "initialize", gaErrNoSexualMating);
}


//   Evolve a new generation of genomes.  When we start this routine, pop
// contains the current generation.  When we finish, pop contains the new 
// generation and oldPop contains the (no longer) current generation.  The 
// previous old generation is lost.  We don't deallocate any memory, we just
// reset the contents of the genomes.
//   The selection routine must return a pointer to a genome from the old
// population.
void
GASimpleEliteGA::step()
{
  int i, mut, c1, c2;
  int pop_size;
  GAGenome *mom, *dad;          // tmp holders for selected genomes

  GAPopulation *tmppop;		// Swap the old population with the new pop.
  tmppop = oldPop;		// When we finish the ++ we want the newly 
  oldPop = pop;			// generated population to be current (for
  pop = tmppop;			// references to it from member functions).

// Generate the individuals in the temporary population from individuals in 
// the main population.

  for(i=0; i<pop->size()-1; i+=2){	// takes care of odd population
    mom = &(oldPop->select());  
    dad = &(oldPop->select());
    stats.numsel += 2;		// keep track of number of selections

    c1 = c2 = 0;
    if(GAFlipCoin(pCrossover())){
      stats.numcro += (*scross)(*mom, *dad,
				&pop->individual(i), &pop->individual(i+1));
      c1 = c2 = 1;
    }
    else{
      pop->individual( i ).copy(*mom);
      pop->individual(i+1).copy(*dad);
    }
    stats.nummut += (mut = pop->individual( i ).mutate(pMutation()));
    if(mut > 0) c1 = 1;
    stats.nummut += (mut = pop->individual(i+1).mutate(pMutation()));
    if(mut > 0) c2 = 1;

    stats.numeval += c1 + c2;
  }
  if(pop->size() % 2 != 0){	// do the remaining population member
    mom = &(oldPop->select());  
    dad = &(oldPop->select());
    stats.numsel += 2;		// keep track of number of selections

    c1 = 0;
    if(GAFlipCoin(pCrossover())){
      stats.numcro += (*scross)(*mom, *dad, &pop->individual(i), (GAGenome*)0);
      c1 = 1;
    }
    else{
      if(GARandomBit())
	pop->individual( i ).copy(*mom);
      else
	pop->individual( i ).copy(*dad);
    }
    stats.nummut += (mut = pop->individual( i ).mutate(pMutation()));
    if(mut > 0) c1 = 1;

    stats.numeval += c1;
  }


// If we are supposed to be elitist, carry the best m individuals from the old
// population into the current population.
// Procedure is exactly the same if we are MAXIMIZE or MINIMIZE!
// 0th individual is always the 'best' and size()-1 is always the 'worst'
  
  //store original pop_size (new population)
  pop_size = pop->size();

  //sort here, won't be done if it isn't needed!
  oldPop->sort();
  pop->sort();
  
  if (nElite > 0)
  {
        //This add method clones individuals,, they must be freed when removed!
        for( i = 0; i < nElite; i++)
        {

          pop->add(oldPop->individual( i ));
                
        }

        //cout << "New Size: " << pop->size() << " Org Size: " << pop_size << endl;

        // get info about current pop for next time
        pop->evaluate(gaTrue);	
        pop->sort();
            
        //now remove the n_added lowest score individuals to maintain org size
        for (i = 0; i < nElite; i++)
        {
            //cout << "Destroying Worst Score Individual: " << pop->individual(pop->size()-1).score() << endl;
            pop->destroy(GAPopulation::WORST);
        }


        //cout << "Destroyed: " << i << " Worst Individuals" << endl;
        //cout << "New Size: " << pop->size() << " Org Size: " << pop_size << endl;

  }
  else  // Elitism disabled.. so eval the new population!
  {
      pop->evaluate(gaTrue);	
  }


  stats.numrep += pop->size();
  stats.update(*pop);		// update the statistics by one generation
  
}
-------------- next part --------------
// $Header: /nfs/dsi/cvs/galib/ga/GASimpleEliteGA.h,v 1.1.1.1 1999/11/11 18:56:03 mbwall Exp $
/* ----------------------------------------------------------------------------
  gasimple.h
  mbwall 28jul94
  Copyright (c) 1995 Massachusetts Institute of Technology
                     all rights reserved

  Header file for the simple genetic algorithm class.
  Oct 2001  Neal Richter richter at cs.montana.edu
    Added nElitism & pElitism!  See step for details on how its done.
---------------------------------------------------------------------------- */

#ifndef _ga_gasimple_h_
#define _ga_gasimple_h_

#include <ga/GABaseGA.h>
#define gaNpElite          "elite_percentage"
#define gaSNpElite         "pelite"
#define gaNnElite          "elite_number"
#define gaSNnElite         "nelite"


class GASimpleEliteGA : public GAGeneticAlgorithm {
public:
  GADefineIdentity("GASimpleEliteGA", GAID::SimpleGA);

  static GAParameterList& registerDefaultParameters(GAParameterList&);

public:
  GASimpleEliteGA(const GAGenome&);
  GASimpleEliteGA(const GAPopulation&);
  GASimpleEliteGA(const GASimpleEliteGA&);
  GASimpleEliteGA& operator=(const GASimpleEliteGA&);
  virtual ~GASimpleEliteGA();
  virtual void copy(const GAGeneticAlgorithm&);

  virtual void initialize(unsigned int seed=0);
  virtual void step();
  GASimpleEliteGA & operator++() { step(); return *this; }

  virtual int setptr(const char* name, const void* value);
  virtual int get(const char* name, void* value) const;

  //INGNORED!
  GABoolean elitist() const {return el;}
  GABoolean elitist(GABoolean);

  virtual int minimaxi() const {return minmax;}
  virtual int minimaxi(int m);

  virtual const GAPopulation& population() const {return *pop;}
  virtual const GAPopulation& population(const GAPopulation&);
  virtual int populationSize() const {return pop->size();}
  virtual int populationSize(unsigned int n);
  virtual GAScalingScheme& scaling() const {return pop->scaling();}
  virtual GAScalingScheme& scaling(const GAScalingScheme & s)
    {oldPop->scaling(s); return GAGeneticAlgorithm::scaling(s);}
  virtual GASelectionScheme& selector() const {return pop->selector(); }
  virtual GASelectionScheme& selector(const GASelectionScheme& s)
    {oldPop->selector(s); return GAGeneticAlgorithm::selector(s);}
  virtual void objectiveFunction(GAGenome::Evaluator f);
  virtual void objectiveData(const GAEvalData& v);

  float pElitism() const { return pElite; }
  float pElitism(float p);
  int nElitism() const { return nElite; }
  int nElitism(unsigned int n);


  
protected:
  GAPopulation *oldPop;		// current and old populations
  GABoolean el;			// are we elitist?  INGNORED!
  float pElite;			// percentage of population to replace each gen
  unsigned int nElite;		// how many of each population to replace
  short which;			// 0 if prepl, 1 if nrepl

};



#ifndef NO_STREAMS
inline ostream& operator<< (ostream& os, GASimpleEliteGA & arg)
{ arg.write(os); return(os); }
inline istream& operator>> (istream& is, GASimpleEliteGA & arg)
{ arg.read(is); return(is); }
#endif

#endif