演化策略(英文版)

演化策略ESEvolutionaryStrategies程睿2015年12月12日2outlineBackgroundAlgorithmprinciple

Strategyparameter

Strategyparametertypes

Mutationofstrategyparameter

Adaptivestrategy

Evolutionarystrategyoperatorselectionoperatorcrossover

operatormutation

operator

Application

FunctionandCirclepackingproblemBackgroundBackgroundofES2/5/2023EvolutionarystrategywasproposedbyI.RechenberyandH.P.SchwefulatthetimetheyinvestigatedtheproblemoffluidforcequestioninwindtunnelwhentheystudiedinBerlinTechnologyUniversityinGermany1964.Thismethodproducesanoptimalsolutionbyusingtheideaofbiologicalvariationtoalterrandomlytheparametervalues.Theevolutionstrategyisspeciallydesignedforsolvingparameteroptimizationproblems,wheretheauto-adaptedmechanismisadopted.Theconcealedparallelismandthecommunity’sglobesearchingareitstwoprominentcharacteristic.Inaddition,ithasastrongrobustnessandalsohastheuniquesuperiorperformancewhensolvingsomecomplexnonlinearsystems.（1+1）策略算法2/5/2023第一個(gè)進(jìn)化策略是由于動(dòng)力學(xué)原理問(wèn)題而被發(fā)明的，這個(gè)（1+1）-進(jìn)化策略是最早講一個(gè)個(gè)體視為一個(gè)被優(yōu)化的決策向量x和策略向量δ構(gòu)成的元祖進(jìn)化算法。個(gè)體表示為如下元組：子代：通過(guò)如下的高斯擾動(dòng)產(chǎn)生：DevelopmentofES2/5/2023μ表示親代個(gè)數(shù)，λ表示子代個(gè)數(shù)（μ+λ）進(jìn)化策略：也被稱(chēng)為加法策略，進(jìn)化策略從μ個(gè)親代和其產(chǎn)生的λ個(gè)子代，下一代包括從μ個(gè)親代和其產(chǎn)生的λ個(gè)子代中選出最好的μ個(gè)個(gè)體作為新的親代。這是一種精英主義，最合適的親代存活到下一代（μ，λ）進(jìn)化策略：逗號(hào)策略，下一代包括λ個(gè)子代產(chǎn)生的最優(yōu)秀的μ個(gè)個(gè)體。這不是一種經(jīng)營(yíng)策略，相對(duì)于加法策略表現(xiàn)出較低的選擇壓力Algorithmprinciple

GeneralevolutionarystrategyalgorithmEvolutionarystrategyalgorithmproceedsasfollows.Confirmtheexpressionofthequestion.

(X,δ)=((x1,x2,··xi···,xn),(δ1,δ2,··δi,··,δn))(2)Producerandomlytheinitialcommunity(3)Calculatethefitnessvalueofeachinitialindividuals(4)Anewcolonyisgeneratedasfollows:(a)Recombine:Exchangetheinformationbasedonthetwofathergenerationindividualstoproducethenewindividual.(b)Mutation:δi’=δi·exp(l’·N(0,1)+l·Ni(0,1))xi’=xi+δi’·Ni(0,1)(c)Calculatingthefitnessvalueofeachnewindividuals.(d)Selection:usingthe(μ,λ)selectionstrategy(5)Carryingoutthestep(4)untiltheterminalconditionissatisfiedAlgorithmprinciple2/5/2023AlgorithmprincipleSimpleexample2/5/2023strategyparameterandadaptivestrategyStrategyparameterexpressionMutationofStrategyparameterAdaptivestrategyStrategyparameterexpression2/5/2023為了與突變操作相適應(yīng)，進(jìn)化策略有兩種表達(dá)方式。1)二元表達(dá)方式：這種表達(dá)方式中個(gè)體由目標(biāo)變量X和標(biāo)準(zhǔn)差σ兩部分組成，每部分又可以有n個(gè)分量，即：X和σ的關(guān)系為:τ為全局系數(shù)，常取1。2/5/2023Strategyparameterexpression2)三元表達(dá)方式。為了改善進(jìn)化策略的收斂速度，Schwefel在二元表達(dá)的基礎(chǔ)上引入第三個(gè)因子——坐標(biāo)旋轉(zhuǎn)角度α。個(gè)體的描述擴(kuò)展為(X,σ,α)，即：三者的關(guān)系為：αi——父代個(gè)體i分量與j分量間坐標(biāo)的旋轉(zhuǎn)角度；α’j——子代新個(gè)體i分量與j分量間坐標(biāo)的旋轉(zhuǎn)角度；β——系數(shù)，常取0.0873；zi——取決于σ’及α’的正態(tài)分布隨機(jī)數(shù)。MutationofStrategyparameter2/5/2023對(duì)于基因型的所有成分只使用了一個(gè)偏移參數(shù)，沒(méi)有旋轉(zhuǎn)角度，變異呈現(xiàn)為一個(gè)圓形策略參數(shù)表示為：MutationofStrategyparameter2/5/2023對(duì)于基因型的每個(gè)成分都有自己的偏移參數(shù)，沿坐標(biāo)軸有了不同梯度，變異呈現(xiàn)為一個(gè)橢圓偏移策略參數(shù)表示：MutationofStrategyparameter2/5/2023在之前偏移參數(shù)的基礎(chǔ)上，設(shè)置了旋轉(zhuǎn)角度。這種方法允許不同的自由度，變異呈現(xiàn)為一個(gè)旋轉(zhuǎn)后的橢圓旋轉(zhuǎn)角度表示為：Adaptivestrategy2/5/2023Evolutionarystrategyoperator

selectionoperatorcrossover

operatormutation

operatorSelectionoperator2/5/2023Eachevolutionaryalgorithmneedsagoalorientedselectionoperatorinordertoguidethesearchintopromisingregionsoftheobjectparameterspace.Selectionisthustheantagonisttothevariationoperators(alsoreferredtoasgeneticoperators)mutationandrecombination.Itgivestheevolutionadirection.SelectioninESisjustlikeanimalorplantbreeding:onlythoseindividualswithpromisingproperties,e.g.,highfitnessvalues(objectivefunctionvalues),getachanceofreproduction.Therearetwoversionsofthisselectiontechnique,dependingonwhetherornottheparentalinthisprocess,i.e.,plusselection,denotedby(μ+λ),andcommaselection,denotedby(μ,λ),respectively.20crossover

operator演化策略中的重組算子由兩個(gè)或多個(gè)父體得到一個(gè)后代。為了得到λ個(gè)后代，需要運(yùn)用重組算子λ次。1）離散重組假設(shè)兩個(gè)父體分別為：

則由這兩個(gè)父體重組得到的后代為其中：21crossover

operator演化策略中的重組算子由兩個(gè)或多個(gè)父體得到一個(gè)后代。為了得到λ個(gè)后代，需要運(yùn)用重組算子λ次。2）中值重組由兩個(gè)父體重組得到的后代為：

上面兩種重組可以以下列方式進(jìn)行推廣，為了得到后代：，對(duì)每個(gè)，從種群中隨機(jī)地抽取兩個(gè)父體x和y，然后對(duì)x和y的第i個(gè)分量進(jìn)行重組。

mutation

operator2/5/2023Hilderbrand提出的一種方向性變異，有特定的坐標(biāo)方向給出優(yōu)先權(quán)，方向性變異導(dǎo)致了一種不對(duì)稱(chēng)的概率分布，因此給定一維的非對(duì)稱(chēng)概率密度函數(shù)：Hansen等人提出的另一種坐標(biāo)系統(tǒng)無(wú)關(guān)的變異算子，對(duì)基因型同時(shí)使用偏移和變異，如下：mutation

operator2/5/2023方向性變異方法只使用偏移作為策略參數(shù)，需結(jié)合方向值和每個(gè)偏移給定策略參數(shù)，這里的策略參數(shù)都是自適應(yīng)的。ApplicationofEvolutionary

Strategy

TheminimumvalueforagivenequationCirclepackingproblemTheminimumvalueforagivenequation2/5/2023問(wèn)題描述：求所給函數(shù)的最小值求解過(guò)程：參數(shù)確定：種群大?。篘=50

終止代數(shù)：T=250

變異的隨機(jī)變量：采用正太分布N(0,1)的隨機(jī)變量適度評(píng)價(jià)：Fit(x)=f(x)選擇算子：在父代和父代產(chǎn)生的產(chǎn)生的400個(gè)個(gè)體中選擇50個(gè)適應(yīng)度最高的個(gè)體作為下一代的群體，即：（μ+λ）-ES交叉算子：該算法沒(méi)采用交叉的方法變異算子：該算法的變異算子為：

父代μ=50，子代λ=350，則：μ/λ=1/7