演化策略(英文版)

演化策略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第一個進(jìn)化策略是由于動力學(xué)原理問題而被發(fā)明的，這個（1+1）-進(jìn)化策略是最早講一個個體視為一個被優(yōu)化的決策向量x和策略向量δ構(gòu)成的元祖進(jìn)化算法。個體表示為如下元組：子代：通過如下的高斯擾動產(chǎn)生：DevelopmentofES2/5/2023μ表示親代個數(shù)，λ表示子代個數(shù)（μ+λ）進(jìn)化策略：也被稱為加法策略，進(jìn)化策略從μ個親代和其產(chǎn)生的λ個子代，下一代包括從μ個親代和其產(chǎn)生的λ個子代中選出最好的μ個個體作為新的親代。這是一種精英主義，最合適的親代存活到下一代（μ，λ）進(jìn)化策略：逗號策略，下一代包括λ個子代產(chǎn)生的最優(yōu)秀的μ個個體。這不是一種經(jīng)營策略，相對于加法策略表現(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á)方式中個體由目標(biāo)變量X和標(biāo)準(zhǔn)差σ兩部分組成，每部分又可以有n個分量，即：X和σ的關(guān)系為:τ為全局系數(shù)，常取1。2/5/2023Strategyparameterexpression2)三元表達(dá)方式。為了改善進(jìn)化策略的收斂速度，Schwefel在二元表達(dá)的基礎(chǔ)上引入第三個因子——坐標(biāo)旋轉(zhuǎn)角度α。個體的描述擴(kuò)展為(X,σ,α)，即：三者的關(guān)系為：αi——父代個體i分量與j分量間坐標(biāo)的旋轉(zhuǎn)角度；α’j——子代新個體i分量與j分量間坐標(biāo)的旋轉(zhuǎn)角度；β——系數(shù)，常取0.0873；zi——取決于σ’及α’的正態(tài)分布隨機(jī)數(shù)。MutationofStrategyparameter2/5/2023對于基因型的所有成分只使用了一個偏移參數(shù)，沒有旋轉(zhuǎn)角度，變異呈現(xiàn)為一個圓形策略參數(shù)表示為：MutationofStrategyparameter2/5/2023對于基因型的每個成分都有自己的偏移參數(shù)，沿坐標(biāo)軸有了不同梯度，變異呈現(xiàn)為一個橢圓偏移策略參數(shù)表示：MutationofStrategyparameter2/5/2023在之前偏移參數(shù)的基礎(chǔ)上，設(shè)置了旋轉(zhuǎn)角度。這種方法允許不同的自由度，變異呈現(xiàn)為一個旋轉(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演化策略中的重組算子由兩個或多個父體得到一個后代。為了得到λ個后代，需要運(yùn)用重組算子λ次。1）離散重組假設(shè)兩個父體分別為：

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

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

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

mutation

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

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

Strategy

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

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

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

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