gpkernel_1.html

用C++编写的遗传算法

<A NAME="IDX47"></A>
<A NAME="IDX48"></A>

</P>
<P>
A <EM>GPPopulation</EM> object is a container that contains all the
genetic programs of a population.

</P>

<BLOCKQUOTE>

<PRE>
class GPPopulation : public GPContainer
{
public:
  GPPopulation (GPVariables&#38; GPVar_, GPAdfNodeSet&#38; adfNs_) : 
    adfNs(&#38;adfNs_), GPVar(GPVar_) {}
  ...
};
</PRE>

</BLOCKQUOTE>

<P>
The above constructor is usually used to create a new population.  That
does not mean that the genetic programs are created at this point, not
even the container space is reserved.  This is done later when a new
generation is created.  The class needs some configuration variables (a
<EM>GPVariables</EM> object, See section <A HREF="gpkernel_1.html#SEC15">1.8  Configuration Variables</A>) which are
used throughout the member functions of the class, and a container with
the node sets for each genetic tree.  The node sets are saved in the
population object as a reference; that means that the node set objects
must not be destroyed as long as the population exists.

</P>
<P>
<A NAME="IDX49"></A>
<A NAME="IDX50"></A>
<A NAME="IDX51"></A>

</P>

<BLOCKQUOTE>

<PRE>
  virtual void create ();
  virtual GP* createGP (int numOfTrees) { return new GP (numOfTrees); }
  virtual int checkForValidCreation (GP&#38; gpo);
</PRE>

</BLOCKQUOTE>

<P>
The function <EM>create()</EM> reserves space for the genetic programs in
the object's container.  Then it loops through the whole population.  It
creates genetic programs which are still empty by calling the function
<EM>createGP()</EM>, then calls the function <EM>GP::create()</EM>
(See section <A HREF="gpkernel_1.html#SEC13">1.6  The Genetic Program</A>) for each genetic program with the
appropriate parameters to create the trees.

</P>
<P>
Once a genetic program has been created, the function
<EM>checkForValidCreation()</EM> is called to check for a valid genetic
program.  This function can reject any genetic program.  This does not
necessarily lead to an infinite loop.  After a certain amount of trials,
the function <EM>create()</EM> accepts the last one even if
<EM>checkForValidCreation()</EM> returns the value 0 (which means the
genetic program is not valid).  In the current implementation, the
function checks whether the genetic program was already created before,
and rejects those genetic programs to ensure ultimate diversity.  A
rejection is likely to happen when small tree depths, few different
nodes and large populations are used.

</P>
<P>
<A NAME="IDX52"></A>
<A NAME="IDX53"></A>
<A NAME="IDX54"></A>
<A NAME="IDX55"></A>
<A NAME="IDX56"></A>
<A NAME="IDX57"></A>

</P>

<BLOCKQUOTE>

<PRE>
  double totalFitness ();
  long totalLength ();
  long totalDepth ();
  GP* NthGP (int n) { return (GP*) GPContainer::Nth (n); }
  virtual void printOn (ostream&#38; os);
  virtual void createGenerationReport (int printLegend, int generation,
                                       ostream&#38; fout, ostream&#38; bout);
</PRE>

</BLOCKQUOTE>

<P>
The first three routines loop through the complete population and sum
all the appropriate values of the genetic programs together.  They are
used for statistical purposes.  The function <EM>NthGP()</EM> returns the
n-th genetic program of the population.  The function <EM>printOn()</EM>
prints all the genetic programs of the population, and
<EM>createGenerationReport()</EM> reports some statistical parameters
about the population.

</P>
<P>
<A NAME="IDX58"></A>
<A NAME="IDX59"></A>
<A NAME="IDX60"></A>
<A NAME="IDX61"></A>
<A NAME="IDX62"></A>

</P>

<BLOCKQUOTE>

<PRE>
  virtual void generate (GPPopulation&#38; newPop);
  GPContainer* evolution (GPPopulationRange&#38; range);
  virtual void demeticMigration ();
  virtual void calculateStatistics ();
  virtual void evaluate();
</PRE>

</BLOCKQUOTE>

<P>
The function <EM>generate()</EM> builds up a new population by applying
the genetic operators creation, reproduction, selection, crossover and
mutation.  The following actions are taken:

</P>

<OL>
<LI>

It divides the population into demes of equal size (the population must
be divisible by the number of genes), if demes are used, and operates on
each deme the same way it would on the whole population.
<LI>

For each deme, or the whole population, the function loops through it
and

<UL>
<LI>

creates objects for the new generation by calling the function
<EM>evolution()</EM> which returns new members (usually one or two) in a
container,
<A NAME="IDX63"></A>
<LI>

mutates the genetic programs by calling <EM>GP::mutate()</EM>,
<LI>

places the new objects either in the new population, or, if steady state
programming is used, in the old one by selecting bad performing genetic
programs and overwriting them.  If steady state is used, the genetic
program is evaluated at that point, because its fitness must be known
for the selection of the next genetic programs.  However, if steady
state is not used, the evaluation will be delayed until the whole
population has been built.
</UL>

<A NAME="IDX64"></A>
<LI>

If steady state is not used, the population is evaluated by calling
<EM>evaluate()</EM> which calls the function <EM>GP::evaluate()</EM> for
each genetic program.
<LI>

After the new population has been built up, <EM>generate()</EM> calls the
function <EM>demeticMigration()</EM>, if demes are used.
<LI>

<EM>calculateStatistics()</EM> is called to calculate some statistics
about the population.
</OL>

<P>
<A NAME="IDX65"></A>
<A NAME="IDX66"></A>
<A NAME="IDX67"></A>
<A NAME="IDX68"></A>

</P>
<P>
The function <EM>evolution()</EM> creates objects for the new generation.
The configuration parameters <EM>CreationProbability</EM> and
<EM>CrossoverProbability</EM> (See section <A HREF="gpkernel_1.html#SEC15">1.8  Configuration Variables</A>) determine
whether a genetic programs is created anew, two parents are crossed or
one is selected for reproduction.  One should be aware that for each
crossover two children are created (Assuming the appropriate kernel
functions are not overwritten).  A crossover probability of 50%
(<EM>CreationProbability</EM>=0) therefore leads statistically to more
than 50% members of the new population resulting from crossover.  The
structure <EM>GPPopulationRange</EM> defines the range of the population
that the selection process works on.  Also, a flag named
<EM>firstSelectionPerDeme</EM> resides here and is used by the
probabilistic selection function to set up variables that speed up
further selections.

</P>
<P>
<A NAME="IDX69"></A>

</P>
<P>
If demes are used, the population is split into parts of equal size, and
each deme is treated the same as the whole population would be treated
without using demes.  Demetic migration means that for every deme of a
population a genetic program is selected by using the usual selection
scheme and exchanged with a similarly selected program from the next
deme.  The probability of an exchange is determined by the configuration
parameter <EM>DemeticMigProbability</EM>.

</P>
<P>
<A NAME="IDX70"></A>
<A NAME="IDX71"></A>
<A NAME="IDX72"></A>
<A NAME="IDX73"></A>
<A NAME="IDX74"></A>

</P>

<BLOCKQUOTE>

<PRE>
  virtual GPContainer* select (int numToSelect, 
    GPPopulationRange&#38; range);
  virtual GPContainer* selectParents (GPPopulationRange&#38; range);
  virtual void selectIndices (int *selection, int numToSelect, 
    int selectWorst, GPPopulationRange&#38; range);
  virtual void tournamentSelection (int *selection, 
    int numToSelect, int selectWorst, GPPopulationRange&#38; range);
  virtual void probabilisticSelection (int *selection, 
    int numToSelect, int selectWorst, GPPopulationRange&#38; range);
</PRE>

</BLOCKQUOTE>

<P>
  
The selection of genetic programs is important for reproduction and
crossover.  The function <EM>evolution()</EM> calls <EM>select()</EM> to
select one genetic program for reproduction, and <EM>selectParents()</EM>
to select two parents for crossover from a given range of the
population.  The range is either the range of a deme, if demes are used,
or of the whole population.
  
Both functions call <EM>selectIndices()</EM> to receive an array of
indices (parameter <EM>selection</EM>) which refer to the selected genetic
programs.  This function calls either <EM>tournamentSelection()</EM> or
<EM>probabilisticSelection()</EM> depending on the selection type set in
the configuration variables.  The functions can either return the best
ones that were selected or the worst (used for steady state to replace
the genetic programs with bad fitness by those with good fitness).  The
number of genetic programs to select must be either one or two.

</P>
<P>
The crossover process works only for two parents so far.  If other
crossover mechanisms are to be used with more than two parents, not only
the crossover function <EM>GP::cross()</EM> has to be changed, but also
the functions that have to select the parents (<EM>selectParents()</EM>,
<EM>tournamentSelection()</EM> and <EM>probabilisticSelection()</EM>).

</P>
<P>
<A NAME="IDX75"></A>
<A NAME="IDX76"></A>

</P>

<BLOCKQUOTE>

<PRE>
  int bestOfPopulation, worstOfPopulation;
protected:
  GPAdfNodeSet* adfNs;
  GPVariables GPVar;
  double avgFitness, avgLength, avgDepth;
</PRE>

</BLOCKQUOTE>

<P>
<A NAME="IDX77"></A>

</P>
<P>
<EM>bestOfPopulation</EM> and <EM>worstOfPopulation</EM> are indices to the
best and worst member of a population.  The indices are valid only after
<EM>calculateStatistics()</EM> has been called (done after the creation of
the new generation and after a new generation has been evolved by
<EM>generate()</EM>).  <EM>adfNs</EM> is a pointer to the node set
container, and <EM>GPVar</EM> are the configuration variables for the
population.  The other variables are used for statistical purposes.

</P>



<H2><A NAME="SEC13" HREF="gpkernel_toc.html#TOC13">1.6  The Genetic Program</A></H2>

<P>
<A NAME="IDX78"></A>
<A NAME="IDX79"></A>
<A NAME="IDX80"></A>

</P>
<P>
A genetic program consists of a main tree and the ADF trees (if any).
Class <EM>GP</EM> is inherited from <EM>GPContainer</EM> and contains the
root gene of each tree.

</P>

<BLOCKQUOTE>

<PRE>
class GP : public GPContainer
{
public:
  GP (int trees) : GPContainer (trees) { fitnessValid=0; 
    GPlength=0; GPdepth=0; }
  ...
};
</PRE>

</BLOCKQUOTE>

<P>
To create a genetic program, the constructor has to be called with the
correct number of trees.

</P>
<P>
<A NAME="IDX81"></A>
<A NAME="IDX82"></A>
<A NAME="IDX83"></A>

</P>

<BLOCKQUOTE>

<PRE>
  virtual void create (enum GPCreationType ctype, int allowabledepth, 
                       GPAdfNodeSet&#38; adfNs);
  virtual GPGene* createGene (GPNode&#38; gpo) { return new GPGene (gpo); }
  virtual int compare (GP&#38; gp);
</PRE>

</BLOCKQUOTE>

<P>
The function <EM>create()</EM> creates a genetic program.  First, it
creates the root genes of the trees and puts them into the container of
the genetic program.  The root genes are always functions.  Then it
creates the trees by calling the function <EM>create()</EM> for each root
gene.  Normally each tree has a different node set.  They are extracted
from the variable <EM>adfNs</EM> which is a container the same size as the
genetic program.  A mismatch will result in an error (See section <A HREF="gpkernel_1.html#SEC22">1.10.1  Error Handling</A>).  The allowed creation types are either <EM>GPGrow</EM> or
<EM>GPVariable</EM>, all other creation types influence only the allowable
tree depth.

</P>
<P>
<A NAME="IDX84"></A>

</P>
<P>
If the user wants to establish his own gene class, he wants his own
class objects created during the creation process.  The virtual function
<EM>createGene()</EM> is used to create the root genes of the trees.  The
user has to overwrite it to create his own objects.  The same has to be
done for the class <EM>GPGene</EM>, where a similar function named
<EM>createChild()</EM> is used to create the children of a gene.

</P>
<P>
The function <EM>compare()</EM> is used to compare two genetic
programs with each other and can be used to ensure diversity during
the creation process.

</P>
<P>
<A NAME="IDX85"></A>
<A NAME="IDX86"></A>
<A NAME="IDX87"></A>
<A NAME="IDX88"></A>
<A NAME="IDX89"></A>

</P>

<BLOCKQUOTE>

<PRE>
  virtual GPContainer&#38; cross (GPContainer* parents, 
                              int maxdepthforcrossover);
  void shrinkMutation ();
  void swapMutation (GPAdfNodeSet&#38; adfNs);
  virtual void mutate (GPVariables&#38; GPVar, GPAdfNodeSet&#38; adfNs);
  virtual void evaluate ();
</PRE>

</BLOCKQUOTE>

<P>
<A NAME="IDX90"></A>

</P>
<P>
Crossover is one of the most important genetic operations.  It crosses
the parents belonging to a container defined as a parameter.  A
container with children is returned.  If the user overwrites the
function and allocates another container, the passed container must be
deleted.  The number of parents is determined by the function
<EM>generate()</EM> of class <EM>GPPopulation</EM> and must be two for this
implementation to work.  The number of children can be any value
(including zero! Note that if no child is returned every time the
function <EM>cross()</EM> is called, an infinite loop will occur), but is
in this implementation always two.  In crossover, a random number
determines which trees of the parents are crossed, for example, the main
trees, ADF0 trees etc.  From these trees, two cut points are chosen and
the whole subtrees are swapped.  If the depth of one or both the
resulting tree is larger than the configuration parameter
<EM>MaximumDepthForCrossover</EM>, the subtrees are swapped back and
another cut point is chosen.  A fixed maximum amount of trials will be
carried out until the tree size of the children is acceptable.

</P>
<P>
The function <EM>mutate()</EM> determines whether a mutation should take
place, depending on the probability given in the appropriate parameters
of the class <EM>GPVariables</EM> variable.  The mutation operation can be
defined in several ways.  This implementation performs swap and shrink
mutation.  Function <EM>swapMutation()</EM> exchanges a node by another
node randomly chosen from the node set.  Only nodes with the same number
of arguments are swapped.  Function <EM>shrinkMutation()</EM> chooses a
function gene (e.g. a gene which has children), then one of its
children.  The chosen child takes the place of the parent, and the
parent and all other children are deleted.

</P>
<P>
<A NAME="IDX91"></A>

</P>
<P>
The selection of genetic programs is based upon assessing the genetic