overview.html

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

<td valign=top>
<img src="images/ListSwapNodeMutation.gif" alt="list_swap_node"><br>
List Swap Node Mutation<br>
</td>
<td valign=top>
<img src="images/ListSwapSequenceMutation.gif" alt="list_swap_sequence"><br>
List Swap Sequence Mutation<br>
</td>
</tr>

<tr valign=baseline>
<td>
<img src="images/ArraySinglePointCrossover.gif" alt="array_single_point"><br>
Fixed-Length Array Single Point Crossover
</td>

<td>
<img src="images/ArraySinglePointCrossover1.gif" alt="array_single_point"><br>
Variable-Length Array Single Point Crossover<br>
</td>

<td>
<img src="images/ArrayUniformCrossover.gif" alt="array_uniform"><br>
Array Uniform Crossover<br>
</td>
</tr>
</table>









<br>
<br>
<br>
<a name="customization">
<strong>How do I define my own operators?</strong><br></a>
<hr>
Defining the operators is only as difficult as figuring out the algorithm you want to implement.  As far as the actual implementation goes, there's not much to it.  To assign an operator to a genome, just use the appropriate member function.  For example, the following code snippet assigns 'MyInitializer' as the initialization function and 'MyCrossover' as the crossover function for a binary string genome.
<blockquote>
<pre>
  GA1DBinaryStringGenome genome(20);
  genome.initializer(MyInitializer);
  genome.crossover(MyCrossover);
</pre>
</blockquote>
If you do this to the first genome (the one you use to create the genetic algorithm) then all of the ones that the GA clones will have the same operators defined for them.
<p>
When you derive your own genome class you will typically hard-code the operators into the genome like this:
<blockquote>
<pre>
  class MyGenome : public GAGenome {
  public:
    static void RandomInitializer(GAGenome&amp;);
    static int JuggleCrossover(const GAGenome&amp;, const GAGenome&amp;, GAGenome*, GAGenome*);
    static int KillerMutate(GAGenome&amp;, float);
    static float ElementComparator(const GAGenome&amp;, const GAGenome&);
    static float ThresholdObjective(GAGenome&amp;);
  public:
    MyGenome() {
      initializer(RandomInitializer);
      crossover(JuggleCrossover);
      mutator(KillerMutate);
      comparator(ElementComparator);
      evaluator(ThresholdObjective);
    }

    // remainder of class definition here

  };
</pre>
</blockquote>
Notice how easy it becomes to change operators.  You can very easily define a multitude of operators for a single representation and experiment with them to see which performs better.
</p>
<p>
Why are the genome operators GAlib <i>not</i> member functions?  The primary reason is so that you do not have to derive a new class in order to change the behaviour of one of the built-in genome types.  In addition, the use of function pointers rather than member functions lets us change operators at run-time (unlike member functions or templatized classes).  And they are faster than virtual functions (OK, so this the virtual/non-virtual component is a pretty small fraction of actual execution time compared to most objective functions...).  On the down side, they permit you to make some ugly mistakes by improperly casting.
</p>
<br>
<br>


The definition for the List1PtCrossover looks like this:<br>
<i>This crossover picks a single point in the parents then generates one or two children from the two halves of each parent.</i>

<blockquote>
<pre>
template &lt;class T&gt; int
OnePointCrossover(const GAGenome&amp; p1, const GAGenome&amp; p2, GAGenome* c1, GAGenome* c2){
  GAListGenome&lt;T&gt; &amp;mom=(GAListGenome&lt;T&gt; &amp;)p1;
  GAListGenome&lt;T&gt; &amp;dad=(GAListGenome&lt;T&gt; &amp;)p2;

  int nc=0;
  unsigned int a = GARandomInt(0, mom.size());
  unsigned int b = GARandomInt(0, dad.size());
  GAList&lt;T&gt; * list;

// first do the sister...

  if(c1){
    GAListGenome&lt;T&gt; &amp;sis=(GAListGenome&lt;T&gt; &amp;)*c1;
    sis.GAList&lt;T&gt;::copy(mom);
    list = dad.GAList&lt;T&gt;::clone(b);
    if(a &lt; mom.size()){
      T *site = sis.warp(a);
      while(sis.tail() != site)
        sis.destroy();          // delete the tail node
      sis.destroy();            // trash the trailing node (list[a])
    }
    else{
      sis.tail();               // move to the end of the list
    }
    sis.insert(list);           // stick the clone onto the end
    delete list;
    sis.warp(0);                // set iterator to head of list

    nc += 1;
  }

// ...now do the brother

  if(c2){
    GAListGenome&lt;T&gt; &amp;bro=(GAListGenome&lt;T&gt; &amp;)*c2;
    bro.GAList&lt;T&gt;::copy(dad);
    list = mom.GAList&lt;T&gt;::clone(a);
    if(b &lt; dad.size()){
      T *site = bro.warp(b);
      while(bro.tail() != site)
        bro.destroy();          // delete the tail node
      bro.destroy();            // trash the trailing node (list[a])
    }
    else{
      bro.tail();               // move to the end of the list
    }
    bro.insert(list);           // stick the clone onto the end
    delete list;
    bro.warp(0);                // set iterator to head of list

    nc += 1;
  }

  return nc;
}
</pre>
</blockquote>
<br>
<br>


The definition for FlipMutator for 1DArrayAlleles looks like this:<br>
<i>This mutator flips the value of a single element of the array to any of the possible allele values.</i>
<blockquote>
<pre>
int 
FlipMutator(GAGenome &amp; c, float pmut)
{
  GA1DArrayAlleleGenome&lt;ARRAY_TYPE&gt; &amp;child=(GA1DArrayAlleleGenome&lt;ARRAY_TYPE&gt; &amp;)c;
  register int n, i;
  if(pmut &lt;= 0.0) return(0);

  float nMut = pmut * (float)(child.length());
  if(nMut &lt; 1.0){		// we have to do a flip test on each bit
    nMut = 0;
    for(i=child.length()-1; i&gt;=0; i--){
      if(GAFlipCoin(pmut)){
	child.gene(i, child.alleleset().allele());
	nMut++;
      }
    }
  }
  else{				// only flip the number of bits we need to flip
    for(n=0; n&lt;nMut; n++){
      i = GARandomInt(0, child.length()-1); // the index of the bit to flip
      child.gene(i, child.alleleset().allele());
    }
  }
  return((int)nMut);
}
</pre>
</blockquote>
<br>
<br>


And the definition for a typical initializer looks like this:<br>
<i>This initializer creates a tree of bounded random size and forkiness.</i>
<blockquote>
<pre>
void
TreeInitializer(GAGenome &amp; c)
{
  GATreeGenome&lt;Point&gt; &amp;tree=(GATreeGenome&lt;Point&gt; &amp;)c;

  tree.root();
  tree.destroy();   // destroy any pre-existing tree

  Point p(0,0,0);
  tree.insert(p,GATreeBASE::ROOT);
  int n = GARandomInt(0,MAX_CHILDREN);	// limit number of children
  for(int i=0; i&lt;n; i++)
    DoChild(tree, 0);
}

void
DoChild(GATreeGenome&lt;Point&gt; &amp; tree, int depth)
{
  if(depth &gt;= MAX_DEPTH) return;     // limit depth of the tree
  int n = GARandomInt(0,MAX_CHILDREN);	// limit number of children

  Point p(GARandomFloat(0,25),GARandomFloat(0,25),GARandomFloat(0,25));
  tree.insert(p,GATreeBASE::BELOW);

  for(int i=0; i&lt;n; i++)
    DoChild(tree, depth+1);

  tree.parent();		// move the iterator up one level
}
</pre>
</blockquote>
<br>
<br>



<a name="derivation">
<strong>What about deriving my own genome class?</strong><br></a>
<hr>
Here is the definition of a genome that contains an arbitrary number of lists.  It could easily be modified to become a diploid genome.  It is used in exactly the same way that the built-in genomes are used.  For a simpler example, see the <a href="examples/gnu/bitstr.h">GNU example</a> which integrates the GNU BitString object with GAlib to form a new genome class.
<blockquote>
<pre>
class RobotPathGenome : public GAGenome {
public:
  GADefineIdentity("RobotPathGenome", 251);
  static void Initializer(GAGenome&amp;);
  static int Mutator(GAGenome&amp;, float);
  static float Comparator(const GAGenome&amp;, const GAGenome&);
  static float Evaluator(GAGenome&amp;);
  static void PathInitializer(GAGenome&amp;);
public:
  RobotPathGenome(int nrobots, int pathlength);
  RobotPathGenome(const RobotPathGenome &amp; orig);
  RobotPathGenome&amp; operator=(const GAGenome &amp; arg);
  virtual ~RobotPathGenome();
  virtual GAGenome *clone(GAGenome::CloneMethod) const ;
  virtual void copy(const GAGenome &amp; c);
  virtual int equal(const GAGenome&amp; g) const ;
  virtual int read(istream &amp; is);
  virtual int write(ostream &amp; os) const ;

  GAListGenome&lt;int&gt; &amp; path(int i){ return *list[i]; }
  int npaths() const { return n; }
  int length() const { return l; }

protected:
  int n, l;
  GAListGenome&lt;int&gt; **list;
};
</pre>
</blockquote>

Please see the <a href="examples/">examples</a> for complete details.

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

</body></html>