extensions.html

麻省理工开发的免费遗传算法类库GAlib,很好用

  GA1DBinaryStringGenome &bro=(GA1DBinaryStringGenome &)b;
  if(sis.length() != bro.length()) return -1;
  float count = 0.0;
  for(int i=sis.length()-1; i>=0; i--)
    count += ((sis.gene(i) == bro.gene(i)) ? 0 : 1);
  return count/sis.length();
}
</pre>












<br>
<br>
<br>
<a name="genome_evaluation">
<br><strong>Genome Evaluation</strong><br></a>
<hr>
The genome evaluator is the objective function for your problem.  It takes a single genome as its argument.  The evaluator returns a number that indicates how good or bad the genome is.  You must cast the generic genome to the genome type that you are using.  If your objective function works with different genome types, then use the genome object's <b>className</b> and/or <b>classID</b> member functions to determine the genome class before you do the casts.
<p>
Here is a simple evaluation function for a real number genome with a single element.  The function tries to maximize a sinusoidal.
</p>

<pre>
float
Objective(GAGenome&amp; g){
  GARealGenome&amp; genome = (GARealGenome &amp;)g;
  return 1 + sin(genome.gene(0)*2*M_PI);
}
</pre>













<br>
<br>
<br>
<a name="pop_initialization">
<br><strong>Population Initialization</strong><br></a>
<hr>
This method is invoked when the population is initialized.
<p>
Here is an implemenation that invokes the initializer for each genome in the population.
</p>

<pre>
void 
PopInitializer(GAPopulation &amp; p){
  for(int i=0; i&lt;p.size(); i++)
    p.individual(i).initialize();
}
</pre>












<br>
<br>
<br>
<a name="pop_evaluation">
<br><strong>Population Evaluation</strong><br></a>
<hr>
This method is invoked when the population is evaluated.  If your objective is population-based, you can use this method to set the score for each genome rather than invoking an evaluator for each genome.
<p>
Here is an implementation that invokes the evaluation method for each genome in the population.
</p>

<pre>
void 
PopEvaluator(GAPopulation &amp; p){
  for(int i=0; i&lt;p.size(); i++)
    p.individual(i).evaluate();
}
</pre>














<br>
<br>
<br>
<a name="pop_scaling">
<br><strong>Scaling Scheme</strong><br></a>
<hr>
The scaling object does the transformation from raw (objective) scores to scaled (fitness) scores.  The most important member function you will have to define for a new scaling object is the <b>evaluate</b> member function.  This function calculates the fitness scores based on the objective scores in the population that is passed to it.
<p>
The GAScalingScheme class is a pure virtual (abstract) class and cannot be instantiated.  To make your derived class non-virtual, you <i>must</i> define the <b>clone</b> and <b>evaluate</b> functions.  You should also define the <b>copy</b> method if your derived class introduces any additional data members that require non-trivial copy.
</p>
<p>
The scaling class is polymorphic, so you should define the object's identity using the GADefineIdentity macro.  This macro sets a class ID number and the name that will be used in error messages for the class.  You can use any number above 200 for the ID, but be sure to use a different number for each of your objects.
</p>
<p>
Here is an implementation of sigma truncation scaling.
</p>
<pre>
class SigmaTruncationScaling : public GAScalingScheme {
public:
  GADefineIdentity("SigmaTruncationScaling", 286);

  SigmaTruncationScaling(float m=gaDefSigmaTruncationMultiplier) : c(m) {}
  SigmaTruncationScaling(const SigmaTruncationScaling &amp; arg){copy(arg);}
  SigmaTruncationScaling &amp; operator=(const GAScalingScheme &amp; arg)
    { copy(arg); return *this; }
  virtual ~SigmaTruncationScaling() {}
  virtual GAScalingScheme * clone() const 
    { return new SigmaTruncationScaling(*this); }
  virtual void evaluate(const GAPopulation &amp; p);
  virtual void copy(const GAScalingScheme &amp; arg){
    if(&amp;arg != this &amp;&amp; sameClass(arg)){
      GAScalingScheme::copy(arg);
      c=((SigmaTruncationScaling&amp;)arg).c;
    }
  }
  float multiplier(float fm) { return c=fm; }
  float multiplier() const { return c; }
protected:
  float c;			// std deviation multiplier
};


void 
SigmaTruncationScaling::evaluate(const GAPopulation &amp; p) {
  float f;
  for(int i=0; i&lt;p.size(); i++){
    f = p.individual(i).score() - p.ave() + c * p.dev();
    if(f &lt; 0) f = 0;
    p.individual(i).fitness(f);
  }
}
</pre>













<br>
<br>
<br>
<a name="pop_selection">
<br><strong>Selection Scheme</strong><br></a>
<hr>
The selection object is used to pick individuals from the population.  Before a selection occurs, the <b>update</b> method is called.  You can use this method to do any pre-selection data transformations for your selection scheme.  When a selection is requested, the <b>select</b> method is called.  The <b>select</b> method should return a reference to a single individual from the population.
<p>
A selector may make its selections based either on the scaled (fitness) scores or on the raw (objective) scores of the individuals in the population.  Note also that a population may be sorted either low-to-high or high-to-low, depending on which sort order was chosen.  Your selector should be able to handle either order (this way it will work with genetic algorithms that maximize or minimize).
</p>
<p>
The selection scheme class is polymorphic, so you should define the object's identity using the GADefineIdentity macro.  This macro sets a class ID number and the name that will be used in error messages for the class.  You can use any number above 200 for the ID, but be sure to use a different number for each of your objects.
</p>
<p>
Here is an implementation of a tournament selector.  It is based on the roulette wheel selector and shares some of the roulette wheel selector's functionality.  In particular, this tournament selector uses the roulette wheel selector's <b>update</b> method, so it does not define its own.  The <b>select</b> method does two fitness-proportionate selections then returns the individual with better score.
</p>
<pre>
class TournamentSelector : public GARouletteWheelSelector {
public:
  GADefineIdentity("TournamentSelector", 255);

  TournamentSelector(int w=GASelectionScheme::FITNESS) : 
  GARouletteWheelSelector(w) {}
  TournamentSelector(const TournamentSelector&amp; orig) { copy(orig); }
  TournamentSelector&amp; operator=(const GASelectionScheme&amp; orig) 
    { if(&amp;orig != this) copy(orig); return *this; }
  virtual ~TournamentSelector() {}
  virtual GASelectionScheme* clone() const
    { return new TournamentSelector; }
  virtual GAGenome&amp; select() const;
};


GAGenome &amp;
TournamentSelector::select() const {
  int picked=0;
  float cutoff;
  int i, upper, lower;

  cutoff = GARandomFloat();
  lower = 0; upper = pop-&gt;size()-1;
  while(upper &gt;= lower){
    i = lower + (upper-lower)/2;
    if(psum[i] &gt; cutoff)
      upper = i-1;
    else
      lower = i+1;
  }
  lower = Min(pop-&gt;size()-1, lower);
  lower = Max(0, lower);
  picked = lower;

  cutoff = GARandomFloat();
  lower = 0; upper = pop-&gt;size()-1;
  while(upper &gt;= lower){
    i = lower + (upper-lower)/2;
    if(psum[i] &gt; cutoff)
      upper = i-1;
    else
      lower = i+1;
  }
  lower = Min(pop-&gt;size()-1, lower);
  lower = Max(0, lower);

  GAPopulation::SortBasis basis = 
    (which == FITNESS ? GAPopulation::SCALED : GAPopulation::RAW);
  if(pop-&gt;order() == GAPopulation::LOW_IS_BEST){
    if(pop-&gt;individual(lower,basis).score() &lt;
       pop-&gt;individual(picked,basis).score())
      picked = lower;
  }
  else{
    if(pop-&gt;individual(lower,basis).score() &gt;
       pop-&gt;individual(picked,basis).score())
      picked = lower;
  }

  return pop-&gt;individual(picked,basis);
}
</pre>













<br>
<br>
<br>
<a name="ga">
<br><strong>Genetic Algorithm</strong><br></a>
<hr>
Here is a sample derived class that does restricted mating.  In this example, one of the parents is selected as usual.  The second individual is select as the first, but it is used only if it is similar to the first individual.  If not, we make another selection.  If enough selections fail, we take what we can get.

<pre>
class RestrictedMatingGA : public GASteadyStateGA {
public:
  GADefineIdentity("RestrictedMatingGA", 288);
  RestrictedMatingGA(const GAGenome&amp; g) : GASteadyStateGA(g) {}
  virtual ~RestrictedMatingGA() {}
  virtual void step();
  RestrictedMatingGA &amp; operator++() { step(); return *this; }
};

void
RestrictedMatingGA::step()
{ 
  int i, k;
  for(i=0; i&lt;tmpPop-&gt;size()-; i++){
    mom = &amp;(pop-&gt;select()); 
    k=0;
    do { k++; dad = &amp;(pop-&gt;select()); }
    while(mom-&gt;compare(*dad) &lt; THRESHOLD &amp;&amp; k&lt;pop-&gt;size());
    stats.numsel += 2;
    if(GAFlipCoin(pCrossover()))
      stats.numcro += (*scross)(*mom, *dad, &amp;tmpPop-&gt;individual(i), 0);
    else
      tmpPop-&gt;individual(i).copy(*mom);
    stats.nummut += tmpPop-&gt;individual(i).mutate(pMutation());
  }

  for(i=0; i&lt;tmpPop-&gt;size(); i++)
    pop-&gt;add(tmpPop-&gt;individual(i));

  pop-&gt;evaluate();		// get info about current pop for next time
  pop-&gt;scale();			// remind the population to do its scaling

  for(i=0; i&lt;tmpPop-&gt;size(); i++)
    pop-&gt;destroy(GAPopulation::WORST, GAPopulation::SCALED);

  stats.update(*pop);		// update the statistics by one generation
}
</pre>



















<br>
<br>
<br>
<a name="termination">
<br><strong>Termination Function</strong><br></a>
<hr>
The termination function determines when the genetic algorithm should stop evolving.  It takes a genetic algorithm as its argument and returns gaTrue if the genetic algorithm should stop or gaFalse if the algorithm should continue.
<p>
Here are three examples of termination functions.  The first compares the current generation to the desired number of generations.  If the current generation is less than the desired number of generations, it returns gaFalse to signify that the GA is not yet complete.
</p>
<pre>
GABoolean
GATerminateUponGeneration(GAGeneticAlgorithm &amp; ga){
  return(ga.generation() &lt; ga.nGenerations() ? gaFalse : gaTrue);
}
</pre>
The second example compares the average score in the current population with the score of the best individual in the current population.  If the ratio of these exceeds a specified threshhold, it returns gaTrue to signify that the GA should stop.  Basically this means that the entire population has converged to a 'good' score.
<pre>
const float desiredRatio = 0.95;    // stop when pop average is 95% of best

GABoolean
GATerminateUponScoreConvergence(GAGeneticAlgorithm &amp; ga){
  if(ga.statistics().current(GAStatistics::Mean) /
     ga.statistics().current(GAStatistics::Maximum) &gt; desiredRatio)
    return gaTrue;
  else
    return gaFalse;
}
</pre>
The third uses the population diversity as the criterion for stopping.  If the diversity drops below a specified threshhold, the genetic algorithm will stop.
<pre>
const float thresh = 0.01;     // stop when population diversity is below this

GABoolean
StopWhenNoDiversity(GAGeneticAlgorithm &amp; ga){
  if(ga.statistics().current(GAStatistics::Diversity) &lt; thresh)
    return gaTrue;
  else
    return gaFalse;
}
</pre>
A faster method of doing a nearly equivalent termination is to use the population's standard deviation as the stopping criterion (this method does not require comparisons of each individual).  Notice that this judges diversity based upon the genome scores rather than their actual genetic diversity.
<pre>
const float thresh = 0.01;     // stop when population deviation is below this

GABoolean
StopWhenNoDeviation(GAGeneticAlgorithm &amp; ga){
  if(ga.statistics().current(GAStatistics::Deviation) &lt; thresh)
    return gaTrue;
  else
    return gaFalse;
}
</pre>










<hr>
<small><i>Matthew Wall, 23 March 1996</i></small>

</body></html>