演化策略(英文版)

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

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

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

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

mutation

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

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

Strategy

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

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

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

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