第6章-其他进化算法教案课件

1第六章其他进化算法一.前言二.进化策略三.进化规划四.遗传规划五.差分进化2进化算法的起源和发展遗传算法（GA）是上世纪六七十年代美国密西根大学Holland教授及其学生提出和发展起来的进化策略（EvolutionaryStrategy,ES）是上世纪60年代柏林技术大学的两名学生Rechenberg和Schwefel在风洞试验中最初提出的进化规划（EvolutionaryProgramming,EP）是上世纪六十年代美国学者Fogel首先提出的一.前言3进化算法的起源和发展由于GA，ES和EP是由不同领域的研究人员分别独立提出的，在相当长的时期内相互之间没有正式沟通1990年，GA才开始与ES和EP有所交流；1992年ES和EP这两个领域的研究人员首次接触到对方的研究工作通过交流，研究人员发现这些算法所依赖的思想都是基于自然界的自然遗传和自然选择等生物进化思想，具有惊人的相似之处一.前言4进化算法的起源和发展于是，GA，ES和EP等算法被统称为进化算法（EvolutionaryAlgorithms,EAs），相应的研究领域被统称为进化计算后来，遗传规划（GeneticProgramming,GP）和差分进化（DifferentialEvolutionary，DE）也被纳入到EA的范畴之内一.前言5总体框架一.前言begin

initializethepopulationwithrandomindividuals;evaluateeachindividual;

repeatselect

parents;recombinepairsofparents;mutatetheresultingoffspring;evaluatethenew-generatedindividuals;selectindividualsforthenextgeneration;

untilastopconditionismetend6国际学术会议情况1985年，在美国召开了第一届遗传算法国际会议，并成立了国际遗传算法学会；1992年，在美国举行了进化规划第一届年会；1999年这两个国际会议合并为GeneticandEvolutionaryComputationConference（GECCO），这是进化算法在

美国召开的最主要国际会议1990年，在欧洲召开了第一届ParallelProblemSolvingFromNature（PPSN）国际会议，成为在欧洲召开的进化算法方面的最主要国际会议一.前言7国际学术会议情况1993年，进化计算领域内第一个国际期刊《EvolutionaryComputation》在美国问世1994年，IEEE神经网络委员会主持召开了第一届进化计算国际会议（IEEEConferenceonEvolutionaryComputation,CEC），这是进化算法领域最顶级的学术会议IEEE进化计算国际会议、IEEE神经网络国际会议和IEEE模糊系统国际会议每三年在同一地点同时召开，统称为IEEE世界计算智能大会（IEEEConferenceonComputationIntelligence,WCCI）一.前言8引言ES最初用于风洞实验中物体外形的参数优化ES强调个体级的行为变化ES的几种形式：(1+1)-ES,(μ+1)-ES,(μ+λ)-ES以及(μ,λ)-ES二.进化策略9(1+1)-ES早期ES的种群中只包含一个个体，并且只使用变异操作，变异后的个体与其父代进行比较，选择较好的作为新的父代存在的问题：各维定常的标准差降低收敛效果单点搜索效率不高（尽管可以理论上证明能够收敛到全局最优点）二.进化策略10(1+1)-ES在每个新个体的特征中增加了一个自适应参数，这样每个解矢量中不仅包含了其数值信息，而且还包含了变异信息二.进化策略11(μ+1)-ES在这种ES中，父代有μ个个体(μ>1)，并且引入重组算子，使父代个体组合出新的个体重组算子类似于GA中的重组运算对重组的新个体执行变异操作，见(1+1)-ES将变异后的个体与父代μ个个体进行比较，如果优于父代的最差个体，则替代后者成为下一代种群的新个体二.进化策略12(μ+1)-ES特点：只产生一个新个体使用种群增添了重组算子二.进化策略13(μ+λ)-ES和(μ,λ)-ES(μ+λ)-ES中，μ个父代产生λ个子代，所有个体都参与生存竞争，最好的μ个作为下一代的父代(μ,λ)-ES中，μ个父代产生λ个子代(λ>μ)，只有λ个子代参与生存竞争，从中选择最好的μ个作为下一代的父代优劣性分析：(μ+λ)-ES保留旧个体可能是过时的可行解，妨碍算法向最优方向发展；而(μ,λ)-ES舍弃全部旧个体，使算法始终从新的基础上全方位进化二.进化策略14(μ+λ)-ES和(μ,λ)-ES优劣性分析：(μ+λ)-ES保留旧个体可能是局部最优解，误导算法收敛，导致“早熟”；而(μ,λ)-ES选择丢弃所有优良旧个体，可以避免“早熟”(μ+λ)-ES保留旧个体的同时也将进化参数σ保留下来，不利于自适应机制；而(μ,λ)-ES恰恰相反，有利于促进这种自适应调整二.进化策略实践也证明，(μ,λ)-ES优于(μ+λ)-ES，成为当前进化策略的主流15引言EP最初用于研究人工智能系统EP强调种群级的行为变化EP注重父代与子代表现行为的联系，而不是像GA那样侧重于父代与子代遗传细节（基因及其遗传操作）的联系三.进化规划16算法流程图三.进化规划begin

initializeapopulationPwithrandomindividuals;evaluateeachindividualinP;

repeat

foreachindividualxinP

dogenerateaoffspringindividualx’inP’viamutatingx;

endfor

evaluateeachindividualinP’;generatethenewPatthenextgenerationfromP+P’;

untilastopconditionismetend17标准形式变异方式自适应调整依赖于适应值产生μ个个体，对每个个体执行变异操作，从2μ个个体中选择出μ个个体组成新的种群三.进化规划18引言GA不能描述层次化的问题四.遗传规划19引言GA不能描述层次化的问题四.遗传规划20引言GA不能描述计算机程序i=1;while(i<20){

i=i+1;}四.遗传规划21引言GA缺乏动态可变性：GA在能够定长（静态）编码表示的优化问题上求解较为有效，对于动态编码的处理往往很难取得很好的求解效果四.遗传规划22引言1992年，美国斯坦福大学Koza提出了GP算法不同领域内的问题都可以重新形成为程序归纳问题，GP为这些程序归纳问题提供了一种强壮有效的求解算法GP利用结构性的表达语言来描述问题，能够解决需用不确定长度字符描述的问题四.遗传规划23算法流程图四.遗传规划begin

generatethefunctionssetFandterminalssetTintheproblemdomain;

initializeapopulationPwithrandomindividualsbasedonFandT;evaluateeachindividualinP;

repeat

whileanew-generatedchildpopulationP’isnotfulldoselect

apairofparentindividualsfromPviaaselectionscheme;generateapairofoffspringindividualsinP’viaarecombinationscheme;mutateeachoffspringindividualviaamutationscheme;

endwhile

evaluateeachindividualinP’;generatethenewPatthenextgenerationfromP+P’;

untilastopconditionismetend24构成要素个体表达函数集F算术运算符超越函数布尔表达式条件表达式循环表达式控制转移说明变量赋值函数四.遗传规划25构成要素个体表达终止集T常数变量四.遗传规划+*acb26构成要素初始种群的产生四.遗传规划Step1从函数集中选择根结点；Step2根据给定的最大深度分别从函数集和终止

集中选择元素1)如果待定结点深度小于给定的最大深度，从

函数集F及终止集T的并集C＝F∪T中选取结点2)如果待定结点深度等于给定的最大深度，从

终止集T中选取结点27引言1995年，Storn和Price提出了DE算法，最初用于解决契比雪夫多项式问题，后来发现DE也能够有效求解很多复杂优化问题DE实际上同时借鉴了EA和群体智能算法的思想，保留EA中基于种群的各种进化操作（选择、交叉和变异等），同时也具有记忆能力使得DE能够通过群体内个体间的合作与竞争实现整个群体智能优化搜索DE成为目前最主流的智能优化算法之一五.差分进化28算法流程图五.差分进化BegininitializeandevaluateapopulationPwithrandomindividuals;repeat

foreachindividualxinP

doselectanumberofdifferentindividualsfromP;generateitsoffspringindividualx’viaamutationschemebasedontheselectedindividuals;executeacrossoveroperationuponx’withaprobabilityscheme;evaluatethegeneratedindividualx’;

endforforeac