📄 extensions.html
字号:
<html><head><title>GAlib: Extensions</title><!-- by matthew wall all rights reserved --><!-- Copyright (c) 1995-1996 Massachusetts Institute of Technology --><!-- Copyright (c) 1996-1999 Matthew Wall --></head><body bgcolor="efefef" text="000000"><strong>Customizing <a href="GAlib.html">GAlib</a></strong><br><i>version 2.4</i><p>This document describes how to extend GAlib's capabilities by defining your own genomes and genetic operators. The best way to customize the behavior of an object is to derive a new class. If you do not want to do that much work, GAlib is designed to let you replace behaviors of existing objects by defining new functions.</p><p>see also: <i><a href="Overview.html">library overview</a>, <a href="ClassHierarchy.html">class hierarchy</a>, <a href="API.html">programming interface</a></i></p><p><strong>Table of contents</strong><br><hr><br></p><table><tr valign=baseline><td width=220><ul><strong>Genome</strong><li><a href="#genome">Deriving a new Genome</a><li><a href="#genome_testing">Testing a new Genome</a><li><a href="#genome_initialization">Initialization</a><li><a href="#genome_mutation">Mutation</a><li><a href="#genome_crossover">Crossover</a><li><a href="#genome_comparison">Comparison</a><li><a href="#genome_evaluation">Evaluation</a></ul></td><td width=6></td><td width=180><ul><strong>Population</strong><li><a href="#pop_initialization">Initialization</a><li><a href="#pop_evaluation">Evaluation</a><li><a href="#pop_scaling">Scaling</a><li><a href="#pop_selection">Selection</a></ul></td><td width=6></td><td width=220><ul><strong>Genetic Algorithm</strong><li><a href="#ga">Deriving a new Algorithm</a><li><a href="#termination">Termination</a></ul></td></tr></table><br><br><br><a name="genome"><br><strong>Deriving your own genome class</strong><br></a><hr>You can create your own genome class by multiply-inheriting from the base genome class and your own data type. For example, if you have already have an object defined, say MyObject, then you would derive a new genome class called MyGenome, whose class definition looks like this:<pre>// Class definition for the new genome object, including statically defined// declarations for default evaluation, initialization, mutation, and // comparison methods for this genome class.class MyGenome : public MyObject, public GAGenome {public: GADefineIdentity("MyGenome", 201); static void Init(GAGenome&); static int Mutate(GAGenome&, float); static float Compare(const GAGenome&, const GAGenome&); static float Evaluate(GAGenome&); static int Cross(const GAGenome&, const GAGenome&, GAGenome*, GAGenome*);public: MyGenome() : GAGenome(Init, Mutate, Compare) { evaluator(Evaluate); crossover(Cross); } MyGenome(const MyGenome& orig) { copy(orig); } virtual ~MyGenome() {} MyGenome& operator=(const GAGenome& orig){ if(&orig != this) copy(orig); return *this; } virtual GAGenome* clone(CloneMethod) const {return new MyGenome(*this);} virtual void copy(const GAGenome& orig) { GAGenome::copy(orig); // this copies all of the base genome parts // copy any parts of MyObject here // copy any parts of MyGenome here } // any data/member functions specific to this new class};void MyGenome::Init(GAGenome&){ // your initializer here}int MyGenome::Mutate(GAGenome&, float){ // your mutator here}float MyGenome::Compare(const GAGenome&, const GAGenome&){ // your comparison here}float MyGenome::Evaluate(GAGenome&){ // your evaluation here}intMyGenome::Cross(const GAGenome& mom, const GAGenome& dad, GAGenome* sis, GAGenome* bro){ // your crossover here}</pre><p>By convention, one of the arguments to a derived genome constructor is the objective function. Alternatively (as illustrated in this example), you can hard code a default objective function into your genome - just call the <b>evaluator</b> member somewhere in your constructor and pass the function you want used as the default.</p><p>Once you have defined your genome class, you should define the <a href="#genome_initialization">intialization</a>, <a href="#genome_mutation">mutation</a>, <a href="#genome_comparison">comparison</a>, and <a href="#genome_crossover">crossover</a> operators for it. The comparison operator is optional, but if you do not define it you will not be able to use the diversity measures in the genetic algorithms and/or populations.</p><p>Note that the genetic comparator is not necessarily the same as the boolean operator== and operator!= comparators. The genetic comparator returns 0 if the two individuals are the same, -1 if the comparison fails for some reason, and a real number greater than 0 indicating the degree of difference if the individuals are not identical but can be compared. It may be based on genotype or phenotype. The boolean comparators, on the other hand, indicate only whether or not two individuals are identical. In most cases, the boolean comparator can simply call the genetic comparator, but in some cases it is more efficient to define different operators (the boolean comparators are called much more often than the genetic comparators, especially if no diversity is being measured).</p><p> To work properly with the GAlib, you <i>must</i> define the following:</p><pre> MyGenome( -default-args-for-your-genome-constructor ) MyGenome(const MyGenome&) virtual GAGenome* clone(GAGenome::CloneMethod) const</pre> If your genome adds any non-trivial member data, you must define these:<pre> virtual ~MyGenome() virtual copy(const GAGenome&) virtual int equal(const GAGenome&) const</pre> To enable streams-based reading and writing of your genome, you should define these:<pre> virtual int read(istream&) virtual int write(ostream&) const</pre> When you derive a genome, don't forget to use the _evaluated flag to indicate when the state of the genome has changed and an evaluation is needed. If a member function changes the state of your genome, that member function should set the _evaluated flag to gaFalse.<p> Assign a default crossover, mutation, initialization, and comparison method so that users don't have to assign one unless they want to. </p><p>It is a good idea to define an identity for your genome (especially if you will be using it in an environment with multiple genome types running around). Use the DefineIdentity macro (defined in id.h) to do this in your class definition. The DefineIdentity 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 classes.</p><p>When run-time type information (RTTI) has stabilized across compilers, GAlib will probably use that instead of the Define/Declare identity macros.</p><br><br><br><a name="genome_testing"><br><strong>Genome Testing</strong><br></a><hr>Use the following program to test your genome. The basic idea here is to test incrementally in order to isolate problems as they arise. If your genome works with a small test program such as this one, it will function properly with any genetic algorithm in GAlib. (This is no guarantee, however, that your genome will help you find the solution to your problem. That is another matter entirely.)<pre>intmain() { MyGenome genome; // test default constructor (if we have one) cout << "genome after creation:\n" << genome << endl; genome.initialize(); // test the initializer cout << "genome after initialization:\n" << genome << endl; genome.mutate(); // test the mutator cout << "genome after mutation:\n" << genome << endl; MyGenome* a = new MyGenome(genome); // test copy constructor MyGenome* b = new MyGenome(genome); MyGenome* c = genome.clone(GAGenome::CONTENTS); cout << "clone contents:\n" << *c << "\n"; MyGenome* d = genome.clone(GAGenome::ATTRIBUTES); cout << "clone attributes:\n" << *d << "\n"; a->initialize(); b->initialize(); cout << "parents:\n" << *a << "\n" << *b << "\n"; MyGenome::DefaultCrossover(*a, *b, c, d); // test two child crossover cout << "children of crossover:\n" << *c << "\n" << *d << "\n"; MyGenome::DefaultCrossover(*a, *b, c, 0); // test single child crossover cout << "child of crossover:\n" << *c << "\n"; a->compare(*b); // test the comparator delete a; delete b; delete c; delete d; return 0;}</pre><br><br><br><a name="genome_initialization"><br><strong>Genome Initialization</strong><br></a><hr>The initializer takes a single argument: the genome to be initialized. The genome has already been allocated; the intializer only needs to populate it with appropriate contents.<p>Here is the implementation of an initializer for the GATreeGenome<int> class.</p><pre>voidTreeInitializer(GAGenome & c){ GATreeGenome<int> &child=(GATreeGenome<int> &)c;// destroy any pre-existing tree child.root(); child.destroy();// Create a new tree with depth of 'depth' and each eldest node containing// 'n' children (the other siblings have none). int depth=2, n=3, count=0; child.insert(count++,GATreeBASE::ROOT); for(int i=0; i<depth; i++){ child.eldest(); child.insert(count++); for(int j=0; j<n; j++) child.insert(count++,GATreeBASE::AFTER); }}</pre><br><br><br><a name="genome_mutation"><br><strong>Genome Mutation</strong><br></a><hr>The genome mutator takes two arguments: the genome that will receive the mutation(s) and a mutation probability. The exact meaning of the mutation probability is up to the designer of the mutation operator. The mutator should return the number of mutations that occured.<p>Most genetic algorithms invoke the mutation method on each newly generated offspring. So your mutation operator should base its actions on the value of the mutation probability. For example, an array of floats could flip a <i>pmut</i>-biased coin for each element in the array. If the coin toss returns true, the element gets a Gaussian mutation. If it returns false, the element is left unchanged. Alternatively, a single biased coin toss could be used to determine whether or not the <i>entire</i> genome should be mutated.</p><p>Here is an implementation of the flip mutator for the GA1DBinaryString class. This mutator flips a biased coin for each bit in the string.</p><pre>int GA1DBinStrFlipMutator(GAGenome & c, float pmut){ GA1DBinaryStringGenome &child=(GA1DBinaryStringGenome &)c; if(pmut <= 0.0) return(0); int nMut=0; for(int i=child.length()-1; i>=0; i--){ if(GAFlipCoin(pmut)){ child.gene(i, ((child.gene(i) == 0) ? 1 : 0)); nMut++; } } return nMut;}</pre><br><br><br><a name="genome_crossover"><br><strong>Genome Crossover</strong><br></a><hr>The crossover method is used by the genetic algorithm to mate individuals from the population to form new offspring. Each genome should define a default crossover method for the genetic algorithms to use. The <b>sexual</b> and <b>asexual</b> member functions return a pointer to the preferred sexual and asexual mating methods, respectively. The <b>crossover</b> member function is used to change the preferred mating method. The genome does not have a member function to invoke the crossover; only the genetic algorithm can actually perform the crossover.<p>Some genetic algorithms use sexual mating, others use asexual mating. If possible, define both so that your genome will work with either kind of genetic algorithm. If your derived class does not define a cross method, an error message will be posted whenever crossover is attempted.</p><p>Sexual crossover takes four arguments: two parents and two children. If one child is nil, the operator should be able to generate a single child. The genomes have already been allocated, so the crossover operator should simply modify the contents of the child genome as appropriate. The crossover function should return the number of crossovers that occurred. Your crossover function should be able to operate on one or two children, so be sure to test the child pointers to see if the genetic algorithm is asking you to create one or two children.</p><p>Here is an implementation of the two-parent/one-or-two-child single point crossover operator for fixed-length genomes of the GA1DBinaryStringGenome class.</p><pre>intSinglePointCrossover(const GAGenome& p1, const GAGenome& p2, GAGenome* c1, GAGenome* c2){ GA1DBinaryStringGenome &mom=(GA1DBinaryStringGenome &)p1; GA1DBinaryStringGenome &dad=(GA1DBinaryStringGenome &)p2; int n=0; unsigned int site = GARandomInt(0, mom.length()); unsigned int len = mom.length() - site; if(c1){ GA1DBinaryStringGenome &sis=(GA1DBinaryStringGenome &)*c1; sis.copy(mom, 0, 0, site); sis.copy(dad, site, site, len); n++; } if(c2){ GA1DBinaryStringGenome &bro=(GA1DBinaryStringGenome &)*c2; bro.copy(dad, 0, 0, site); bro.copy(mom, site, site, len); n++; } return n;}</pre><br><br><br><a name="genome_comparison"><br><strong>Genome Comparison</strong><br></a><hr>The comparison method is used for diversity calculations. It compares two genomes and returns a number that is greater than or equal to zero. A value of 0 means that the two genomes are identical (no diversity). There is no maximum value for the return value from the comparator. A value of -1 indicates that the diversity could not be calculated.<p>Here is the comparator for the binary string genomes. It simply counts up the number of bits that both genomes share. In this example, we return a -1 if the genomes are not the same length.</p><pre>floatGA1DBinStrComparator(const GAGenome& a, const GAGenome& b){ GA1DBinaryStringGenome &sis=(GA1DBinaryStringGenome &)a;⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -