📄 eooperators.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>Variation Operators</title></head><body text="#000000" link="#0000EF" vlink="#51188E" alink="#FF0000" background="beige009.jpg"><b><font color="#FF0000">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</a></font></font></b><br><hr WIDTH="100%"><br><b><font color="#FF0000">Local</font></b>: <a href="#introduction">Introduction</a>- <a href="#crossover">Crossover</a> - <a href="#mutation">Mutation</a>- <a href="#proportional_simple">Combinations</a> - <a href="#general">GeneralOperators</a> - <a href="#populators">Populators</a> - <a href="#general_combination">Generalcombinations</a>- <a href="#advanced_general">Advanced operators</a><br><hr WIDTH="100%"><center><h1><b><font color="#CC0000">Variation Operators</font></b></h1></center><a NAME="introduction"></a><b><font color="#000099"><font size=+2>VariationOperators</font></font></b><br>Variation operators modify the gnotype of individuals, or, equivalently,move them in the search space. In Evolutionary Algorithms, varitaion operatorsare almost always <b><font color="#FF6600">stochastic</font></b>, i.e.they are based on random numbers, or equivalently, perform random modificationsof their arguments. Variation operators are classified depending on thenumber of arguments they use and/or modify.<ul><li>Variation operators involving <b><font color="#FF6600">two individuals</font></b>are called <a href="#crossover">crossover operators</a>. They can eithermodify one of the parents according to the material of the other parent,or modify both parents. In EO, the former are called Binary operators andthe latter Quadratic operators.</li><li>Variation operators involving <b><font color="#FF6600">one single individual</font></b>are called <a href="#mutation">mutation operators.</a></li><li>Straightforward extensions of these simple operators allow to combine them:in<a href="#proportional_simple">proportional combinations</a>, one operatoris chosen among a given set of operators of same arity according to someweights.</li><li>In EO you can also define and use variation operators that generate anynumber of offspring from any number of parents (sometimes termed <b><font color="#FF6600">orgy</font></b>operators). They are called <a href="#general">general operators</a>.</li><li>However, the interface of such operators was designed for their use inside<a href="#general_combination">generalcombinations</a>: you can use <b><font color="#FF6600">proportional combination</font></b>,in which one operator is chosen among a given set of operators of samearity according to some weights, as for simple operators except that operatorsof different arities can be mixed, but you can also use <b><font color="#FF6600">sequentialcombinations</font></b>, where different operators are applied inturn with given probability. But you can also embed any of such combinationsat any depth.</li><li>The price to pay for that is that you must use an instermediate class toaccess the individuals, the <a href="#populators">eoPopulator</a> class.</li><li>Thanks to that class, it also become easy to design <a href="#advanced_general">advancedoperators</a>, such as crossover operators where the mate is chosen accordingto <b><font color="#FF6600">sexual preference</font></b> rather than fitness-basedpreferences.</li></ul><b><font color="#FF0000">Implementation</font></b><p>The basic idea of EO variation operators is that they operate on genotypesonly. Hence there should be generally no reference to anything relatedto the fitness within a variation operator. However, whenever the genotypeof an individual has been modified, it will be necessary to recompute itsfitness before any selection process. This is why <b><font color="#FF6600">allvariation operator return</font></b> a bool that indicates whether or notthe genotype argument has been modified or not.<p><b><font color="#FF0000">EO classes for variation operators</font></b>:<ul><li><b><font color="#FF0000">Base classes</font></b>: all variation operatorsin EO derive from the base (pure abstract) class <b><font face="Arial,Helvetica"><font size=+1><a href="../../doc/html/classeo_op.html">eoOp</a></font></font></b>(as usual, click to see the inheritance diagram). Four (also abstract)classes derive from <b><font color="#CC33CC">eoOp</font></b>, namely <b><font face="Arial,Helvetica"><font size=+1><a href="../../doc/html/classeo_mon_op.html">eoMonOp</a></font></font></b>(for <a href="#mutation">mutations</a>), <b><font face="Arial,Helvetica"><font size=+1><a href="../../doc/html/classeo_bin_op.html">eoBinOp</a></font></font></b>and <b><font face="Arial,Helvetica"><font size=+1><a href="../../doc/html/classeo_quad_op.html">eoQuadOp</a></font></font></b>(for <a href="#crossover">crossover</a>) and <b><font face="Arial,Helvetica"><font size=+1><a href="../../doc/html/classeo_gen_op.html">eoGenOp</a></font></font></b>for <a href="#general">all other operators</a>.</li><li><b><font color="#FF0000">Combined classes</font></b>: those classes combinevariation operators, and are variation operators by themselves: the simplevariation operators can be combined into the corresponding <b><font face="Arial,Helvetica"><font size=+1><a href="../../doc/html/classeo_prop_combined_mon_op.html">eoProportionalCombinedMonOp</a></font></font></b>,<b><font face="Arial,Helvetica"><font size=+1><a href="../../doc/html/classeo_prop_combined_bin_op.html">eoProportionalCombinedBinOp</a></font></font></b>and <b><font face="Arial,Helvetica"><font size=+1><a href="../../doc/html/classeo_pro_combined_quad_op.html">eoProportionalCombinedQuadOp</a></font></font></b>.The general operators <b><font color="#CC33CC">eoGenOp</font></b> can becombined into some <b><font face="Arial,Helvetica"><font color="#000000"><font size=+1><a href="../../doc/html/classeo_op_container.html">eoOpContainer</a></font></font></font></b>,abstract class with two implementations, <b><font face="Arial,Helvetica"><font color="#000000"><font size=+1><a href="../../doc/html/classeo_proportional_op.html">eoProportionalOp</a></font></font></font></b>and <b><font face="Arial,Helvetica"><font color="#000000"><font size=+1><a href="../../doc/html/classeo_sequential_op.html">eoSequentialOp</a></font></font></font></b></li><li><b><font color="#FF0000">Related classes</font></b>: General operatorsof class <b><font color="#CC33CC">eoGenOp</font></b> can only be used throughthe <b><font face="Arial,Helvetica"><font size=+1><a href="../../doc/html/classeo_populator.html">eoPopulator</a></font></font></b>class.</li></ul><hr WIDTH="100%"><a NAME="crossover"></a><b><font size=+1><font color="#000099">Simpleoperators: </font><font color="#FF0000">Crossover</font></font></b><p>The characteristic of crossover operators is that they involve two parents.However, there are crossover operators that generate two parents, and somethat generate one parent only, and both types are available in EO. Theformer type (2 --> 2) is termed quadratic crossover operator, and is implemantedin the <b><font color="#CC33CC">eoQuadOp</font></b> class; the latter type(2 --> 1) is termed binary operator and is implemanted in class <b><font color="#CC33CC">eoBinOp</font></b>.Both classes are, as usual, templatized by the type of individual theycan handle (see documentation for <b><font face="Arial,Helvetica"><font size=+1><a href="../../doc/html/classeo_bin_op.html">eoBinOp</a></font></font></b>and <b><font face="Arial,Helvetica"><font size=+1><a href="../../doc/html/classeo_quad_op.html">eoQuadOp</a></font></font></b>).<p><b><font color="#FF0000">Note:</font></b> Whereas it is straightforwardto create a binary crossover operator from a quadratic one (by discardingthe changes on the second parent), the reverse might prove impossible (imaginea binary crossover that simply merges the parents material: there is noway to generate two new parents from that!).<p><b><font color="#FF0000">Interfaces</font></b>:<br>The general approach in EO about simple variation operators is to perform<b><font color="#FF6600">in-placemodifications</font></b>, i.e. modifying the arguments rather than generatingnew (modified) individuals. This results in the following interfaces forthe functor objects eoBinOp and eoQuadOp:<p><b><tt><font color="#993300">bool operator()(EOT & , const EOT &) </font></tt></b> for eoBinOp (note the const)<br><b><tt><font color="#993300">bool operator()(EOT & , EOT &) </font></tt></b> for eoQuadOp<p>which you could have guessed from the inheritance diagrams up to theeoBF abstract class. You can also guess that only the first argument willbe modified by an oeBin object, while both arguments will be modified byan eoQuad object.<p><b><font color="#FF0000">Using crossover operators</font></b>:<br>Directly applying crossover operators is straightforward from the interfaceabove:<br><tt><font color="#993300"><b>eoBinOpDerivedClass<Indi> myBinOp(parameters);</b>// use constructor to pass</font></tt><br><tt><font color="#993300"><b>eoQuadOpDerivedClass<Indi> myQuadOp(parameters);</b>// any useful argument</font></tt><br><tt><font color="#993300"><b>Indi eo1= ..., eo2= ...; </b>//the candidates to crossover</font></tt><br><b><tt><font color="#993300">if (myBinOp(eo1, eo2))</font></tt></b><br><tt><font color="#993300"><b> { ... </b>// eo1 has been modified, <b>not</b> eo2</font></tt><br><b><tt><font color="#993300"> }</font></tt></b><br><tt><font color="#993300"><b>else ... </b>// none has been modified</font></tt><br><b><tt><font color="#993300">if (myQuadOp(eo1, eo2))</font></tt></b><br><tt><font color="#993300"><b> { ... </b>// both eo1 and eo2 have been modified</font></tt><br><b><tt><font color="#993300"> }</font></tt></b><br><tt><font color="#993300"><b>else ... </b>// none has been modified</font></tt><p>However, you will hardly have to actually apply operators to individuals,as operators are used within other classes, and are applied systematicallyto whole sets of individuals (e.g. that have already been selected, instandard generation-based evolutionary algorithms).<br>Hence the way to use such operators will more likely ressemble <a href="FirstRealGA.html#operators">this</a>if you are using for instance an SGA. See also the different ways thatare described below, encapsulating the operators into combined operatorsobjects.<p><a NAME="writing_crossover"></a><b><font color="#FF0000">Writing a crossoveroperator:</font></b><br>There are three things to modify in the template class definitionsprovided in the Templates directory for both <a href="../Templates/binCrossover.tmpl">binarycrossover</a> and <a href="../Templates/quadCrossover.tmpl">quadratic crossovers</a>(apart from the name of the class you are creating!)<ul><li>The <font color="#FF6600">constructor</font>, where you pass to the objectany useful parameter (see the private data at end of class definition).</li><li>The <font color="#FF6600">operator()</font> method, which performs theactual crossover.</li><li>The <font color="#FF6600">return value</font>, that should be <b><tt><font color="#993300">true</font></tt></b>as soon as at least one genotype has actually been modified. Otherwise,the <a href="eoEval.html#lazy">lazy fitness evaluation procedure</a> inEO might not know it should compute the fitness again and will keep theold value.</li></ul><hr WIDTH="100%"><a NAME="mutation"></a><b><font color="#000099"><font size=+1>Simpleoperators: </font></font><font color="#FF0000"><font size=+2>Mutation</font></font></b><br>Mutation operators modify one single individual. The correspondingEO class is called <b><font color="#CC33CC">eoMonOp</font></b>. and itsi as usual templatized by the type of individual it can handle (see documentation⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -