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