geneticlibrary.aspx.htm

Visual C++实现的基因遗传算法库源代码以演示程序Free Source Code for Genetic algorithm 2008年05月21日 C++, Windows, Win32

catalogues [catalogs are used to store and keep track of currently
available genetic operations]. </p>

<p>Except these general-purpose features, library provides some more GA
specific stuff at the lowest layer such as classes for keeping track of
statistical information of genetic algorithms and observing framework.
Interfaces for genetic operations and parameters' objects are also
defined at this layer. </p>

<p>Together these features provide common functionality that is used by
other, higher layers of the library. Classes of this layer are split in
several namespaces. </p>

<p>Mid-layer part is split in three namespaces, as shown at the
diagram. Majority of the core features of the library are implemented
at this layer. </p>

<p>First of all, <code>Chromosome</code> namespace contains set of
interfaces and classes used to represent chromosomes in the library and
to define their basic behavior in the system. This namespace contains
declaration of interfaces for four types of genetic operations:
crossover, mutation, fitness operation and fitness comparator. </p>

<p>The second namespace is <code>Population</code> namespace. Central
class of this namespace is class that manages population of
chromosomes, stores statistical information and tracks the best and the
worst chromosomes. Interfaces for selection, coupling, replacement and
scaling operations are defined in this namespace. </p>

<p>The last namespace, <code>Algorithm</code>, defines interfaces for
genetic algorithms and implements some of their basic behaviors. This
namespace also defines interface for operations that implements stop
criteria of the algorithms. </p>

<p>These two layers represent the core of the library. </p>

<p>The top layer of the library implements earlier mentioned genetic
operations, chromosomes representations and genetic algorithms. As
mentioned all built-in genetic operations are sorted in appropriate
catalogues. </p>

<p align="left"><img alt="Namespaces" src="geneticlibrary.aspx_files/ga_namespaces.png"> <br>Diagram - Namespaces </p>

<h3><a name="Chromosomes4">Chromosomes</a></h3>

<p>Chromosomes are central objects in a genetic algorithm. Chromosomes are defined by <code>GaChromosome</code> class in this library. </p>

<p align="left"><img alt="GaChromosome Class" src="geneticlibrary.aspx_files/GaChromosome.png"> <br>Diagram - <code>GaChromosome</code> class </p>

<p><code>GaChromosome</code> is interface for actual implementations of chromosomes. This class [interface] defines methods <code>Crossover</code>, <code>Mutation</code>, <code>CalculateFitness</code> and <code>CompareFitness</code> which represent previously described genetic operations [mutation, crossover, fitness operation and fitness comparator]. </p>

<p><code>MakeCopy</code> method represents virtual copy constructor.
New classes should override this method and it should return new
instance of chromosome's object. This method can copy entire chromosome
[setup and coded solution] or it can copy just chromosome's setup
[leaving empty encoding]. <code>MakeFromPrototype</code> method makes
new chromosome's object with the same setup as the current object but
it initializes encoding of the solutions randomly. </p>

<p>Each chromosome has defined parameters [such as crossover and mutation probability], these parameters are represented by <code>GaChromosomeParams</code> class. </p>

<p align="left"><img alt="GaChromosomeParams Class" src="geneticlibrary.aspx_files/GaChromosomeParams.png"> <br>Diagram - <code>GaChromosomeParams</code> class </p>

<p><code>GaChromosomeParams</code> defines mutation and crossover
probability, size of mutation and number of crossover points as well as
"improving-only mutation" flag. Default chromosome's parameters
initialized by default constructor are: </p>

<ul>
<li>mutation probability: 3% </li>

<li>mutation size: 1 [only one value of coded solution is mutated] </li>

<li>only improving mutations are accepted: yes </li>

<li>crossover probability: 80% </li>

<li>number of crossover points: 1 </li>
</ul>

<p>All parameter classes in the library inherit <code>GaParameters</code> class. </p>

<p align="left"><img alt="GaParameters Class" src="geneticlibrary.aspx_files/GaParameters.png"> <br>Diagram - <code>GaParameters</code> class </p>

<p>This class [interface] defines <code>Clone</code> method which
represents virtual copy constructor and it should return pointer new
parameters' object which is the copy of the current object. </p>

<p><code>GaChromosomes</code> class is interface and it does not
implements any behaviors. Still some basic features are common to all
chromosome types [storing chromosome parameters and fitness value];
these features are implemented by <code>GaDefaulChromosome</code> class. Beside parameters chromosome can have other configuration data [<strong>C</strong>hromosome <strong>C</strong>onfiguration <strong>B</strong>lock
or CCB] and these data are usually same for all chromosomes in the
population. Storing of chromosome's configuration data is defined by <code>GaChromosomeParamBlock</code> class. </p>

<p align="left"><img alt="GaDefaultChromosome and GaChromosomeParamsBlock Classes" src="geneticlibrary.aspx_files/GaDefaultChromosome.png"> <br>Diagram - <code>GaDefaultChromosome</code> and <code>GaChromosomeParamsBlock</code> classes </p>

<p><code>Crossover</code> and <code>Mutation</code> methods of <code>GaDefaultChromosome</code>
class performs these genetic operations only with probability defined
by chromosome's parameters. If the operations should be performed these
methods call <code>PerformCrossover</code> and <code>PerformMutation</code>. New chromosomes that inherits <code>GaDefaultChromosome </code>class should override <code>PerformCrossover</code> and <code>PerformMutation</code> not the <code>Crossover</code> and <code>Mutation</code> methods. </p>

<p>This class also introduces framework for improving-only mutations. Before the mutation operation is executed, <code>PrepareForMutation</code>
method is called, this method should backup old chromosome, and then
mutation is performed. After that, old fitness of chromosome [before
mutation] and new one are compared. If the mutation has improved
fitness it is accepted and <code>AcceptMutation</code> method is called, otherwise <code>RejectMutation</code>
method is called. If the "improving-only mutation" flag is not set,
mutations are immediately accepted without calls to these methods. </p>

<p>Crossover, mutation and fitness operations can be implemented by
inheriting the already defined class that implements specific type of
chromosomes. Then user can override <code>PerformCrossover</code> [or <code>Crossover</code>], <code>PerformMutation</code> [or <code>Mutation</code>] and <code>CalculateFitness</code> methods and implement specific operations for the targeted problem. </p>

<p>Genetic Algorithm Library provides another way to accomplish this.
These genetic operations can be defined and implemented in separated
classes. Then references to object of these classes [called functors]
can be stored in CCB. This allows user to change genetic operations at
runtime [which is not possible with previously described method]. </p>

<p align="left"><img alt="GaDynamicOperationChromosome Class" src="geneticlibrary.aspx_files/GaDynamicOperationChromosome.png"> <br>Diagram - <code>GaDynamicOperationChromosome</code> class and interfaces for genetic operations </p>

<p><code>GaDynamicOperationChromosome</code> overrides <code>PerformCrossover</code>, <code>PerformMutation</code>, <code>CalculateFitness</code> and <code>CompareFitnesses</code> methods and routes calls to functors of genetic operations stored in CCB. </p>

<p>CCB represented by <code>GaChromosomeOperationsBlock</code> class stores these functors. </p>

<p><code>GaCrossoverOperation</code> is interface for crossover operation. User defined classes should override <code><span class="code-keyword">operator</span>()</code>: </p>

<p>

</p><div class="SmallText" id="premain0" style="width: 100%; cursor: pointer;"><img preid="0" src="geneticlibrary.aspx_files/minus.gif" id="preimg0" width="9" height="9"><span preid="0" style="margin-bottom: 0pt;" id="precollapse0"> Collapse</span></div><pre style="margin-top: 0pt;" id="pre0"><span class="code-keyword">virtual</span> GaChromosomePtr <span class="code-keyword">operator</span> ()(
    <span class="code-keyword">const</span> GaChromosome* parent1,
    <span class="code-keyword">const</span> GaChromosome* parent2) <span class="code-keyword">const</span>;
</pre>

<p>The parameters are pointers to parents that are used by crossover
operation. Operator should return smart pointer to produced offspring
chromosome. </p>

<p><code>GaMutationOperation</code> is interface for mutation operation. User defined classes should override <code><span class="code-keyword">operator</span>()</code>: </p>

<p>

</p><div class="SmallText" id="premain1" style="width: 100%; cursor: pointer;"><img preid="1" src="geneticlibrary.aspx_files/minus.gif" id="preimg1" width="9" height="9"><span preid="1" style="margin-bottom: 0pt;" id="precollapse1"> Collapse</span></div><pre style="margin-top: 0pt;" id="pre1"><span class="code-keyword">virtual</span> <span class="code-keyword">void</span> <span class="code-keyword">operator</span> ()(GaChromosome* chromosome) <span class="code-keyword">const</span>;
</pre>

<p>This operator takes [as parameter] pointer to chromosome on which this operation should be performed. </p>

<p><code>GaFitnessOperation</code> is interface for fitness operation. User defined classes should override <code><span class="code-keyword">operator</span>()</code>: </p>

<p>

</p><div class="SmallText" id="premain2" style="width: 100%; cursor: pointer;"><img preid="2" src="geneticlibrary.aspx_files/minus.gif" id="preimg2" width="9" height="9"><span preid="2" style="margin-bottom: 0pt;" id="precollapse2"> Collapse</span></div><pre style="margin-top: 0pt;" id="pre2"><span class="code-keyword">virtual</span> <span class="code-keyword">float</span> <span class="code-keyword">operator</span> ()(<span class="code-keyword">const</span> GaChromosome* chromosome) <span class="code-keyword">const</span>;
</pre>

<p>This operator takes [as parameter] pointer to chromosome on which
this operation should be performed and returns calculated fitness value
of the chromosome. </p>

<p>The last operation is fitness comparator. Interface for fitness comparators are defined by <code>GaFitnessComparator</code> class. User defined classes should override <code><span class="code-keyword">operator</span>()</code>: </p>

<p>

</p><div class="SmallText" id="premain3" style="width: 100%; cursor: pointer;"><img preid="3" src="geneticlibrary.aspx_files/minus.gif" id="preimg3" width="9" height="9"><span preid="3" style="margin-bottom: 0pt;" id="precollapse3"> Collapse</span></div><pre style="margin-top: 0pt;" id="pre3"><span class="code-keyword">virtual</span> <span class="code-keyword">int</span> <span class="code-keyword">operator</span> ()
    <span class="code-keyword">float</span> fitness1,
    <span class="code-keyword">float</span> fitness2) <span class="code-keyword">const</span>;
</pre>

<p>This operator takes two fitness values as parameters and returns an integer: </p>

<ol>
<li><code>-<span class="code-digit">1</span></code> if the first fitness value is lower then the second </li>

<li><code><span class="code-digit">0</span></code> if these two values are equal </li>

<li><code><span class="code-digit">1</span></code> if the first value is higher then the second </li>
</ol>

<p>All classes that implements genetic operations in the library inherit <code>GaOperation</code> class. </p>

<p align="left"><img alt="GaOperation Class" src="geneticlibrary.aspx_files/GaOperation.png"> <br>Diagram - <code>GaOperation</code> class </p>

<p><code>MakeParameters</code> makes parameters' object that is needed
by the operation, and returns pointer to the object. If operation does
not require parameters, method can return <code>NULL</code> pointer. <code>CheckParameters</code> method checks validity of provided parameters and returns <code><span class="code-keyword">true</span></code> it they are valid or <code><span class="code-keyword">false</span></code> if they are invalid. All genetic operations must implement these two methods. </p>

<p>Genetic Algorithm Library is designed to use stateless objects of
genetic operations [functors]. Following that design, all built-in
operations are stateless, but the library can handle user defined
operations whose objects are not stateless. </p>

<h3><a name="Populations5">Populations</a></h3>
Population objects of genetic algorithm are represented in this library by <code>GaPopulation</code> class. 
<p align="left"><img alt="GaPopulation Class" src="geneticlibrary.aspx_files/GaPopulation1.png"> <br>Diagram - <code>GaPopulation</code> class </p>

<p>Population stores chromosomes and statistical information. Chromosomes in the population are represented by objects of <code>GaScaledChromosome</code>
class. Objects of this class bind chromosomes to population.
Chromosomes generally stores data which do not depend on population in
which chromosomes reside, but there is portion of information about
chromosomes which are dependant [such as scaled fitness or index of
chromosomes in population]. These data are members of <code>GaScaledChromosome</code> class. It makes sharing of chromosomes among populations easier and more [memory] efficient. </p>

<p>Chromosomes can be stored in population in sorted or unsorted order
[by fitness value - scaled or raw]. Whether the population should be
sorted or not depends on other parts of genetic algorithm [selection
operation for instance] and it is controlled by the parameters of
population. It is also easier to track the best and th