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