最经典的遗传算法教程PPT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,遗传算法,传统的优化方法（局部优化）,共轭梯度法、拟牛顿法、单纯形方法,全局优化方法,漫步法（,Random Walk,）、模拟退火法、,GA,关于优化问题,比较：,传统的优化方法,1,）依赖于初始条件。,2,）与求解空间有紧密关系，促使较快地收敛到局部 解，但同时对解域有约束，如可微或连续。利用这些约束，收敛快。,3,）有些方法，如,Davison-Fletcher-Powell,直接依赖于至少一阶导数；共轭梯度法隐含地依赖于梯度。,1,全局优化方法,1,）不依赖于初始条件；,2,）不与求解空间有紧密关系对解域，无可微或连续的要求。求 解稳健，但收敛速度慢。能获得全局最优。适合于求解空间不知的情况,2,选择运算,交换操作,变异,遗传算法的基本运算,遗传算法,基本原理,模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传,空间，把可能的解编码成一个向量,染色体，向量的每个,元素称为基因。,通过不断计算各染色体的适应值，选择最好的染色体，获,得最优解。,3,选择运算,从旧的种群中选择适应度高的染色体，放入匹配集（缓冲,区），为以后染色体交换、变异，产生新的染色体作准备。,选择方法,适应度比例法（转轮法）,按各染色体适应度大小比例来决定其被选择数目的多少。,某染色体被选的概率：,P,c,x,i,为种群中第,i,个染色体，,4,具体步骤,1,）计算各染色体适应度值,2,）累计所有染色体适应度值，记录中间累加值,S,-mid,和最,后累加值,sum=,f(x,i,),3,）产生一个随机数,N,，,0 N,sum,4,）选择对应中间累加值,S,-mid,的第一个染色体进入交换集,5,）重复（,3,）和（,4,），直到获得足够的染色体。,举例：,具有,6,个染色体的二进制编码、适应度值、,P,c,累计,值。,5,染色体的 适应度和所占的比例,用转轮方法进行选择,6,染色体编号,1,2,3,4,5,6,7,8,9,10,适应度,8,2,17,7,2,12,11,7,3,7,被选概率,0.1,0.02,0.22,0.09,0.02,0.16,0.14,0.09,0.03,0.09,适应度累计,8,10,27,34,36,48,59,66,69,76,随机数,23,49,76,13,1,27,57,所选染色体号码,3,7,10,3,1,3,7,染色体被选的概率,被选的染色体个数,10,个染色体种群按比例的选择过程,7,交换操作,方法,:,随机选择二个染色体,(,双亲染色体,),随机指定一点或多点,进行交换,可得二个新的染色体,(,子辈染色体,).,新的子辈染色体,:A,11010001,B 01011110,模拟生物在自然界环境变化,引起基因的突变,.,在染色体二进制编码中,1,变成,0;或,0,变成,1.,突变产生染色体的多样性,避免进化中早期成熟,陷入局部极值点,突变的概率很低,.,变异,复制不能创新,交换解决染色体的创新,8,GA,的流程,9,简单遗传算法（,GA,）的基本参数,种群规模,P:,参与进化的染色体总数,.,代沟,G:,二代之间不相同的染色体数目,无重叠,G=1;,有重叠,0 G 1,选择方法,:,转轮法,精英选择法,竞争法,.,交换率,:,P,c,一般为,60100%.,变异率,:,P,m,一般为,0.110%,举例,:,变异概率取,0.001,10,初始种群和它的适应度值,染色体的交换操纵,11,举例,：,14,12,步骤,1,）编码：确定二进制的位数；组成个体（染色体）,步骤,2,）选择种群数,P,和初始个体，计算适应度值，,P,=20,；,13,步骤,3,）确定选择方法；交换率,P,C,；变异率,P,m,。,选择方法用竞争法；,P,C,=0.7,P,m,=0.05,计算结果,：,8,代后，,f(x,y),=0.998757,41,代后，,f(x,y),=1.00000,x=3.000290,y=2.999924.,160,次适应度计算，达到最优值。,遗传算法的基本数学问题,一个重要的定理,图式定理,什么叫图式？,描述种群中染色体相似性的字符串。,（插入演示）,演示,12,14,（*为通配符）,15,图式的描述：,定义长度,（,H)H,左右二端有定义位置之间的距离；,图式的阶次,(,或固定长度,)O(H,）,H,中非*位（有定义位）,的个数。,图式定理的推导,图式在选择过程中的增加,.,16,经过选择,在,t+1,代,图式,H,的数量,m(H,t+1),为,:,17,图式在交换中的破坏,图式在变异中的破坏,经过选择、交换、变异后在,t+1,中，图式,H,的数量：,图式定理：在选择、交换、变异的作用下，阶次低、定义长度短、适应度高的图式（模块）将按指数增长的规律，一代一代地增长。,18,遗传算法在应用中的一些基本问题,1,）知识的编码,2,）适应度函数,。,a),适应度函数值必须非负。根据情况做适当的处理,二进制和十进制的比较：二进制有更多图式和更大的搜索范围；十进制更接近于实际操作。,19,20,3,）全局最优和收敛性,。,根据图式定理，对于具有“欺骗性”函数，,GA,有可能落入局部最优点。,b,）为保持种群的多样性，防止“超级”染色体“统治”种群。,21,欺骗性函数,图式划分：,指引相互之间竞争的,定义位为同一集合,的一组图式。,如,#,表示定义位，则,H,1,=*1*0*,，,H,2,=*0*1*,，,H,3,=*1*1*,，,H,4,=*0*0*,同属于划分*,#*#*,。,总平均适应度（,OAF,）,：对一个给定图式，,OAF,即为其成员,的平均适应度。,欺骗性函数,包含全局最优的图式其,OAF,不如包含局部最优的,OAF,，这种划分称为欺骗划分，它会使,GA,陷入局部最优。,如最高阶欺骗函数有,k,个定义位，则此函数称,k,阶欺骗。,22,举例：,3,位欺骗函数,23,高级,GA,算法,1,）操作的改进,2,）算法的改进,选择方法改进,：精英法（竞赛法）、置换式和非置换式,随机选择法，排序法。,交换方法的改进：,多点交换；重组运算,微种群遗传算法（,GA,）,双种群遗传算法（,DPGA,）,重组运算：解决染色体分布过于集中问题。把适应度函数做进一步处理。,24,终止条件：,1,）达到预定指标；,2,）达到预定代数。,GA,算法,25,双种群算法（,DPGA,）,基本思想：利用人类社会分工合作的机理。,分成：,全局种群,粗搜索，寻找可能存在的最优区域；,局部种群,精搜索在全局划定的区域内，寻找最优点。,26,测试函数：,27,28,遗传算法的应用：,1,）神经网络结构参数的选择,2,）滑模控制中应用,3,）倒立摆控制中应用,29,