遗传算法课件PPT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,第三章 遗传算法,2,五,.,遗传算法的各种变形,5.1,其它编码方法,5.2,遗传运算中的问题,5.3,适值函数的标定,(Scaling),5.4,选择策略,5.5,停止准则,六,.,应用,遗传算法,3,5.1,其它编码方法,顺序编码：用,1,到,N,的自然数的不同顺序来,编码，此种编码不允许重复，即,且 ，又称自然数编码。,该法适用范围很广：指派问题、旅行商问题和单机调度问题等等。,合法性问题：是否符合采用的编码规则的问题,五,.GA,的各种变形（,1,）,4,实数编码：,R,为实数集,特征：方便运算简单，但反映不出基因的特征,整数编码类似于顺序编码，但编码允许重复,适用于：新产品投入，时间优化，伙伴挑选,例：,3212345,对顺序编码来说是不合法的，而,对整数编码来说是合法的；,010200,不合法的,01,编码；,五,.GA,的各种变形（,2,）,5,5.2,遗传运算中的问题,在,顺序编码,遗传运算的过程中会遇见不合法,的编码，应战的策略有二,:,拒绝或修复。,例如：经双切点交叉后，后代编码不合法,21 345 67 21 125 67,43 125 76 43 345 76,我们采用下面的修复策略使以上的编码合法。,五,.GA,的各种变形（,3,）,6,顺序编码的合法性修复：,交叉修复策略，分为以下几种：,部分映射交叉,顺序交叉,循环交叉,五,.GA,的各种变形（,4,）,7,部分映射交叉,(PMX)(Partially Mapped Crossover),：用特别的修复程序解决简单的双切点交叉引起的非法性，步骤：,选切点,X,Y,；,交换中间部分；,确定映射关系；,将未换部分按映射关系恢复合法性。,五,.GA,的各种变形（,5,）,8,PMX,例题,：,五,.GA,的各种变形（,6,）,映射关系：,3-1,，,4-2,，,5-5,则：,4 3,1 2 5,6 7,2 1,3 4 5,7 6,2 1 3 4 5 6 7 ,1 2 5,4 3,1 2 5,7 6,3 4 5,X,Y,9,顺序交叉,(OX,)Order Crossover,：可看做是带有不同修复程序的部分映射交叉的变形。,OX,步骤：,选切点,X,Y,；,交换中间部分；,从切点,Y,后第一个基因起列出原顺序，去掉已有基因；,从切点,Y,后第一个位置起，按顺序填入。,五,.GA,的各种变形（,7,）,10,OX,例题：,五,.GA,的各种变形（,8,）,列出基因：,6 7 2 1 3 4 5 7 6 4 3 1 2 5,则：,3 4,1 2 5,6 7,1 2,3 4 5,7 6,2 1 3 4 5 6 7 ,1 2 5,4 3,1 2 5,7 6,3 4 5,X,Y,11,OX,的特点：,较好的保留了相邻关系、先后关系,满足了,TSP,问题的需要,但不保留位值特征。,五,.GA,的各种变形（,9,）,12,循环交叉,(CX)Cycle Crossover,基本思想：子串位置上的值必须与父母的相同,位置上的位值相等。,CX,步骤：,选 的第一个元素作为 的第一位，,选 的第一个元素作为 的第一位；,五,.GA,的各种变形（,10,）,13,到 中找 的第一个元素赋给 的相对位置,，重复此过程，直到 上得到 的第一个元素为止，称为一个循环；,对,最前,的基因按 、基因,轮替,原则重复以上过程；,重复以上过程，直到所有位都完成。,五,.GA,的各种变形（,11,）,14,CX,例题：,五,.GA,的各种变形（,12,）,2 4 5 3 8 9 6 1 7 2,3,6,3 9 8 6 5 4 2 7 1 3 6 2,3,2,，,9 4,，,5 8,，,7 1,6,2 9,3,4 6,3 4 6 9 2,2 9,5 3 8,4 6 7 1,3 4 8 6 5 9 2 1 7,15,CX,的特点：,与,OX,的特点不同的是，,CX,较好的保留了位值,特征，适合指派问题；而,OX,较好的保留了相邻,关系、先后关系满足了,TSP,问题的需要。,五,.GA,的各种变形（,13,）,16,变异的修复策略,换位变异,(,最常用,),是随机地在染色体上选取两个位置，交换基因的位值。,例：,4,3,1 2,5,6 7 4,5,1 2,3,6 7,移位变异：任选一位移到最前,例：,4 3 1 2,5,6 7 5 4 3 1 2 6 7,五,.GA,的各种变形（,14,）,17,实数编码的合法性修复,交叉,单切点交叉,五,.GA,的各种变形（,15,）,切点,18,双切点交叉,(,与单切点交叉类似,),该方法最大的问题：如何在实际优化中保持,可行性,。,五,.GA,的各种变形（,16,）,切点,切点,19,五,.GA,的各种变形（,17,）,凸组合交叉：可以克服上面简单交叉操作导致的解的不可行性。,约束是个凸集，可行性可以保持，但是分散,性太差，又出现了向中间汇集的问题。,20,变异,位值变异：,任选一位加,（,变异步长），,例：,五,.GA,的各种变形（,18,）,21,向梯度方向变异,缺点：只能用于目标函数可微的问题。,例,:,对于最大化问题可采用如下操作：,优点：考虑到了问题本身的性质，效率较高。但染色体种群也可能因此而趋于聚集，导致种群的多样性较差。,五,.GA,的各种变形（,19,）,22,5.3,适值函数的标定,(Scaling),五,.GA,的各种变形（,20,）,相对,差别放大，选择压力变大，选优功能强化了,标定,相对,差别小，选择压力小，选优功能弱化了,23,标定的目的使适值函数不会太大，有一定差别,选择压力的概念：,选择压力是种群好、坏个体被选中的概率,之差，差大称为选择压力大,。,注意：上述概念中的“差大小”是相对于适值函数而言的。,五,.GA,的各种变形（,21,）,24,局部搜索、广域搜索与选择压力的关系,局部搜索与广域搜索是,GA,中的一对矛盾，只注重局部搜索很可能陷入局优，只注重广域搜索则会导致精确开发能力不强。因此，好的算法要将以上二者综合考虑。一般来说，算法开始时应注重广域搜索，通过使用较小的选择压力来实现；随着迭代的进行，逐步偏重于局部搜索，通过使用较大的选择压力来实现。,五,.GA,的各种变形（,22,）,25,适值的标定方法,线性标定：,函数表达式：,为目标函数，为适值函数,五,.GA,的各种变形（,23,）,26,对 ，,=1，=,+,，,函数表达式：,+,，,对 ，,=-1，=,+,函数表达式：,+,，,上述中,的,是,一个较小的数，目的是使种群中最差的个体仍然有繁殖的机会，增加种群的多样性。,五,.GA,的各种变形（,24,）,27,动态线性标定,(,最常用,),：线性标定中的参数随着迭代次数的增加而变化时就得到了动态线性标定,优点：计算容易不占用时间,函数表达式：，为迭代指标,最常用最大化,=1,函数表达式：,五,.GA,的各种变形（,25,）,第,k,代的最小目标函数值,28,加入的意义,（同线性标定中,的意义加入使最坏个体仍有繁殖的可能，随 的增大而减小,的取值：,，,调节 和 ，从而来调节,五,.GA,的各种变形（,26,）,29,五,.GA,的各种变形（,27,）,引入 的目的：,调节选择压力，即好坏个体选择概率的,差，使广域搜索范围宽保持种群的多样性，而,局域搜索细保持收敛性。如下图表示：,开始：希望选择压力小,后来：希望选择压力大,k,30,幂律标定：,函数表达式：,的取值，,1,时选择压力加大,1,时选择压力减小,对数标定：,函数表达式：,对数标定的作用：缩小目标函数值的差别,五,.GA,的各种变形（,28,）,31,指数标定：,函数表达式：,指数标定的作用：扩大差别,窗口技术：,函数表达式：,为前,W,代中的最小目标值，它考虑了各代的波动，这样 具有记忆性,五,.GA,的各种变形（,29,）,32,正规化技术：,函数表达式：,正规化技术的作用：,将 映射到,(0,1),区间，抑制超级染色体,正规化技术的实质：特殊的动态标定,即,其中：,五,.GA,的各种变形（,30,）,33,5.4,选择策略,传统的,GA,选择和遗传是一起进行的，即使,后代不如父代，却无法纠正。下面介绍的选择,策略都是先遗传后选择。这样，样本空间扩大,了，可供选择的个体增多了。,五,.GA,的各种变形（,31,）,34,截断选择：,选择,最好的前,T,个,个体，让每一个有,1/T,的选择概率，平均得到NP/T,个繁殖机会。,例：,NP=100,T=50,即,100,名学生，成绩前,50,名的选出。每人的选择概率为,1,50,，有平均,2,个机会。,缺点：这种方法将花费较多的时间在适应值的,排序,上。,五,.GA,的各种变形（,32,）,35,顺序选择：,步骤：,从好到坏排序所有个体,定义最好个体的选择概率为,则第 个个体的选择概率为：,五,.GA,的各种变形（,33,）,36,由于,有限时要归一化，则有下面的公式：,，其中,顺序选择的优点：选择概率可以离线计算，节省算法执行时间，且选择压力可控；,缺点：把选择概率固定化了，选择压力不可调节。,五,.GA,的各种变形（,34,）,37,举例且：,采用旋轮法，随机产生,当 ，选择个体,五,.GA,的各种变形（,35,）,前,i-1,个个体的选择概率,前,i,个个体的选择概率,38,正比选择：个体,i,的选择概率,令：，,用动态标定来调节选择压力，采用,旋轮法,来共,同完成种群的选择。,五,.GA,的各种变形（,36,）,39,5.5,停止准则,指定最大代数（常用）：该方法简单但不准确。,检查种群中适值的一致性：保持历史上最好的个体。计算公式：,或,第二种方法因很难实现，所以很少使用。,五,.GA,的各种变形（,37,）,40,背包问题,个物品，对物品 ，价值为 ，重量为 ，,背包容量是 。如何选取物品装入背包，使背,包中的价值最大。,六,.,应用（,1,）,41,模型,:,（二进制编码方法）,，装入物品,，不装入物品,六,.,应用（,2,）,42,例如，对于一个,7,个项目的背包问题，背包容量,W=100,，具体数据见下表，考察如下编码,X=,（,1 1 0 0 1 1 0,）,这表示项目,1,、,2,、,5,和,6,被装入了背包，经过计算可知产生的解不可行。,背包问题示例,i,1,2,3,4,5,6,7,wi,40,50,30,10,10,40,30,pi,40,60,10,10,3,20,60,Pi/wi,1,1.2,0.33,1,0.3,0.5,2,43,如何处理约束来保持可行性,拒绝策略：,可行解不易达到时，很难达到一个初始种群,修复策略：,将不可行解修复为可行的，但将失去多样性。,六,.,应用（,3,）,44,惩罚策略：,要求设计适当的惩罚函数，但设计不好会掩盖目标函数的优化。,下面，我们将分别采用惩罚策略和解码法来处理上面的背包问题。,六,.,应用（,4,）,45,罚函数法,令适值函数 ，其中 是目标函数,令 ，其中,注：与 是 的两个端点,六,.,应用（,5,）,罚函数,46,函数式的意义：,的作用是使，保证,可行也惩罚，只有当 时不惩罚。,罚函数法的目的：把解拉向边界，尽量装满。,六,.,应用（,6,）,47,解码法,First Fit Heuristic(,优先适合启,发式,),解码法是一段修复程序,(,修复可行性的方法,),步骤：,将选上物品按 降序排列；,选前 个物品，使；,解码法的关键：如何在,GA,中解决可行性问题,编码方法：采用顺序编码,六,.,应用（,7,）,48,例：,=7,用顺序,(3 2 5 1 4 6 7),表示选择物品的顺序,用优先适合启发式保留前,K,位，使解可行,即：,=3,，,(3 2 5),问题：编码长度是可变的，如何做交叉和变异,六,.,应用（,8,）,30,50,10,40,100,49,变长顺序编码的遗传算法插入式交叉算法,在 上选一个随机的断点；,在 上随机选一个基因片断插入 的断点处；,去掉 上的重复基因；,按优先适合启发式得到可行解,见下页例题,六,.,应用（,9,）,50,例题,：,六,.,应用（,10,）,去掉重复基因：,3 2,4 6,1 5,可行吗？,选,5,时背包装不下，去掉,5,3 2 4 6 1,3 2 1 5 4 3 2,4 6,1 5 4,1 2,4 6,3 5,X,51,（,5,）变长顺序编码的遗传算法插入式变异算法,随机删除一个基因；,在染色体中随机插入一个没有的基因；,对于以上原始后代用优先适合启发式方法产生一个可行解。,六,.,应用（,11,）,52,对于二进制编码来说,7,个项目的背包问题共有编码 个，这与解空间是一一对应的，但是不能保证解的可行性；对于边长顺序编码来说，其初始编码（及随机产生的项目顺序）共有 个，与解空间不是一一对应的，但是能够保证解的可行性。,53,谢谢欣赏！,