eoengine.html

这是linux下的进化计算的源代码。 === === === === === === === === === === === ===== check latest news at http:

become the next generation. It is an <b><tt><font color="#993300">eoMergeReduce(eoPlus,
eoTruncate)</font></tt></b>.</li>

<li>
<b><tt><font color="#009900">eoEPReplacement</font></tt></b>, used in th<font color="#000000">e
Evolutionary Programming historical </font>algorithm, does an EP stochastic
tournament among parents + offspring. It is an <b><tt><font color="#993300">eoMergeReduce(eoPlus,
eoEPReduce)</font></tt></b> and its constructor requires as argument T,
the size of the tournament (unsigned int).</li>
</ul>

<li>
<b><tt><font color="#009900">eoReduceMerge</font></tt></b> is another important
type of eoReplacement: the parents are first reduced, and then merged with
the offspring. Note that the parent population is reduced of the exact
number of offspring.</li>

<br>Though not mandatory, it is implicitely assumed that few offspring
have been generated. Hence, all derived replacement procedures of class
<b><tt><font color="#009900">eoReduceMerge</font></tt></b>
are termed <b><tt><font color="#009900">eoSSGAxxx</font></tt></b>, as they
are the ones to use in SteadyState Genetic Algorithm engine. This gives
the following <font color="#FF6600">instances of eoReduceMerge</font>:
<ul>
<li>
&nbsp;<b><tt><font color="#009900">eoSSGAWorseReplacement</font></tt></b>
in which the worse parents are killed and replaced by all offsprings (no
additional argument needed);</li>

<li>
<b><tt><font color="#009900">eoSSGADetTournamentReplacement</font></tt></b>
in which parents to be killed are chosen by a (reverse) determinitic tournament.
Additional parameter (in the constructor) is the tournament size, an <b><tt><font color="#993300">unsigned
int</font></tt></b>.</li>

<li>
<b><tt><font color="#009900">eoSSGAStochTournamentReplacement</font></tt></b>
in which parents to be killed are chosen by a (reverse) stochastic tournament.
Additional parameter (in the constructor) is the tournament rate, a <b><tt><font color="#993300">double</font></tt></b>.</li>
</ul>

<li>
<a NAME="SADreplacement"></a><b><tt><font color="#009900">eoSurviveAndDie</font></tt></b>
replacement strategies are a generalization of both the above that allows
strong elitist and eugenism in both the parent population and the offspring
population. The <b><tt><font color="#009900"><a href="#SAD">eoSurviveAndDie</a></font></tt></b>
building block takes one population, kills the worse and moves the best
to some safe place.&nbsp; The corresponding replacements apply an <b><tt><font color="#009900">eoSurviveAndDie</font></tt></b>
to the parents, another one to the offspring, and finally merges the remaining
parents and offspring before reducing the resulting population to the right
size. Available instances of <b><tt><font color="#009900">eoSurviveAndDieReplacement</font></tt></b>
are limited todayto the <b><tt><font color="#009900">eoDeterministicSaDReplacement</font></tt></b>,
the&nbsp; that uses a deterministic MergeReduce.</li>

<br>&nbsp;
<p>&nbsp;
<br>&nbsp;
<br>&nbsp;
<p><b><font color="#FF0000">Note</font></b>: The basic use (and initial
motivation) for <b><tt><font color="#009900">eoSurviveAndDie</font></tt></b>
takes 2 arguments, an eoMergeReduce and a number of surviving parents.
It starts by copying the best parents to the new populations, then merges
the remaining parents with the offspring before reducing to the number
of remaining seats in the new population.</ul>

<hr WIDTH="50%">
<br><a NAME="weakelitism"></a><b><font color="#000099">Replacement: </font><font color="#FF0000">Adding
(weak) elitism</font></b>
<p>You can add what is called <font color="#FF6600">weak elitism</font>
to any replacement by encapsulating it into an <b><tt><font color="#009900">eoWeakElitismReplacement</font></tt></b>
object. Weak elitism ensures that the overall <font color="#FF6600">best
fitness</font> in the population <font color="#FF6600">will never decrease</font>:
if the best fitness in the new population is less than the best fitness
of the parent population, then the best parent is added back to the new
population, replacing the worse.
<p>Within EO, this is very easy to add:
<p>First, declare your replacement functor (here, generational, but it
can be any replacement object):
<br><b><tt><font color="#009900">eoGenerationalReplacement&lt;Indi> genReplace;</font></tt></b>
<br>Then wrap the weak elitism around it:
<br><b><tt><font color="#009900">eoWeakElitismReplacement&lt;Indi> replace(genReplace);</font></tt></b>
<br>and use now replace as your replacement procedure within your algorithm.
<p><font color="#FF0000">Note</font>: of course, adding weak elitism to
an elitist replacement makes no sense - but will not harm either :-)
<br>
<hr WIDTH="50%">
<br><b><font color="#000099">Replacement: </font><font color="#FF0000">Test
file</font></b>
<p>The file <b><tt><font color="#993300">t-eoReplacement</font></tt></b>
in the <b><font color="#FF6600">test directory</font></b> implements all
above replacement procedures within a very simple and easy-to-monitor Dummy
EO class.
<p>
<hr WIDTH="100%">
<br><a NAME="general"></a><b><font color="#000099"><font size=+2>General
Replacement: eoReduceMergeReduce</font></font></b>
<p>In an attempt to unify all the well-known replacements, plus most of
the less-known-though-often-used, the <b><tt><font color="#009900">eoReduceMergeReduce</font></tt></b>
replacement has been designed, and supersedes all of the above instances.
<br>It allows to implement <b><font color="#FF0000">strong elistism</font></b>
(i.e. some parents survive, whatever their fitness and that of the offspring),
as well as multiple weak elistism (the best parents are put back in the
next population if they outperform the best offspring).
<p>Basically, an <b><tt><font color="#009900">eoReduceMergeReduce</font></tt></b>
starts by eventually preserving the (strong) elite parents, proceeds by
reducing both the parent and offspring populations, merges those populations,
and eventually reduces the resulting populations (augmented with the elite
parents) to the right size. Last, the weak elitism is taken care of if
necessary.
<br>The following image, taken from the graphical interface of EASEA, somehow
demonstrates the different parameters of an <b><tt><font color="#009900">eoReduceMergeReduce.</font></tt></b>
<br>
<hr WIDTH="50%">
<br><b><font color="#000099">eoReduceMergeReduce: </font><font color="#FF0000">The&nbsp;
interface</font></b>
<br>Of course the interface is that of eoReplacement. Let's concentrate
on the constructor.
<p>The constructor takes 6 arguments:
<ol>
<li>
<b><tt><font color="#993300">eoHowMany elite</font></tt></b> determines
the number of parents to be treated as elite (actual behavior determined
by next parameter) using the <a href="#howmany">eoHowMany</a> behavior.</li>

<li>
<b><tt><font color="#993300">bool strongElitism</font></tt></b> tells whether
the elite above corresponds to strong (true) or false(weak) elitism.</li>

<br><b><font color="#FF0000">Note</font></b>: the case of no elitism is
obtained by setting elite to 0
<li>
<b><tt><font color="#993300">eoHowMany reducedParents </font></tt></b>gives
the number of parents remaining after reducing them</li>

<br><b><font color="#FF0000">Note</font></b>: 0 means that no parent survive
(except the possible elite), as in <b><tt><font color="#009900">eoCommaReplacement</font></tt></b>
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
-1 is used inside <b><tt><font color="#009900">eoSSGAReplacement</font></tt></b>s
(one parent is killed to make room for the newborn)
<li>
<b><tt><font color="#993300">eoReduce&lt;EOT> &amp; reduceParents</font></tt></b>
indicates how the parents will be reduced (see <a href="#reduce">available
instances</a>).</li>

<li>
<b><tt><font color="#993300">eoHowMany reducedOffspring </font></tt></b>gives
the number of offspring remaining after reducing them</li>

<br><b><font color="#FF0000">Note</font></b>: 0 is impossible (no evolution!!!)
<li>
<b><tt><font color="#993300">eoReduce&lt;EOT> &amp; reduceOffspring</font></tt></b>
indicates how the offspring will be reduced (see <a href="#reduce">available
instances</a>).</li>

<li>
<b><tt><font color="#993300">eoReduce&lt;EOT> &amp; reduceFinal</font></tt></b>
indicates how the merged reduced-parents/reduced-offspring will be reduced
(see <a href="#reduce">available instances</a>).</li>

<br><b><font color="#FF0000">Note</font></b>: the number of individuals
remaining after that reduction is of course the original size of the population.</ol>
All popular evolution engines use some replacement procedure that can be
viewed as an instance of an <b><tt><font color="#009900">eoReduceMergeReduce</font></tt></b>.
<br>Moreover, a <b><font color="#FF0000">parser-based</font></b> input
of a general&nbsp; is proposed in file do/make_checkpoint.h.
<br>
<hr WIDTH="100%">
<br><a NAME="popular"></a><b><font color="#000099"><font size=+2>Popular
evolution engines</font></font></b>
<p>The most popular evolution engines are listed below, together with the
way to use them in EO. If you don't find your particuler algorithm, please
send it to us, and we might include it here! In the following, P will denote
the number of individuals in the initial population.
<ul>
<li>
<a NAME="GGA"></a><b><font color="#000099">Generational Genetic Algorihtm</font></b><font color="#000000">:
popularized by Holland (75) and Goldberg (89), it uses</font></li>

<br><font color="#FF0000">Number of offspring:&nbsp;</font><font color="#000000">
P</font>
<br><font color="#FF0000">Selection:</font><font color="#000000"> Proportional
(the historical roulette wheel) </font><b><font color="#FF6600">when maximizing
a positive scalar fitness</font></b><font color="#000000">, ranking or
tournament (stochatic or deterministic) in all cases.</font>
<br><font color="#FF0000">Replacement:</font><font color="#000000"> Generational.</font>
<br><font color="#FF0000">Remark:</font><font color="#000000"> You could
use also the </font><b><tt><font color="#009900">eoCommaReplacement</font></tt></b><font color="#000000">,
with exactly the same result as there are as many offspring as we need
indiviudals in the next population. And using the </font><b><tt><font color="#009900">eoSSGAWorseReplacement</font></tt></b><font color="#000000">
would also give the same result, but would be very inefficient!</font>
<br><font color="#000000">You can also add <a href="#weakelitism">weak
elitism</a> to preserve the best individual.</font>
<li>
<a NAME="SSGA"></a><b><font color="#000099">Steady-State Genetic Algorithm</font></b><font color="#000000">:
widely used in GA/GP community</font></li>

<br><font color="#FF0000">Number of offspring:&nbsp;</font><font color="#000000">
small (historically, 1)</font>
<br><font color="#FF0000">Selection:</font><font color="#000000"> tournament
(you can use ranking or proportional, but it will be rather inefficient).</font>
<br><font color="#FF0000">Replacement:</font><font color="#000000"> An
eoSSGAxxxReplacement.</font>
<br><font color="#FF0000">Remark:</font><font color="#000000"> You can
also use the eoPlusReplacement, but you divert from the original SSGA</font>
<li>
<a NAME="ESPlus"></a><b><font color="#000099">(MU+Lambda)-Evolution Strategy</font></b><font color="#000000">:
The elitist ES strategy (Rechenberg 71 and Schwefel 81)</font></li>

<br><font color="#FF0000">Number of offspring:&nbsp;</font><font color="#000000">
Any</font>
<br><font color="#FF0000">Selection:</font><font color="#000000"> eoDetSelect
(batch deterministic).</font>
<br><font color="#FF0000">Replacement:</font><font color="#000000"> eoPlusReplacement</font>
<br><font color="#FF0000">Remark:</font><font color="#000000"> You could
also use eoEPReplacement, to smoothen the selective pressure during replacement,
thus getting close to EP evolution engine</font>
<li>
<a NAME="ESComma"></a><b><font color="#000099">(MU,Lambda)-Evolution Strategy</font></b><font color="#000000">:
The non-elitist ES strategy</font></li>

<br><font color="#FF0000">Number of offspring:&nbsp;</font><font color="#000000">
> P</font>
<br><font color="#FF0000">Selection:</font><font color="#000000"> eoDetSelect
(batch deterministic).</font>
<br><font color="#FF0000">Replacement:</font><font color="#000000"> eoCommaReplacement</font>
<br><font color="#FF0000">Remark:</font><font color="#000000"> You can
also add <a href="#weakelitism">weak elitism</a> to preserve the best individual
- though you'd probably use the plus strategy if you want (strong) elitism.</font>
<li>
<a NAME="EP"></a><b><font color="#000099">Evolutionary Programming</font></b><font color="#000000">:
The historical method of L. Fogel (65)</font></li>

<br><font color="#FF0000">Number of offspring:&nbsp;</font><font color="#000000">
P</font>
<br><font color="#FF0000">Selection:</font><font color="#000000"> eoDetSelect
(batch deterministic). Every individual reproduces exactly once.</font>
<br><font color="#FF0000">Replacement:</font><font color="#000000"> eoEPReplacement,
though one historical replacement was the determnistic replacement - i.e.
in EO the eoPlusReplacement).</font>
<br><font color="#FF0000">Remark:</font><font color="#000000"> Close to
an (P+P)-ES</font>
<li>
<a NAME="General"></a><font color="#FF0000">You name it :-)</font><font color="#000000">:
you can of course choose whatever combination you like - respecting a few
constraints and common-sense remarks. For instance, eoProportionalSelect
should be used only when maximizing a positive fitness, eoCommaReplacement
requires more offspring than parents, and, over all, existing EO algorithms
wirk with fixed size population - and it is your responsability to use
a cmbinatino of selection/replacement that fulfills this requirement (or
to create your own eoAlgo that handles varying size populations).</font></li>
</ul>

<hr WIDTH="100%">
<br><a NAME="tournament"></a><b><font color="#000099"><font size=+2>Tournaments</font></font></b>
<p>Tournaments are an easy and quick way to <b><font color="#FF6600">select</font></b>
individuals within a population based on simple comparisons. Though usually
based on fitness comparisons, they can use any comparison operator.
<br>In EO, there are two variants of tournaments used to select one single
individual, namely <b><tt><font color="#009900">Deterministic Tournament</font></tt></b>
and <b><tt><font color="#009900">Stochastic Tournament</font></tt></b>,