geneticlibrary.aspx.htm

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

<li><a href="#Catalogues8">Catalogues</a> </li>

<li><a href="#RandomNumberGenerators9">Random Number Generators</a> </li>

<li><a href="#ChromosomeRepresentations10">Chromosome Representations</a> </li>

<li><a href="#Built-inFitnessComparators11">Built-in Fitness Comparators</a> </li>

<li><a href="#Built-inCrossoverOperations12">Built-in Crossover Operations</a> </li>

<li><a href="#Built-inMutationOperations13">Built-in Mutation Operations</a> </li>

<li><a href="#Built-inCouplingOperations14">Built-in Coupling Operations</a> </li>

<li><a href="#Built-inReplacementOperations15">Built-in Replacement Operations</a> </li>

<li><a href="#Built-inScalingOperations16">Built-in Scaling Operations</a> </li>

<li><a href="#Built-inStopCriteriaOperations17">Built-in Stop Criteria Operations</a> </li>

<li><a href="#Built-inGeneticAlgorithms18">Built-in Genetic Algorithms</a> </li>
</ul>
</li>

<li><a href="#Examples19">Examples</a> 
<ul>
<li><a href="#Example1:%3Cem%3Efindingminimumoff%28x,y%29=5*x*sin%28x%29+1.1*y*sin%28y%29;x,yininterval%280,10%29%3C/em%3E20">Example 1: <em>finding minimum of f(x, y) = 5*x*sin(x) + 1.1*y*sin(y); x, y in interval (0, 10)</em></a> </li>

<li><a href="#Example2:%3Cem%3Epatternmatching%3C/em%3E21">Example 2: <em>pattern matching</em></a> </li>

<li><a href="#Example3:%3Cem%3ETravelingSalespersonProblem%3C/em%3E22">Example 3: <em>Traveling Salesperson Problem</em></a> </li>

<li><a href="#Example4:%3Cem%3EClassSchedule%3C/em%3E23">Example 4: <em>Class Schedule</em></a> </li>
</ul>
</li>

<li><a href="#Portability,CompilingandLinkingtheGeneticAlgorithmLibrary24">Portability, Compiling and Linking the Genetic Algorithm Library</a> 
<ul>
<li><a href="#WindowsPlatform25">Windows Platform</a> </li>

<li><a href="#Linux,MacOSX,Solarisand*BSDPlatforms26">Linux, Mac OS X, Solaris and *BSD Platforms</a> </li>

<li><a href="#Portability27">Portability</a> </li>
</ul>
</li>
</ul>
</li>
</ul>

<h2><a name="GeneticAlgorithms1">Genetic Algorithms</a></h2>

<p>Genetic algorithms operate on set of possible solutions. Because of
random nature of the genetic algorithm, solutions found by the
algorithm can be good, poor or infeasible [defective, erroneous] so
there should be a way to specify how good that solution is. This is
done by assigning fitness value [or just fitness] to the solution.
Chromosomes represent solutions within the genetic algorithm. Two basic
component of chromosome are coded solution and its fitness value. </p>

<p>Chromosomes are grouped into population [set of solutions] on which
the genetic algorithm operates. In each step [generation] genetic
algorithm selects chromosomes form population [selection is usually
based on fitness value of chromosome] and combines them to produce new
chromosomes [offspring]. These offspring chromosomes form new
population [or replace some of the chromosomes in the existing
population] in hope that new population will be better then previous.
Populations keep track of the worst and the best chromosomes and stores
additional statistical information which can be used by genetic
algorithm to determine stop criteria. </p>

<p>Chromosome in some way stores solution which it represents. This is
called representation [encoding] of the solution. There are number of
probabilities way to represent solution in such way that it is suitable
for genetic algorithm [binary, real number, vector of real number,
permutations, and so on] and they are mostly depend on nature of
problem. </p>

<p align="left"><img alt="Chromosome representation" src="geneticlibrary.aspx_files/ga_representation1.png"> <br>Diagram - Chromosome representations [for maximization of single-parameter function] </p>

<p align="left"><img alt="Chromosome representation" src="geneticlibrary.aspx_files/ga_representation2.png"> <br>Diagram - Chromosome representations [Traveling Salesman Problem] </p>

<p>Genetic algorithms produce new chromosomes [solutions] by combining
existing chromosomes. This operation is called crossover. Crossover
operation takes parts of solution encodings from two existing
chromosomes [parents] and combines them into single solution [new
chromosome]. This operation depends on chromosome representation and
can be very complicated. Although general crossover operations are easy
to implement, building specialized crossover operation for specific
problem can greatly improve performance of the genetic algorithm. </p>

<p align="left"><img alt="Crossover Operation Examples" src="geneticlibrary.aspx_files/ga_crossover1.png"> <br>Diagram - Crossover operation examples </p>

<p>Before genetic algorithm finishes production of new chromosome,
after it performs crossover operation, it performs mutation operation.
Mutation operation makes random but small changes to encoded solution.
This prevents falling of all solution into local optimum and extends
search space of the algorithm. Mutation as well as crossover operation
depends on chosen representation. </p>

<p align="left"><img alt="Mutation Operation Examples" src="geneticlibrary.aspx_files/ga_mutation1.png"> <br>Diagram
- Mutation operation examples [swap mutation is performed over the
first and overt the second invert mutation is performed] </p>

<p>Crossover and mutation operations are not always performed when
producing new chromosome. If crossover is not performed the genetic
algorithm produce new chromosome by copying on of the parents. Rates of
crossover and mutation operations are called crossover probability and
mutation probability. The crossover probability is usually high [about
80%] and mutation probability should be relatively low [about 3%, but
for some problems higher probability gives better results]. Higher
mutation probability can turn the genetic algorithm in a random search
algorithm. </p>

<p>The last operations defined by genetic algorithms used to manipulate
the chromosomes are fitness operation and fitness comparator. Fitness
operation measures quality of produced solution [chromosome]. This
operation is specific to problem and it actually tells genetic
algorithm what to optimize. Fitness comparators [as their name
suggests] are used to compare chromosomes based their fitness.
Basically fitness comparator tells genetic algorithm whether it should
minimize or maximize fitness values of chromosomes. </p>

<p>Choosing parents for production of new chromosomes from population
is called selection. Selection can be based on many different criterias
but it is usually based on fitness value. The idea behind this is to
select the best chromosomes for parents in hope that combining them
will produce better offspring chromosomes. But selecting only the best
chromosome has one major disadvantage, all chromosomes in population
will start to look the same very quickly. This narrows exploration
space, pushes genetic algorithm into local optimum, and prevents
genetic algorithm to find possibly better solutions that reside in
inaccessible area of exploration space. To preserver diversity of
chromosomes [and wider exploration space] within the population,
selection operations usually introduce factor of randomness in the
selection process. Some implementations of selection operation are
entirely random. </p>

<p>One problem may occur with selection operations that are based on
fitness values. When there is a chromosome with dominant fitness value,
it will be selected most of the times thus it will cause problem
similar to previous. To prevent this fitness values can be scaled
[transformed] to lower the difference between dominant chromosome(s)
and the rest of population [this allows other chromosomes to be
selected]. There are many ways to transformation fitness value. Usually
they are implemented by applying mathematical transformation to fitness
value, but there other methods like ranking based scaling that use rank
[based on raw fitness values of chromosomes] of chromosome as scaled
fitness value. </p>

<p align="left"><img alt="Scaling Fitness Values" src="geneticlibrary.aspx_files/ga_scaling1.png"> <br>Diagram - Scaling fitness value [shows selection probability of chromosomes] </p>

<p>Coupling operation defines how the selected chromosomes [parents]
are paired for mating [mating is done by performing crossover operation
over paired parents and applying mutation operation to newly produced
chromosome]. This operation gives better control over the production of
new chromosomes but can it be skipped and new chromosomes can be
produced as the selection operation selects parents from the
population. </p>

<p align="left"><img alt="Coupling Operation Flowchart" src="geneticlibrary.aspx_files/ga_coupling_flow.png"> <br>Diagram - Coupling operation flowchart </p>

<p align="left"><img alt="Selection Operation with no Soupling Operation Flowchart" src="geneticlibrary.aspx_files/ga_selection_flow.png"> <br>Diagram - Selection operation without coupling operation flowchart </p>

<p>Next step performed by genetic algorithm is introduction of new
chromosomes into population. Offspring chromosomes can form new
population and replace the entire [previous] population
[non-overlapping population] or they can replace only few chromosomes
in the current population [overlapping population]. For overlapping
populations, replacement operation defines which chromosomes are
removed [usually the worst chromosomes in current population] from the
current population and which offspring chromosomes are inserted. By
replacing chromosomes there is a chance that the genetic algorithm will
loose the best chromosome[s] [found so far]. To prevent this concept of
elitism is introduced into genetic algorithms. Elitism guarantees that
the best chromosome[s] from the current generation is going to survive
to next generation. </p>

<p>Algorithm performs previously described steps one by one in sequence
and when they have been performed it is said that one generation has
passed. At the end of each generation genetic algorithm checks stop
criteria. Because the nature of the genetic algorithms, most of the
times it is not clear when the algorithm should stop, so criteria is
usually based on statistical information such as number of generation,
fitness value of the best chromosome or average fitness value of
chromosomes in population, duration of evolution process... </p>

<p align="left"><img alt="Genetic Algorithm Flowchart" src="geneticlibrary.aspx_files/ga_flow1.png"> <br>Diagram - Flowchart of a genetic algorithm [overlapping population coupling operation] </p>

<p align="left"><img alt="Genetic Algorithm Flowchart" src="geneticlibrary.aspx_files/ga_flow2.png"> <br>Diagram - Flowchart of a genetic algorithm [overlapping population without coupling operation] </p>

<p align="left"><img alt="Genetic Algorithm Flowchart" src="geneticlibrary.aspx_files/ga_flow3.png"> <br>Diagram - Flowchart of a genetic algorithm [non-overlapping population with coupling operation] </p>

<h2><a name="GeneticAlgorithmLibrary2">Genetic Algorithm Library</a></h2>

<p>This is brief introduction in the design and the structure of the
Genetic Algorithm Library. The library is set of C++ classes that
represent building blocks of genetic algorithms. </p>

<h3><a name="StructureoftheLibrary3">Structure of the Library</a></h3>

<p>Next diagrams illustrate basic structure of Genetic Algorithm Library. </p>

<p align="left"><img alt="Genetic Algorithm Library Basic Structure" src="geneticlibrary.aspx_files/ga_structure.png"> <br>Diagram - Structure of Genetic Algorithm Library </p>

<p>The first layer mainly contains classes that are not directly
related to genetic algorithms but are essential for their
implementation. Genetic Algorithm Library implements random number
generators, a set of classes for platform-independent threading and
synchronization, smart pointers for easier management of memory
[primarily for automatic management of memory used by chromosomes] and