gpkernel_1.html

用C++编写的遗传算法

programs in some way.  This depends on the problem the user wants to
solve.  The function <EM>evaluate()</EM> must therefore be written by the
user.  It has to calculate the standardised fitness (See Koza's book) of
the genetic program and put the result in the member variable
<EM>stdFitness</EM>.  The standardised fitness is a positive value where
smaller values denotes a better fitness.

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

</P>

<BLOCKQUOTE>

<PRE>
  virtual void printOn (ostream&#38; os);
</PRE>

</BLOCKQUOTE>

<P>
The print function prints out all trees the genetic program contains.

</P>
<P>
<A NAME="IDX93"></A>
<A NAME="IDX94"></A>
<A NAME="IDX95"></A>
<A NAME="IDX96"></A>
<A NAME="IDX97"></A>
<A NAME="IDX98"></A>

</P>

<BLOCKQUOTE>

<PRE>
  double getFitness () { return stdFitness; }
  virtual int length () { return GPlength; }
  virtual int depth () { return GPdepth; }
  virtual void calcLength ();
  virtual void calcDepth ();
  GPGene* NthGene (int n) { return (GPGene*) GPContainer::Nth(n); }
</PRE>

</BLOCKQUOTE>

<P>
These functions return information about the genetic program.  The
length and depth of a genetic program is defined as the sum of the
length and depth of all trees.  These values are needed more than once
within the library.  To calculate them repeatedly leads to an impact on
program efficiency as all the trees have to be parsed.  To save
calculation time, the values are saved in the object.  That means that
the functions <EM>calcLength()</EM> and <EM>calcDepth()</EM> have to be
called whenever the length and depth of a genetic program might change
(for example, for crossover, but not swap mutation).

</P>

<BLOCKQUOTE>

<PRE>
protected:
  int fitnessValid;
  double stdFitness;
  int GPlength, GPdepth;
</PRE>

</BLOCKQUOTE>

<P>
The variable <EM>stdFitness</EM> is the standardised fitness (positive
numbers, and 0.0 is best) of the genetic program.  The fitness does not
change when a program is reproduced.  To save computational power, a
flag determines whether the fitness of the <EM>GP</EM> object is already
calculated or not.  The flag must be set to 0 by any operation that
changes the genetic program (for example, the crossover and mutation),
but not by reproduction.  The length and depth of a genetic program are
also saved.

</P>



<H2><A NAME="SEC14" HREF="gpkernel_toc.html#TOC14">1.7  The Gene</A></H2>

<P>
<A NAME="IDX99"></A>
<A NAME="IDX100"></A>
<A NAME="IDX101"></A>

</P>
<P>
Genetic Programming uses tree structures to internally store genetic
programs.  A tree consists of genes, each of which can be the parent
gene for one or more children.  A gene is also a container, so the class
<EM>GPContainer</EM> can be used again.  A gene object has only one
component: a pointer to an object of class <EM>GPNode</EM>.  By
referencing a node object rather than, for example, the node's
identification value, several aspects have to be taken into account.
The most important argument was that the user might use his own node
class with components accessible in this way.  To store the complete
node object into the gene is certainly not a bad solution, but is not
used due to memory considerations.  The reference, on the other hand,
makes problems when a population has to be saved and loaded again.  See
section <A HREF="gpkernel_1.html#SEC16">1.9  Loading and Saving of Populations</A> how this is solved.

</P>

<BLOCKQUOTE>

<PRE>
class GPGene : public GPContainer
{
public:
  GPGene (GPNode&#38; gpo) : node(&#38;gpo), GPContainer(gpo.arguments()) {}
  ...
};
</PRE>

</BLOCKQUOTE>

<P>
To create and use a gene object, a node object has to exist.  The
constructor is called with a reference to the node object, which is
saved in the gene object.  At the same time, the constructor of the base
class <EM>GPContainer</EM> is called with the number of arguments (or
children) the gene requires.

</P>
<P>
<A NAME="IDX102"></A>
<A NAME="IDX103"></A>
<A NAME="IDX104"></A>

</P>

<BLOCKQUOTE>

<PRE>
  virtual void create (enum GPCreationType ctype, int allowabledepth, 
                       GPNodeSet&#38; ns);
  virtual GPGene* createChild (GPNode&#38; gpo) {
    return new GPGene (gpo); }
  friend int operator == (GPGene&#38; pg1, GPGene&#38; pg2);
  virtual int compare (GPGene&#38; g);
</PRE>

</BLOCKQUOTE>

<P>
The function <EM>create()</EM> is used to create a complete subtree.  It
must be called either with <EM>GPGrow</EM> or <EM>GPVariable</EM> as
creation type.  The other creation types that exist (see
section <A HREF="gpkernel_1.html#SEC15">1.8  Configuration Variables</A> for more on the possible creation types)
influence only the maximum allowable depth for creation.  The function
creates the children for the object it was called for and calls itself
recursively for each child which is not a terminal, reducing the
allowable depth by 1.  To build a complete tree, the root tree node must
be created, and then this function can be called for that object.  The
function <EM>GP::create()</EM> does exactly this.

</P>
<P>
If the user wants to establish his own gene class, he wants his own
class objects created during the creation process.  Instead of the
constructor, the class <EM>GPGene</EM> uses the function
<EM>createChild()</EM>, a virtual function, for the creation process.  The
user can overwrite the function and create any object that belongs to a
class inherited from <EM>GPGene</EM>.  A similar function in class
<EM>GP</EM> must also be overwritten.

</P>
<P>
The compare function compares two trees with each other.  It is used
during creation to ensure that the created genetic programs are unique.

</P>
<P>
<A NAME="IDX105"></A>
<A NAME="IDX106"></A>
<A NAME="IDX107"></A>
<A NAME="IDX108"></A>

</P>

<BLOCKQUOTE>

<PRE>
  GPGene** findNthNode (GPGene** rootPtr, int findFunction,
                        int &#38;iLengthCount);
  virtual GPGene** choose (GPGene** rootPtr);
  int countFunctions ();
  GPGene** chooseFunctionNode (GPGene** rootPtr);
</PRE>

</BLOCKQUOTE>

<P>
These functions are used for crossover and shrink mutation where a gene
has to be selected on each parent tree by random.  This is done by
function <EM>findNthNode()</EM>.  It must be called with (a) a reference
to the pointer to the root gene, (b) a flag indicating whether just
functions or both functions and terminals are to be selected, and (c) a
reference to a variable containing a (random) number between 0 and one
less than the number of selectable genes in the tree.  The function
parses the tree thereby decrementing the length counter, and returns a
reference to the pointer to the found gene.  The reason why references
to pointers are used is very simple: the crossover operation only has to
swap the pointers to perform the crossover.  Shrink mutation is also
faster.

</P>
<P>
The function <EM>choose()</EM> is used for crossover.  It selects a point
within a genetic tree and returns a reference to a pointer to that node.
It uses the function <EM>length()</EM> to calculate the length of the tree
before choosing a random number in the correct range and calling
<EM>findNthNode()</EM>.

</P>
<P>
The function <EM>chooseFunctionNode()</EM> is used for shrink mutation.
It selects a function gene within a genetic tree and returns a reference
to a pointer to that node.  It uses the function <EM>countFunctions()</EM>
to calculate the number of function of the tree before choosing a random
number in the correct range and calling <EM>findNthNode()</EM>.  If no
function nodes exists, NULL is returned.

</P>
<P>
<A NAME="IDX109"></A>
<A NAME="IDX110"></A>
<A NAME="IDX111"></A>
<A NAME="IDX112"></A>
<A NAME="IDX113"></A>
<A NAME="IDX114"></A>
<A NAME="IDX115"></A>

</P>

<BLOCKQUOTE>

<PRE>
  virtual void printOn (ostream&#38; os);
  GPGene* NthChild (int n) {
    return (GPGene*) GPContainer::Nth (n); }
  GPNode&#38; geneNode () { return *node; }
  virtual int isFunction () { return node-&#62;isFunction (); }
  virtual int isTerminal () { return node-&#62;isTerminal (); }
  virtual int length ();
  virtual int depth (int depthSoFar=1);
</PRE>

</BLOCKQUOTE>

<P>
These functions return information about the gene or a genetic tree.
<EM>printOn()</EM> prints a tree in the typical lisp notation: if the gene
is a function, it prints an open parenthesis, the node, all children and
a close parenthesis, otherwise only the node.  Printing the node means
that the function <EM>GPNode::printOn()</EM> of the node is called.

</P>
<P>
The function <EM>depth()</EM> should be called without a parameter.  It is
recursive and uses its parameter to calculate the depth of the tree.

</P>

<BLOCKQUOTE>

<PRE>
protected:
  union
  {
    GPNode* node;
    int nodeValue;
  };
</PRE>

</BLOCKQUOTE>

<P>
As described above, using a reference to a <EM>GPNode</EM> object
complicates the process of loading and saving a population.  It is
solved this way: only the identification value of the node is saved.
That means that if a gene is loaded again from a stream, it gets only
this value back and, to save memory, stores it temporarily at the same
location where the pointer resides.  Another function described later
has to be called after the load process to convert the identification
value back to a reference.

</P>



<H2><A NAME="SEC15" HREF="gpkernel_toc.html#TOC15">1.8  Configuration Variables</A></H2>

<P>
<A NAME="IDX116"></A>
<A NAME="IDX117"></A>
<A NAME="IDX118"></A>

</P>
<P>
This class is used to control the behaviour of several aspects of
Genetic Programming.  Each population object has an object of this class
as a member.  In this section, the meaning of all variables will be
discussed.

</P>
<DL COMPACT>

  
<DT><STRONG>PopulationSize (integer, <CODE>[1..MaxInt]</CODE>)</STRONG>
<DD>
<A NAME="IDX119"></A>
 

The number of members in a population.  The kernel uses this parameter
during the creation of a population, where the appropriate space for the
genetic programs is reserved.
  
<A NAME="IDX120"></A>
<DT><STRONG>NumberOfGenerations (integer, <CODE>[0..MaxInt]</CODE>)</STRONG>
<DD>
The maximum number of generations for which the evolution process should
run.  This variable is not used by the Genetic Programming system.  The
user programs the main loop and can use other criteria to halt the
evolution process (for example, convergence to a solution, time etc.),
but it is quite common to restrict the number of generations.
  
<A NAME="IDX121"></A>
<DT><STRONG>CrossoverProbability (double, <CODE>[0.0..100.0]</CODE>)</STRONG>
<DD>
The probability (in percent) that crossover takes place.  The crossover
function returns usually two children, but may return also more or less.
That means that the percentage of new population members resulting from
crossover does not conform with the probability of crossover.
  
<A NAME="IDX122"></A>
<DT><STRONG>CreationProbability (double, <CODE>[0.0..100.0]</CODE>)</STRONG>
<DD>
The probability (in percent) that completely new trees are created for
the new generation.  The creation type used is <EM>GPVariable</EM>.  As
the fitness of a newly created tree tends to be bad, this parameter can
be set to 0.
  
<A NAME="IDX123"></A>
<DT><STRONG>CreationType (integer, <CODE>[0..5]</CODE>)</STRONG>
<DD>
The creation type for the initial population.  The values have the
following meaning:

<A NAME="IDX124"></A>
<A NAME="IDX125"></A>
<A NAME="IDX126"></A>
<A NAME="IDX127"></A>
<A NAME="IDX128"></A>
<A NAME="IDX129"></A>
<A NAME="IDX130"></A>
<A NAME="IDX131"></A>
<A NAME="IDX132"></A>
<A NAME="IDX133"></A>
<A NAME="IDX134"></A>
<A NAME="IDX135"></A>


<UL>
  
<LI>[0] <EM>GPVariable</EM>

Variable growth.  During creation, the children of a function node are
chosen from either the function set or the terminal set with a certain
probability (in this case always 50%).
  
<LI>[1] <EM>GPGrow</EM>

All branches have a maximum depth.
    
<LI>[2] <EM>GPRampedHalf</EM>

Koza uses this creation method.  It is half and half of
<EM>GPRampedVariable</EM> and <EM>GPRampedGrow</EM>.
    
<LI>[3] <EM>GPRampedVariable</EM>

Ramped means that during creation, the allowable tree depth is increased
up to the maximum specified by the user.  The behaviour is the same as
<EM>GPVariable</EM> otherwise.
    
<LI>[4] <EM>GPRampedGrow</EM>

Same as <EM>GPGrow</EM> except for the maximum allowable tree depth which
changes according to a ramp during creation.
    
<LI>[5] <EM>GPUserDefinedCreation</EM>

This is not implemented, but the user can do this in one of his
inherited classes.

</UL>

<A NAME="IDX136"></A>
<DT><STRONG>MaximumDepthForCreation (integer, <CODE>[2..MaxInt]</CODE>)</STRONG>
<DD>
The maximum depth that must not be exceeded during the creation of a
genetic tree.  The Genetic Programming kernel always uses a function as
the root node of a tree during creation, as does Koza.  Therefore, a
depth smaller then 2 makes no sense.  Depending on the creation type, a
high depth size can lead to extremely large trees and long creation
times and consumes a lot of memory.
  
<A NAME="IDX137"></A>
<DT><STRONG>MaximumDepthForCrossover (integer, <CODE>[MaximumDepthForCreation..MaxInt]</CODE>)</STRONG>
<DD>
The maximum tree depth is most easily exceeded by crossing two trees.
Therefore, the crossover operation selects two cut points on the
selected trees so that the tree depth of each child is less than or
equal to this parameter.
  
<A NAME="IDX138"></A>
<DT><STRONG>SelectionType (integer, <CODE>[0..1]</CODE>)</STRONG>
<DD>
Can be probabilistic selection (value 0) or tournament selection (value
1).  Remember that for large populations tournament selection usually
works faster, but the implementation of probabilistic selection is also
very fast, and both methods are difficult to compare with respect to
computational power.
  
<A NAME="IDX139"></A>
<DT><STRONG>TournamentSize (integer, <CODE>[1..MaxInt]</CODE>)</STRONG>
<DD>
When tournament selection is used, a number of members are chosen by
random from of the population.  Only the best of this tournament are
selected for further evolution strategies.  If this parameter is too
large the probability that always the best one of a population is
selected is very high.
  
<A NAME="IDX140"></A>
<DT><STRONG>DemeticGrouping (integer, <CODE>[0..1]</CODE>)</STRONG>
<DD>
This is a switch and indicates whether demetic grouping should be used
(value 1) or not (value 0).
  
<A NAME="IDX141"></A>
<DT><STRONG>DemeSize (integer, <CODE>[1..PopulationSize]</CODE>)</STRONG>
<DD>
Determines the size of the demes.  <EM>PopulationSize</EM> modulo
<EM>DemeSize</EM> must be zero.
  
<A NAME="IDX142"></A>
<DT><STRONG>DemeticMigProbability (double, <CODE>[0.0..100.0]</CODE>)</STRONG>
<DD>
The probability (in percent) that a member of one deme is swapped with a
member of the next deme.  There is always only one member swapped.