演化策略(英文版)

演化策略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第一个进化策略是由于动力学原理问题而被发明的，这个（1+1）-进化策略是最早讲一个个体视为一个被优化的决策向量x和策略向量δ构成的元祖进化算法。个体表示为如下元组：子代：通过如下的高斯扰动产生：DevelopmentofES2/5/2023μ表示亲代个数，λ表示子代个数（μ+λ）进化策略：也被称为加法策略，进化策略从μ个亲代和其产生的λ个子代，下一代包括从μ个亲代和其产生的λ个子代中选出最好的μ个个体作为新的亲代。这是一种精英主义，最合适的亲代存活到下一代（μ，λ）进化策略：逗号策略，下一代包括λ个子代产生的最优秀的μ个个体。这不是一种经营策略，相对于加法策略表现出较低的选择压力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和σ的关系为:τ为全局系数，常取1。2/5/2023Strategyparameterexpression2)三元表达方式。为了改善进化策略的收敛速度，Schwefel在二元表达的基础上引入第三个因子——坐标旋转角度α。个体的描述扩展为(X,σ,α)，即：三者的关系为：αi——父代个体i分量与j分量间坐标的旋转角度；α’j——子代新个体i分量与j分量间坐标的旋转角度；β——系数，常取0.0873；zi——取决于σ’及α’的正态分布随机数。MutationofStrategyparameter2/5/2023对于基因型的所有成分只使用了一个偏移参数，没有旋转角度，变异呈现为一个圆形策略参数表示为：MutationofStrategyparameter2/5/2023对于基因型的每个成分都有自己的偏移参数，沿坐标轴有了不同梯度，变异呈现为一个椭圆偏移策略参数表示：MutationofStrategyparameter2/5/2023在之前偏移参数的基础上，设置了旋转角度。这种方法允许不同的自由度，变异呈现为一个旋转后的椭圆旋转角度表示为：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提出的一种方向性变异，有特定的坐标方向给出优先权，方向性变异导致了一种不对称的概率分布，因此给定一维的非对称概率密度函数：Hansen等人提出的另一种坐标系统无关的变异算子，对基因型同时使用偏移和变异，如下：mutation

operator2/5/2023方向性变异方法只使用偏移作为策略参数，需结合方向值和每个偏移给定策略参数，这里的策略参数都是自适应的。ApplicationofEvolutionary

Strategy

TheminimumvalueforagivenequationCirclepackingproblemTheminimumvalueforagivenequation2/5/2023问题描述：求所给函数的最小值求解过程：参数确定：种群大小：N=50

终止代数：T=250

变异的随机变量：采用正太分布N(0,1)的随机变量适度评价：Fit(x)=f(x)选择算子：在父代和父代产生的产生的400个个体中选择50个适应度最高的个体作为下一代的群体，即：（μ+λ）-ES交叉算子：该算法没采用交叉的方法变异算子：该算法的变异算子为：

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