eolesson1.html

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

GA here: a simple selector, and a generational replacement. The <b><font face="Arial,Helvetica"><font size=+1><a href="../../doc/html/classeo_det_tournament_select.html">eoDetTournamentSelect</a></font></font></b>
has been chosen as a robust selection, and the generational replacement
(all parents are replaced by the offspring) is hard-coded in the eoSGA
<a href="#algorithm">algorithm</a>.</font></li>

<br>&nbsp;
<li>
<font color="#CC33CC"><b>Variation operators</b>:</font><font color="#000000">
in the simple algorithm considered here, individuals undergo </font><font color="#CC33CC">crossover</font><font color="#000000">
and </font><font color="#CC33CC">mutation</font><font color="#000000">.
In EO, these operators are (<a href="eoProgramming.html#functors">functor</a>)
objects of class</font> <b><font face="Arial,Helvetica"><font size=+1><a href="../../doc/html/classeo_quad_op.html">eoQuadOp</a></font></font></b>
(binary operator that modifies both its arguments) and <b><font face="Arial,Helvetica"><font size=+1><a href="../../doc/html/classeo_mon_op.html">eoMonOp</a></font></font></b>
(unary operator).&nbsp; These operators are applied in turn to all selected
parents, according to user-defined probabilities.&nbsp; These probabilities
are defined with all other <a href="#parametres">parameters</a>, and will
be passed to the <b><tt><font color="#FF6666"><font size=+1>eoSGA </font></font></tt></b><a href="#parametres">algorithm</a><font color="#000000">.&nbsp;
For more details on these classes, go to the <a href="eoOperators.html#crossover">algorithm-based
corresponding pages</a>, or to their respective documentation pages.</font></li>

<br>&nbsp;
<ul>
<li>
<a href="FirstBitGA.html#operators">Bit</a> The crossover <b><font face="Arial,Helvetica"><font size=+1><a href="../../doc/html/classeo1_pt_bit_crossover.html">eo1PtBitXover</a></font></font></b>
is the standard <font color="#CC33CC">1-point crossover</font>, and <b><font face="Arial,Helvetica"><font size=+1><a href="../../doc/html/classeo_bit_mutation.html">eoBitMutation</a></font></font></b>
is the standard <font color="#FF6600">bit-flip mutation</font> that randomly
flips all bits with a given probability <b><tt>P_MUT_PER_BIT.</tt></b></li>

<br><b><font color="#FF0000">Warning</font></b>: the <b><tt>P_MUT_PER_BIT</tt></b>
probability is an <font color="#FF6600">internal parameter</font> of the
<b><tt><font color="#CC33CC"><font size=+1>eoBinMutation</font></font></tt></b>,
it is <b><font color="#FF6600">NOT</font></b> the probability of mutation
at the individual level. EO corrects what can be viewed as an inconsistency
in Holland's original work, further used in Goldberg's book by separating
the probability of mutation for each individual (independent of the type
of mutation that will be applied) from the probability of flipping each
bit, which is specific of the bit-flip mutation.&nbsp; Hence, to run the
same algorithm as Goldberg's SGA, the mutation probability (at individual
level) is 1, and the probability of flipping each bit is <b><tt>P_MUT_PER_BIT.</tt></b>
<li>
<a href="FirstRealGA.html#operators">Real</a> The crossover <b><font face="Arial,Helvetica"><font size=+1><a href="../../doc/html/classeo_segment_crossover.html">eoSegmentCrossover</a></font></font></b>
is the standard <font color="#CC33CC">segment crossover</font> for real-valued
vectors, that chooses a point randomly on the segment between both parents
(also termed <font color="#CC33CC">BLX-0</font>). <b><font face="Arial,Helvetica"><font size=+1><a href="../../doc/html/classeo_uniform_mutation.html">eoUniformMutation</a></font></font></b>
is the <font color="#CC33CC">uniform mutation</font> for real-valued vectors
that chooses a new value for each variable uniformly on an interval centered
on the parent value. The width of the interval is an <font color="#FF6600">internal
parameter</font> of the object, here called <b><tt>EPSILON</tt></b>.</li>

<br>&nbsp;</ul>

<li>
<b><font color="#3366FF">Stopping criterion:</font></b><font color="#000000">
Specify a </font><font color="#3366FF">maximum number of generations</font><font color="#000000">
to run (<a href="FirstBitGA.html#stop">Bit</a> - <a href="FirstRealGA.html#stop">Real</a>):
the simplest of all stopping criteria at the moment, using an object of
a sub-class of class </font><b><font face="Arial,Helvetica"><font color="#3366FF"><font size=+1><a href="../../doc/html/classeo_continue.html">eoContinue</a></font></font></font></b><font color="#000000">.</font></li>

<br>&nbsp;
<li>
<a NAME="algorithm"></a><b><font color="#FF6666">The algorithm: </font></b><font color="#000000">the
simple algorithm that is used here, called&nbsp; </font><b><tt><font color="#FF6666"><font size=+1>eoSGA
</font></font></tt></b><font color="#000000">requires
as parameters a </font><font color="#FF6600">selector</font><font color="#000000">,
a </font><font color="#FF6600">crossover</font><font color="#000000"> and
the associated </font><font color="#FF6600">crossover rate</font><font color="#000000">,
a </font><font color="#FF6600">mutation</font><font color="#000000"> and
the associated </font><font color="#FF6600">mutation rate,</font><font color="#000000">
and a </font><font color="#FF6600">stopping criterion</font><font color="#000000">.
Take a look at the corresponding
<a href="eoSGA.html#constructor">constructor</a>
of the class </font><b><tt><font color="#FF6666"><font size=+1>eoSGA</font></font></tt></b><font color="#000000">:
it only initializes its <a href="eoSGA.html#parametres">private data</a>
with the parameters. Now look at the <a href="eoSGA.html#generation">operator()</a>
method - the one that is called in the code for <a href="FirstBitGA.html#generation">FirstBitGA</a>
or <a href="FirstRealGA.html#generation">FirstRealGA</a> - and you'll find
out that is is as simple as it sounds.</font></li>

<br>&nbsp;
<li>
<b><font color="#3366FF">Output</font></b><font color="#000000">: After
running the algorithm, output the sorted final population (<a href="FirstBitGA.html#final_output">Bit</a>
- <a href="FirstRealGA.html#final_output">Real</a>) - and look at the best
individual: this is the result of the algorithm.</font></li>

<br>&nbsp;
<li>
<b><font color="#990000">Main body:</font></b><font color="#000000"> for
technical reasons (intercepting the exceptions), we need a main like this
one (<a href="FirstBitGA.html#main">Bit</a> - <a href="FirstRealGA.html#main">Real</a>).,
and you should not touch it unless you know what you are doing. Simply
note that this main calls the function main_function, which we have been
discussing up to now!</font></li>
</ul>

<h3>

<hr WIDTH="100%"><a NAME="exercise1"></a><font color="#000099">Exercise
1: maximize your own function</font></h3>
This is very easy - if your search space is that of bitstring or of unbounded
real numbers.
<ul>
<li>
Go to the tutorial directory, and <font color="#FF6600">copy</font> the
program you want to modify onto <b><tt><font color="#663300">mytest.cpp.</font></tt></b></li>

<li>
<font color="#FF6600">Edit</font> <b><tt><font color="#990000">mytest.cpp</font></tt></b>
with any text editor:</li>

<li>
<font color="#FF6600">Modify</font> the fitness function itself (<a href="FirstBitGA.html#evalfunc">binary_value</a>
in <font color="#FF6666"><b><tt>FirstBitGA</tt></b><font face="Courier New,Courier">,</font></font><a href="FirstRealGA.html#evalfunc">real_value</a>
in&nbsp; <font color="#FF6666"><b><tt>FirstRealGA</tt></b><font face="Courier New,Courier">)</font></font></li>

<li>
<font color="#FF6600">Compile</font> the program by typing <b><tt><font color="#990000">make
mytest</font></tt></b> at system prompt</li>

<li>
<font color="#FF6600">Run</font> the new program by entering the command
<b><tt><font color="#990000">mytest</font></tt></b>
at system prompt.</li>
</ul>

<h3>

<hr WIDTH="100%"><a NAME="exercise2"></a><font color="#000099">Exercise
2: check the differences between both programs</font></h3>
Go and take a look at the code for these programs <font color="#000000">(<a href="FirstBitGA.html">Bit</a>
- <a href="FirstRealGA.html">Real</a>)</font>. Use the symbolic representation
of an Evolutionary Algorithm (you should understand that figure now, otherwise
go <a href="eoIntro.html">there</a> and come back) to understand how each
part of the EA is coded. Try to spot the differences between both codes:
there are not so many!
<br>After you've tried that alone, take a look at the <a href="Firstmerge.html">solution</a>
:-)
<h3>

<hr WIDTH="100%"><a NAME="exercise3"></a><font color="#000099">Exercise
3: change the selection procedure</font></h3>
This is rather straightforward ... if you know what other types of selection
are available!
<br>At the moment, let's only consider only the following simple ones:
<ul>
<li>
You already know the <font color="#FF6600">tournament selection</font></li>

<br><font color="#FF0000">Syntax:&nbsp; </font><tt><font color="#009900"><b>eoDetTournamentSelect&lt;Indi>
select(T_SIZE);&nbsp;&nbsp; </b>// T_SIZE in [2,POP_SIZE)</font></tt>
<li>
Try the well-known <font color="#FF6600">roulette wheel</font></li>

<br>&nbsp;<font color="#FF0000">Syntax:&nbsp;</font>&nbsp;&nbsp; <b><tt><font color="#009900">eoProportionalSelect&lt;Indi>
select;</font></tt></b>
<li>
Or the <font color="#FF6600">stochastic binary tournament</font></li>

<br><font color="#FF0000">Syntax:&nbsp; </font><b><tt><font color="#009900">eoStochTournamentSelect&lt;Indi>
select(RATE);&nbsp;</font></tt></b><tt><font color="#009900">&nbsp;&nbsp;&nbsp;
// RATE in ]0.5,1]</font></tt>
<li>
and of course the <font color="#FF6600">random</font> selection should
give bad results!</li>

<br><font color="#FF0000">Syntax:&nbsp; </font><b><tt><font color="#009900">eoRandomSelect&lt;Indi>
select;</font></tt></b></ul>
Note that all these classes of eoObjects are derived from the abstract
class
<b><font face="Arial,Helvetica"><font size=+1><a href="../../doc/html/classeo_select_one.html">eoSelectOne.</a></font></font></b>
To find out exactly how each procedure selects the individuals, read the
corresponding <a href="eoEngine.html#selection">component-based page</a>.
<p>
<hr WIDTH="100%"><b><font color="#000099"><font size=+2>Lessons learned:</font></font></b>
<ul>
<li>
in EO, all actions are performed by <a href="eoProgramming.html#functors">functor
objects</a> (this section is the last time in this tutorial that there
is a direct link to the <a href="eoProgramming.html">EO Programming hints</a>
page - though the link at top and bottom of all pages will remain there).</li>

<li>
in EO, all object you will usually need to manipulate are <a href="eoProgramming.html#templates">templatized</a><b><font color="#FF6600">
w.r.t. the type of the individual</font></b> you are handling.</li>

<li>
The type of the individual is itself <a href="eoProgramming.html#templates">templatized</a><b><font color="#FF6600">
w.r.t. the type of fitness</font></b> (double by default).</li>

<li>
In EO (actually, in EC!) <font color="#CC33CC">initialization and variation</font>
operators are <font color="#999900">representation</font>-dependent, while
the <font color="#009900">evolution engine</font> is <font color="#999900">representation</font>-independent
(well, like any rule, this one does have some exceptions).</li>

<li>
Changing the <font color="#990000">fitness function</font>, or the <font color="#009900">selection
procedure</font> inside the generational GA evolution engine is straightforward.</li>

<li>
remember, all <font color="#FF6600">solutions</font> to exercises are in
the same sub-dir of dir Tutorial than the lesson itself (see <a href="NoWay.html">here</a>).</li>
</ul>

<hr WIDTH="100%"><a href="eoLesson2.html">Lesson 2</a> -
<a href="eoTutorial.html">Tutorial
main page</a> -
<a href="eoTopDown.html">Algorithm-Based</a> - <a href="eoBottomUp.html">Component-Based</a>
- <a href="eoProgramming.html">Programming hints</a> - <font face="Arial,Helvetica"><font size=+1><a href="../../doc/html/index.html">EO
documentation</a></font></font>
<br>
<hr>
<address>
<a href="mailto:[e-mail]">Marc Schoenauer</a></address>

<br><!-- Created: Fri Nov  3 18:49:12 CET 2000 --><!-- hhmts start -->Last
modified: Fri Nov 3 18:49:12 CET 2000<!-- hhmts end -->
</body>
</html>