gpkernel_1.html

用C++编写的遗传算法

</P>
<P>
A container also provides a simple print function: it calls the
<EM>printOn()</EM> function of every object it contains.  This function is
usually overwritten by the inheriting classes.

</P>



<H2><A NAME="SEC7" HREF="gpkernel_toc.html#TOC7">1.4  Functions and Terminals</A></H2>

<P>
<A NAME="IDX18"></A>
<A NAME="IDX19"></A>
<A NAME="IDX20"></A>

</P>
<P>
A genetic program consists of a tree structure.  Each node within the
tree has certain properties.  It can be either a function, which has
parameters, or a terminal.  By definition the difference between a
function and terminal is that a terminal has no arguments.  One could
also say a terminal is a function with no arguments.  Indeed they are so
similar that a distinction that leads to different classes is not
necessary.  Both types are referred to as nodes throughout the report.

</P>
<P>
The class <EM>GPNode</EM> is used to describe the properties of a node.
The class is not used to represent the tree structure of a genetic
program (See section <A HREF="gpkernel_1.html#SEC14">1.7  The Gene</A>, class <EM>GPGene</EM>).  The classes
<EM>GPNode</EM>, <EM>GPNodeSet</EM> and <EM>GPAdfNodeSet</EM> are only used to
describe the properties of the functions and terminals for later
populations.

</P>



<H3><A NAME="SEC8" HREF="gpkernel_toc.html#TOC8">1.4.1  Class GPNode</A></H3>

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

</P>

<BLOCKQUOTE>

<PRE>
class GPNode : public GPObject
{
public:
  GPNode (int nVal, char* str, int args=0) : nodeValue(nVal), 
      numOfArgs(args) { representation=copyString (str); }
  virtual ~GPNode () { delete [] representation; }
  ...
};
</PRE>

</BLOCKQUOTE>

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

</P>
<P>
The constructor defines a node and receives an identification parameter
of type integer and a string which is used for output.  The class makes
a copy of this string.  To define a function, a third parameter, namely
the number of arguments the function has, is given to the constructor.
The identification value must be unique for a node set (See section <A HREF="gpkernel_1.html#SEC9">1.4.2  Sets of Nodes</A>).

</P>
<P>
<A NAME="IDX23"></A>
<A NAME="IDX24"></A>
<A NAME="IDX25"></A>
<A NAME="IDX26"></A>
<A NAME="IDX27"></A>

</P>

<BLOCKQUOTE>

<PRE>
  int value () { return nodeValue; }
  int isFunction () { return numOfArgs!=0; }
  int isTerminal () { return numOfArgs==0; }
  int arguments () { return numOfArgs; }
  virtual void printOn (ostream&#38; os) { os &#60;&#60; representation; }
</PRE>

</BLOCKQUOTE>

<P>
These functions are self-explanatory and return information about the
node.  The function <EM>printOn()</EM> prints the representation string.

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

</P>

<BLOCKQUOTE>

<PRE>
protected:
  char copyString (char *str);
  int nodeValue;
  int numOfArgs;
  char* representation;
</PRE>

</BLOCKQUOTE>

<P>
These components are protected and not accessible from outside the class
scope.  <EM>copyString()</EM> allocates memory with the <EM>new</EM>
operator and makes a copy of the given string.

</P>



<H3><A NAME="SEC9" HREF="gpkernel_toc.html#TOC9">1.4.2  Sets of Nodes</A></H3>

<P>
<A NAME="IDX29"></A>
<A NAME="IDX30"></A>

</P>
<P>
Each genetic tree has its own function and terminal set.  For this
purpose, the class <EM>GPNodeSet</EM> is introduced and serves as a
container to hold all the different nodes.

</P>
<P>
<A NAME="IDX31"></A>
<A NAME="IDX32"></A>

</P>
<P>
During the creation process of the population, the class has to choose a
node either from the terminals or the functions.  To increase
efficiency, the class puts functions at the beginning and terminals at
the end of the container.  Therefore, the function <EM>put()</EM> must not
be used to manually put nodes in the container, the function
<EM>putNode()</EM> should be used.  This also increases ease of use.

</P>

<BLOCKQUOTE>

<PRE>
class GPNodeSet : public GPContainer
{
public:
  GPNodeSet (int numOfNodes) : GPContainer (numOfNodes) {
    numFunctions=0; numTerminals=0; }
  ...
};
</PRE>

</BLOCKQUOTE>

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

</P>
<P>
During the process of placing nodes in the container, two variables are
used which are initialised by the constructors.  These count the number
of functions and terminals that are put in the container.

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

</P>

<BLOCKQUOTE>

<PRE>
  virtual void put (int, GPObject&#38;);
  virtual void putNode (GPNode&#38; gpo);
</PRE>

</BLOCKQUOTE>

<P>
As mentioned above, the function <EM>putNode()</EM> puts functions at the
beginning and terminals at the end of the container.  If the user tries
to call the function <EM>put()</EM>, the whole process gets mixed up.  The
function <EM>put()</EM> is defined in the class and exits with an error
message if it is called.  The identification values of the nodes must be
distinguishable for a node set (See section <A HREF="gpkernel_1.html#SEC8">1.4.1  Class GPNode</A>).  This is checked
by the function <EM>putNode()</EM>.

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

</P>

<BLOCKQUOTE>

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

</BLOCKQUOTE>

<P>
<EM>printOn()</EM> prints out the complete node set.  For each node, it
prints out the node, and if the node is a function, parenthesis around
the number of arguments of the function.

</P>
<P>
<A NAME="IDX36"></A>
<A NAME="IDX37"></A>

</P>

<BLOCKQUOTE>

<PRE>
  virtual GPNode* searchForNode (int value);
  GPNode* NthNode (int n) {
    return (GPNode*) GPContainer::Nth (n); }
</PRE>

</BLOCKQUOTE>

<P>
Function <EM>searchForNode()</EM> scans through a node set and tries to
find a node with the given identification value.  It returns the address
of the node.  If no node is found, NULL is returned.  <EM>NthNode()</EM>
returns the node with index n of the container.

</P>
<P>
<A NAME="IDX38"></A>
<A NAME="IDX39"></A>
<A NAME="IDX40"></A>

</P>

<BLOCKQUOTE>

<PRE>
  virtual GPNode&#38; chooseFunction();
  virtual GPNode&#38; chooseTerminal();
  virtual GPNode* chooseNodeWithArgs (int args);
</PRE>

</BLOCKQUOTE>

<P>
The first two functions are used during the creation process and choose
either a function or a terminal from the node set.  They do this by
random and are virtual functions in case the user wants to, for example,
impose restrictions on the selection.  To perform swap mutation, the
mutation function exchanges a node with another node from the node set
but with the same number of arguments.  <EM>chooseNodeWithArgs()</EM>
scans through the node set, counts the nodes with the appropriate number
of arguments and selects one of them by random.  If none is found,
<EM>chooseNodeWithArgs()</EM> returns NULL.

</P>

<BLOCKQUOTE>

<PRE>
protected:
  int numFunctions, numTerminals;
</PRE>

</BLOCKQUOTE>

<P>
These variables are used to distinguish between functions and terminals
within the container.  The container contains functions from index
<CODE>[</CODE>0...<EM>numFunctions</EM><CODE>]</CODE> and terminals from index
<CODE>[</CODE><EM>containerSize()</EM><CODE>-</CODE><EM>numTerminals</EM>...<EM>containerSize()</EM><CODE>]</CODE>
(last index exclusive).

</P>



<H3><A NAME="SEC10" HREF="gpkernel_toc.html#TOC10">1.4.3  Container for Node Sets</A></H3>

<P>
<A NAME="IDX41"></A>
<A NAME="IDX42"></A>
<A NAME="IDX43"></A>

</P>
<P>
A genetic program consists of the main tree and the ADF trees.  Each
tree type can have different function and terminal sets.  This allows
the user to introduce a priori knowledge of the task to be performed by
the genetic program.  To ensure easy handling and to prevent mistakes in
accessing the sets, the container class <EM>GPAdfNodeSet</EM> is used to
collect the node sets together rather than using an array which is not
foolproof.  The container size of such an object determines the number
of ADFs the user wants to use.

</P>
<P>
<A NAME="IDX44"></A>
<A NAME="IDX45"></A>

</P>

<BLOCKQUOTE>

<PRE>
class GPAdfNodeSet : public GPContainer
{
public:
  GPAdfNodeSet () {}
  GPAdfNodeSet (int numOfTrees) : GPContainer(numOfTrees) {}
  virtual void printOn (ostream&#38; os);
  GPNodeSet* NthNodeSet (int n) { 
    return (GPNodeSet*) GPContainer::Nth (n); }
  ...
};
</PRE>

</BLOCKQUOTE>

<P>
The class declaration is very short as it differs only slightly from an
ordinary container class.  Remember that if the parameterless
constructor is used the container size can be set later with the
function <EM>reserveSpace()</EM>.  The function <EM>printOn()</EM> prints
the number of the tree and the corresponding node set for each tree.
<EM>NthNodeSet(n)</EM> returns a reference to the node set with index
<EM>n</EM>.

</P>



<H3><A NAME="SEC11" HREF="gpkernel_toc.html#TOC11">1.4.4  How to Use the Classes</A></H3>

<P>
Before a population can be created, the functions and terminals have to
be defined.  This is very easy using the classes <EM>GPNode</EM>,
<EM>GPNodeSet</EM>, and <EM>GPAdfNodeSet</EM>.  First the container for all
node sets must be declared.

</P>

<BLOCKQUOTE>

<PRE>
  GPAdfNodeSet adfNs;
</PRE>

</BLOCKQUOTE>

<P>
Then space is reserved for the node sets (in this example one for the
main tree and one ADF tree).  This code determines the number of ADF
trees the genetic programs have, because the creation process uses all
node sets in this container, and creates the same number of trees.

</P>

<BLOCKQUOTE>

<PRE>
  adfNs.reserveSpace (2);
</PRE>

</BLOCKQUOTE>

<P>
Now the node sets for each tree are allocated and put into the container
of the <EM>adfNs</EM> object.  Each node set constructor is passed the
correct number of nodes the container will hold:

</P>

<BLOCKQUOTE>

<PRE>
  GPNodeSet&#38; mainTree=*new GPNodeSet (6);
  GPNodeSet&#38; adf0Tree=*new GPNodeSet (4);
  adfNs.put (0, mainTree);
  adfNs.put (1, adf0Tree);
</PRE>

</BLOCKQUOTE>

<P>
The last step is to define the functions and terminals and put them into
the node sets.  The identification values for the nodes are of type
<EM>integer</EM>, but can be characters which are more descriptive.  This
example is taken from the symbolic regression program and defines the
following nodes:

</P>
<DL COMPACT>

<DT><VAR>Main tree</VAR>
<DD>
<DL COMPACT>

<DT><VAR>Functions</VAR>
<DD>
<CODE>+,-,*,/,ADF0(x1,x2)</CODE>
<DT><VAR>Terminals</VAR>
<DD>
<CODE>x</CODE>
</DL>
<DT><VAR>ADF tree</VAR>
<DD>
<DL COMPACT>

<DT><VAR>Functions</VAR>
<DD>
<CODE>+,-</CODE>
<DT><VAR>Terminals</VAR>
<DD>
<CODE>x1,x2</CODE>
</DL>
</DL>


<BLOCKQUOTE>

<PRE>
  mainTree.putNode (*new GPNode ('+', "+", 2));
  mainTree.putNode (*new GPNode ('-', "-", 2));
  mainTree.putNode (*new GPNode ('*', "*", 2));
  mainTree.putNode (*new GPNode ('%', "%", 2));
  mainTree.putNode (*new GPNode ('A', "ADF0", 2));
  mainTree.putNode (*new GPNode ('X', "x"));
  adf0Tree.putNode (*new GPNode ('+', "+", 2));
  adf0Tree.putNode (*new GPNode ('*', "*", 2));
  adf0Tree.putNode (*new GPNode (1, "x1"));
  adf0Tree.putNode (*new GPNode (2, "x2"));
</PRE>

</BLOCKQUOTE>



<H2><A NAME="SEC12" HREF="gpkernel_toc.html#TOC12">1.5  The Population</A></H2>

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