📄 eoengine.html
字号:
<!doctype html public "-//w3c//dtd html 4.0 transitional//en"><html><head> <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> <meta name="GENERATOR" content="Mozilla/4.78 [en] (X11; U; Linux 2.4.7-10 i686) [Netscape]"> <title>Genetic Engine</title></head><body text="#000000" link="#0000EF" vlink="#51188E" alink="#FF0000" background="beige009.jpg"><b><font color="#CC0000">General: </font></b><a href="eoTopDown.html">Algorithm-Based</a>- <a href="eoBottomUp.html">Component-Based</a> - <a href="eoProgramming.html">Programminghints</a> - <b><font face="Arial,Helvetica"><font size=+1><a href="../../doc/html/index.html">EOdocumentation<hr WIDTH="100%"></a></font></font><font color="#CC0000">Local: </font></b><a href="#introduction">Introduction</a> - <a href="#selection">Selection</a> - <a href="#replacement">Replacement</a>- <a href="#general">General Replacement</a> - <a href="#popular">Popularevolution engines</a> - <a href="#tournament">Tournaments</a> - <a href="#merge">Merge</a>- <a href="#reduce">Reduce</a> - <a href="#howmany">HowMany</a> - <a href="#SAD">SurviveAndDie</a><hr WIDTH="100%"><center><h1><b><font color="#CC0000">Evolution Engine</font></b></h1></center><hr WIDTH="100%"><br><a NAME="introduction"></a><b><font color="#000099"><font size=+2>EvolutionEngines</font></font></b><p>The term <b><font color="#FF6600">evolution engine</font></b> denotesthe different parts of an Evolutionary Algorithm that simulate the Darwinism:<center><p><i><font color="#009900">The fittest individuals are more likely toreproduce and survive.</font></i></center><p>Darwinism takes place in two different phases of an EA, though in many<a href="#popular">popularvariants</a>, only one phase is activated.<p><a href="#selection">Selection</a> is the Darwinistic choice of parentsthat will be allowed to <b><font color="#009900">reproduce</font></b><font color="#CC33CC">.</font><br><a href="#replacement">Replacement</a> takes place after reproduction,and is the Darwinistic choice of those individuals that will <b><font color="#009900">survive</font></b>,i.e. become the parents of the next generation.<p>Both selection and replacement will be discussed in turn, before somehelper classes that are used within selection and replacement proceduresare presented.<p><hr WIDTH="100%"><a NAME="selection"></a><b><font color="#000099"><font size=+2>Selection</font></font></b><p>The very beginning of the generation loop is the selection phase, wheresome individuals from the population are chosen to become the parents,to be later modified by the variation operators and become the offspring.This is the first step of the <font color="#009900">artificial Darwinism</font>,where the <i><font color="#FF6600">fittest individuals are allowed to reproduce</font></i>.<br>Conceptually, there are two distinct ways to choose the lucky ones:one by one from the very same population (i.e. with replacement), whichmeans that at the extreme the same individual can be chosen every time;or as a whole, in some sort of batch procedure. Of course, repeated selectionof one individual results in a batch selection!<p>There are hence two basic EO classes for selection: <font color="#009900">eoSelectOne</font>and <font color="#009900">eoSelect</font>, with different interfaces.<br><hr WIDTH="50%"><br><b><font color="#000099">eoSelectOne: </font><font color="#FF0000">Theinterface</font></b><p>The abstract class for selection of a single individual from a populationis <font color="#009900">eoSelectOne</font>, and the interface for its<tt><font color="#993300">operator()</font></tt>is<center><p><b><tt><font color="#993300">const EOT & operator()(const eoPop<EOT>&_parents)</font></tt></b></center><p>which you could have guessed from the inheritance tree for class <b><font face="Arial,Helvetica"><font size=+1><a href="../../doc/html/classeo_select_one.html">eoSelectOne</a></font></font></b>.,as you see there that <font color="#009900">eoSelectOne</font> derivesfrom <tt><font color="#993300">class eoUF<const eoPop<EOT>&,const EOT&></font></tt>.<br>This means that it takes <font color="#FF6600">1 population</font>(without the right to modify it - see the <b><tt><font color="#993300">const</font></tt></b>keyword in argument) and returns a const reference to an individual (again,the <b><tt><font color="#993300">const</font></tt></b> keyword ensuresthat nothing will happen to the individual in the population - rememberit returns a reference).<br><hr WIDTH="50%"><br><b><font color="#000099">eoSelectOne: </font><font color="#FF0000">Instances</font></b><ul><li><b><tt><font color="#009900">eoDetTournamentSelect</font></tt></b> usesthe <a href="#detTournament">(deterministic) tournament</a> to choose oneindividual. Its constructor has one parameter, the tournament size (integer>= 2).</li><li><b><tt><font color="#009900">eoStochTournamentSelect</font></tt></b> usesthe <a href="#stochTournament">binary stochastic tournament</a> to chooseone individual. Its constructor has one parameter, the tournament rate(real in [0.5,1]).</li><li> <b><tt><font color="#009900">eoProportionalSelect</font></tt></b>is the original <font color="#FF6600">roulette wheel</font> selection:each parent is selected with a probability proportional to its fitness.</li><li><b><tt><font color="#009900">eoRandomSelect</font></tt></b> is the <font color="#FF6600">random</font>selection and should give bad results! At the moment, it selects one individualuniformly, but it would be easy to use any probability distribution.</li></ul><hr WIDTH="50%"><br><b><font color="#000099">eoSelect: </font><font color="#FF0000">Theinterface</font></b><p>The abstract class for batch selection of a whole set of individualsfrom a population is <font color="#009900">eoSelect</font>, and the interfacefor its<tt><font color="#993300">operator()</font></tt> is<center><p><b><tt><font color="#993300">void operator()(const eoPop<EOT>&_source, eoPop<EOT>& _dest)</font></tt></b></center><p>which you could have guessed from the inheritance tree for class <b><font face="Arial,Helvetica"><font size=+1><a href="../../doc/html/classeo_select.html">eoSelect</a></font></font></b>.,as you see there that <font color="#009900">eoSelect</font> derives from<tt><font color="#993300">classeoBF<const eoPop<EOT>&, eoPop<EOT>&, void></font></tt>.<br>This means that it takes <font color="#FF6600">2 populations</font>,and fills the second one with individuals from the first one without modifyingit (see the <b><tt><font color="#993300">const</font></tt></b> keyword).This raises two questions:<ul><li>How does it know how many individuals to select?</li><li>How to use repeated selection of one individual (see above the <font color="#009900">eoSelectOne</font>class)?</li></ul><hr WIDTH="50%"><br><b><font color="#000099">eoSelect: </font><font color="#FF0000">HowMany</font></b><p>There are two ways an can derive the number of individuals ithas to select: either it is a fixed number, or it is some percentage ofthe source population size (any positive real number). In both case, thismust be passed to the constructor. In most instances, however, the constructorwill accept a real number (double) and a boolean indicating whether thisreal number should be used as an absolute integer or as a rate, thanksto the <a href="#howmany">eoHowMany</a> class.<p><b><font color="#FF0000">Note</font></b>: an <font color="#009900">eoSelect</font>can select more individuals than there are in the original population.It is the job of the <font color="#009900">replacement</font> to ensurethat the population size does not grow along the generations.<p><hr WIDTH="50%"><b><font color="#000099">eoSelectMany: </font><font color="#FF0000">EncapsulatingeoSelectOne</font></b><p>It is clear that repeated selection of a single individual is a wayto do batch selection. This is why it is possible to encapsulate an objectof class <font color="#009900">eoSelectOne</font> into an object of class<font color="#009900">eoSelect</font>using the class <font color="#009900">eoSelectMany</font>. Class <font color="#009900">eoSelectMany</font>is derived from class <font color="#009900">eoSelect</font> and takes inits constructor an <font color="#009900">eoSelectOne</font> (plus the numberof individuals it should select, according to the <a href="#howmany">eoHowMany</a>paradigm).<p><b><font color="#FF0000">Note</font></b>: some procedures for selectinga single individual require some pre-processing of the whole populationthat takes place before any selection, and will be repeated identicallyfor every individual. The encapsulation of an into an allowsto call such technical processing only once through the use of method setupof class . This method does nothing by default, but is mandatory<br><hr WIDTH="50%"><br><b><font color="#000099">eoSelect: </font><font color="#FF0000">Otherinstances</font></b><ul><li><b><tt><font color="#009900">eoDetSelect</font></tt></b> selects individuals<b><font color="#FF6600">deterministically</font></b>,i.e. starting from the best ones down to the worse ones. If the total numberto select is less than the size of the source populations, the best individualsare selected once. If more individuals are needed after reaching the bottomof the population, then the selection starts again at top. It the totalnumber required is N times that of the source size, all individuals areselected exactly N times.</li></ul>No other instances of <font color="#009900">eoSelect</font> that are notencapsualtions of <font color="#009900">eoSelectOne</font> procedures areavaiable as of today (Jan. 4 2001).<br><hr WIDTH="100%"><br><a NAME="replacement"></a><b><font color="#000099"><font size=+2>Replacement</font></font></b><p>The replacement phase takes plac<font color="#000000">e after the birthof all offspring through </font>variation operators. This is the secondstep of the <font color="#009900">artificial Darwinism</font>, where the<i><font color="#FF6600">fittestindividuals are allowed to survive</font></i>.<br>It can also be viewed on the algorithmic side as closing the generationloop, i.e. building the population that will be the initial populationof next generation. That population will be <font color="#FF6600">builtupon the old parents and the new-born offspring</font>. In all algorithmsthat come up with EO, the <font color="#FF6600">population size</font>is supposed to be <font color="#FF6600">constant</font> from one generationto the next one - though nothing stops you from writing an algorithm withvarying population size.<br><hr WIDTH="50%"><br><b><font color="#000099">Replacement: </font><font color="#FF0000">Theinterface</font></b><p>The abstract class for replacement procedures is the functor class<font color="#009900">eoReplacement</font>,and the interface for its <tt><font color="#993300">operator()</font></tt>is<center><p><b><tt><font color="#993300">void operator()(eoPop<EOT>& _parents,eoPop<EOT>& _offspring)</font></tt></b></center><p>which you could have guessed from the inheritance tree for class <b><font face="Arial,Helvetica"><font size=+1><a href="../../doc/html/classeo_replacement.html">eoReplacement</a></font></font></b>.,as you see there that <font color="#009900">eoReplacement</font> derivesfrom <tt><font color="#993300">class eoBF<eoPop<EOT>&, eoPop<EOT>&,void></font></tt>.<br>This means that it takes <font color="#FF6600">2 populations</font>(called, for obvious anthropomorphic reasons, _parents and _offspring :-)and is free to modify both, but the resulting population should be placedin the first argument (usually called_parents) to close the loop and goto next generation.<br><hr WIDTH="50%"><br><b><font color="#000099">Replacement: </font><font color="#FF0000">Instances</font></b><ul><li><b><tt><font color="#009900">eoGenerationalReplacement </font></tt></b>Thisis the most straightforward replacement, called <font color="#FF6600">generationalreplacement</font>: all offspring replace all parents (used in Holland'sand Goldberg's traditional GAs). It takes no argument, and supposesthat offspring and parents are of the same size (but does not check!).</li><br> <li><a NAME="SSGA"></a><b><tt><font color="#009900">eoMergeReduce</font></tt></b>This is one the basic types of replacement in EO. It has two major steps,<font color="#FF6600">merging</font>both populations of parents and offspring, and <font color="#FF6600">reducing</font>this big population to the right size. It <font face="Arial,Helvetica"><font size=+1><a href="../../doc/html/classeo_merge_reduce.html">containstwo objects</a></font></font> of respective types <b><font color="#009900"><a href="#merge">eoMerge</a></font></b>and <b><font color="#009900"><a href="#reduce">eoReduce</a></font></b>and you can probably guess what each of them actually does :-)</li><br> <p> <br> <br> <p>Available <font color="#FF6600">instances of eoMergeReduce</font> replacementinclude<ul><li><b><tt><font color="#009900">eoCommaReplacement</font></tt></b>, one ofthe two standard strategies in <font color="#000000">Evolution Strategies</font>,<b><font color="#FF6600">selectsthe best offspring</font></b>. It is an<b><tt><font color="#993300">eoMergeReduce(eoNoElitism,eoTruncate)</font></tt></b>.</li><li><b><tt><font color="#009900">eoPlusReplacement</font></tt></b>, the otherstandar<font color="#000000">d Evolution Startegies repla</font>cement,where <b><font color="#FF6600">the best from offspring+parents</font></b>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -