遗传算法ppt课件.ppt

《遗传算法ppt课件.ppt》由会员分享，可在线阅读，更多相关《遗传算法ppt课件.ppt（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于遗传算法PPT1 1现在学习的是第1页，共53页2 2五五.遗传算法的各种变形遗传算法的各种变形5.1其它编码方法其它编码方法5.2遗传运算中的问题遗传运算中的问题5.3适值函数的标定适值函数的标定(Scaling)5.4选择策略选择策略5.5停止准则停止准则六六.应用应用 遗传算法遗传算法现在学习的是第2页，共53页3 35.1 其它编码方法其它编码方法顺序编码：用顺序编码：用1到到N的自然数的不同顺序来的自然数的不同顺序来编码，此种编码不允许重复，即编码，此种编码不允许重复，即 且且 ，又称自然数编码。，又称自然数编码。该法适用范围很广：指派问题、旅行商问题和单该法适用范围很广：指派问

2、题、旅行商问题和单机调度问题等等。机调度问题等等。合法性问题：是否符合采用的编码规则的问题合法性问题：是否符合采用的编码规则的问题五五.GA.GA的各种变形（的各种变形（1 1）现在学习的是第3页，共53页4 4实数编码：实数编码：,R为实数集为实数集 特征：方便运算简单，但反映不出基因的特征特征：方便运算简单，但反映不出基因的特征整数编码类似于顺序编码，但编码允许重复整数编码类似于顺序编码，但编码允许重复适用于：新产品投入，时间优化，伙伴挑选适用于：新产品投入，时间优化，伙伴挑选例：例：3212345 对顺序编码来说是不合法的，而对顺序编码来说是不合法的，而对整数编码来说是合法的；对整数编码

3、来说是合法的；010200不合法的不合法的01编码；编码；五五.GA.GA的各种变形（的各种变形（2 2）现在学习的是第4页，共53页5 55.2 遗传运算中的问题遗传运算中的问题在在顺序编码顺序编码遗传运算的过程中会遇见不合法遗传运算的过程中会遇见不合法的编码，应战的策略有二的编码，应战的策略有二:拒绝或修复。拒绝或修复。例如：经双切点交叉例如：经双切点交叉后，后代编码不合法后，后代编码不合法 21 345 67 21 125 67 43 125 76 43 345 76我们采用下面的修复策略使以上的编码合法。我们采用下面的修复策略使以上的编码合法。五五.GA.GA的各种变形（的各种变形（3

4、 3）现在学习的是第5页，共53页6 6顺序编码的合法性修复：顺序编码的合法性修复：I.I.交叉修复策略，分为以下几种：交叉修复策略，分为以下几种：a.a.部分映射交叉部分映射交叉b.b.顺序交叉顺序交叉c.c.循环交叉循环交叉五五.GA.GA的各种变形（的各种变形（4 4）现在学习的是第6页，共53页7 7a.a.部分映射交叉部分映射交叉(PMX)(Partially Mapped Crossover)：用特别的修复程序解决简单的双：用特别的修复程序解决简单的双切点交叉引起的非法性，步骤：切点交叉引起的非法性，步骤：选切点选切点X,Y；交换中间部分；交换中间部分；确定映射关系；确定映射关系；

5、将未换部分按映射关系恢复合法性。将未换部分按映射关系恢复合法性。五五.GA.GA的各种变形（的各种变形（5 5）现在学习的是第7页，共53页8 8PMX例题例题：五五.GA.GA的各种变形（的各种变形（6 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 XY Y现在学习的是第8页，共53页9 9b.b.顺序交叉顺序交叉顺序交叉顺序交叉(OX(OX )Order Crossover：可看做是带有不同：可看做是带有不同修复程序的部分映射交叉的变形。修复程序的

6、部分映射交叉的变形。OXOX步骤：步骤：步骤：步骤：选切点选切点X,Y；交换中间部分；交换中间部分；从切点从切点Y后第一个基因起列出原顺序，去掉已有基因；后第一个基因起列出原顺序，去掉已有基因；从切点从切点从切点从切点Y Y后第一个位置起，按顺序填入。后第一个位置起，按顺序填入。后第一个位置起，按顺序填入。后第一个位置起，按顺序填入。五五.GA.GA的各种变形（的各种变形（7 7）现在学习的是第9页，共53页1010OX例题：例题：五五.GA.GA的各种变形（的各种变形（8 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、7 6 2 1 3 4 5 6 7 1 2 5 4 3 1 2 5 7 6 3 4 5 X XY Y现在学习的是第10页，共53页1111OX的特点：的特点：较好的保留了相邻关系、先后关系较好的保留了相邻关系、先后关系,满足了满足了TSP问题的需要问题的需要,但不保留位值特征。但不保留位值特征。五五.GA.GA的各种变形（的各种变形（9 9）现在学习的是第11页，共53页1212c.循环交叉循环交叉(CX)Cycle Crossover基本思想：子串位置上的值必须与父母的相同基本思想：子串位置上的值必须与父母的相同位置上的位值相等。位置上的位值相等。CX步骤：步骤：选选 的第一个元素作为的第一

8、个元素作为 的第一位，的第一位，选选 的第一个元素作为的第一个元素作为 的第一位；的第一位；五五.GA.GA的各种变形（的各种变形（1010）现在学习的是第12页，共53页1313 到到 中找中找 的第一个元素赋给的第一个元素赋给 的相对位置的相对位置，重复此过程，直到重复此过程，直到 上得到上得到 的第一个元素为止，的第一个元素为止，称为一个循环；称为一个循环；对对最前最前的基因按的基因按 、基因基因轮替轮替原则重复以上过原则重复以上过程；程；重复以上过程，直到所有位都完成。重复以上过程，直到所有位都完成。五五.GA.GA的各种变形（的各种变形（11 11）现在学习的是第13页，共53页14

9、14CXCX例题：例题：五五.GA.GA的各种变形（的各种变形（1212）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 现在学习的是第14页，共53页1515CX的特点：的特点：与与OX的特点不同的是，的特点不同的是，CX较好的保留了位值较好的保留了位值特征，适合指派问题；而特征，适合指派问题；而OX较好的保留了相邻较好的保留了相邻关系、先后关系满足了关系、先后关系满足了TSP问题的需要。问题

10、的需要。五五.GA.GA的各种变形（的各种变形（1313）现在学习的是第15页，共53页1616II.II.变异的修复策略变异的修复策略a.a.换位变异换位变异(最常用最常用)是随机地在染色体上选取两是随机地在染色体上选取两个位置，交换基因的位值。个位置，交换基因的位值。例：例：4 3 1 2 5 6 7 4 5 1 2 3 6 7 b.b.移位变异：任选一位移到最前移位变异：任选一位移到最前 例：例：4 3 1 2 5 6 7 5 4 3 1 2 6 7五五.GA.GA的各种变形（的各种变形（1414）现在学习的是第16页，共53页1717实数编码的合法性修复实数编码的合法性修复 I.I.交

11、叉交叉a.a.单切点交叉单切点交叉五五.GA.GA的各种变形（的各种变形（1515）切点切点切点切点现在学习的是第17页，共53页1818b.b.双切点交叉双切点交叉(与单切点交叉类似与单切点交叉类似)该方法最大的问题：如何在实际优化中保持该方法最大的问题：如何在实际优化中保持可行可行性性。五五.GA.GA的各种变形（的各种变形（1616）切点切点切点切点切点切点切点切点现在学习的是第18页，共53页1919五五.GA.GA的各种变形（的各种变形（1717）c.c.凸组合交叉：可以克服上面简单交叉操作导致的解凸组合交叉：可以克服上面简单交叉操作导致的解凸组合交叉：可以克服上面简单交叉操作导致的

12、解凸组合交叉：可以克服上面简单交叉操作导致的解的不可行性。的不可行性。的不可行性。的不可行性。约束是个凸集，可行性可以保持，但是分散约束是个凸集，可行性可以保持，但是分散性太差，又出现了向中间汇集的问题。性太差，又出现了向中间汇集的问题。现在学习的是第19页，共53页2020II.II.变异变异a.a.位值变异：位值变异：任选一位加任选一位加（变异步长），（变异步长），例：例：五五.GA.GA的各种变形（的各种变形（1818）现在学习的是第20页，共53页2121b.b.向梯度方向变异向梯度方向变异向梯度方向变异向梯度方向变异缺点：只能用于目标函数可微的问题。缺点：只能用于目标函数可微的问题。

13、例例例例:对于最大化问题可采用如下操作：对于最大化问题可采用如下操作：对于最大化问题可采用如下操作：对于最大化问题可采用如下操作：优点：考虑到了问题本身的性质，效率较高。但染色体种群优点：考虑到了问题本身的性质，效率较高。但染色体种群优点：考虑到了问题本身的性质，效率较高。但染色体种群优点：考虑到了问题本身的性质，效率较高。但染色体种群也可能因此而趋于聚集，导致种群的多样性较差。也可能因此而趋于聚集，导致种群的多样性较差。也可能因此而趋于聚集，导致种群的多样性较差。也可能因此而趋于聚集，导致种群的多样性较差。五五.GA.GA的各种变形（的各种变形（1919）现在学习的是第21页，共53页222

14、25.3 适值函数的标定适值函数的标定(Scaling)五五.GA.GA的各种变形（的各种变形（2020）相对相对相对相对差别放大，差别放大，差别放大，差别放大，选择压力变大，选择压力变大，选择压力变大，选择压力变大，选优功能强化了选优功能强化了选优功能强化了选优功能强化了标定标定标定标定 相对相对相对相对差别小，选差别小，选差别小，选差别小，选择压力小，选优择压力小，选优择压力小，选优择压力小，选优功能弱化了功能弱化了功能弱化了功能弱化了现在学习的是第22页，共53页2323标定的目的：标定的目的：使适值函数不会太大，有一定差别使适值函数不会太大，有一定差别I.I.选择压力的概念：选择压力的

15、概念：选择压力是种群好、坏个体被选中的概率选择压力是种群好、坏个体被选中的概率 之差，差大称为选择压力大之差，差大称为选择压力大。注意：上述概念中的注意：上述概念中的“差大小差大小”是相对于适值函是相对于适值函数而言的。数而言的。五五.GA.GA的各种变形（的各种变形（2121）现在学习的是第23页，共53页2424II.II.局部搜索、广域搜索与选择压力的关系局部搜索、广域搜索与选择压力的关系局部搜索、广域搜索与选择压力的关系局部搜索、广域搜索与选择压力的关系 局部搜索与广域搜索是局部搜索与广域搜索是局部搜索与广域搜索是局部搜索与广域搜索是GAGA中的一对矛盾，只注重局部搜索中的一对矛盾，只

16、注重局部搜索中的一对矛盾，只注重局部搜索中的一对矛盾，只注重局部搜索很可能陷入局优，只注重广域搜索则会导致精确开发能很可能陷入局优，只注重广域搜索则会导致精确开发能很可能陷入局优，只注重广域搜索则会导致精确开发能很可能陷入局优，只注重广域搜索则会导致精确开发能力不强。因此，好的算法要将以上二者综合考虑。一般力不强。因此，好的算法要将以上二者综合考虑。一般力不强。因此，好的算法要将以上二者综合考虑。一般力不强。因此，好的算法要将以上二者综合考虑。一般来说，算法开始时应注重广域搜索，通过使用较小的选来说，算法开始时应注重广域搜索，通过使用较小的选来说，算法开始时应注重广域搜索，通过使用较小的选来说

17、，算法开始时应注重广域搜索，通过使用较小的选择压力来实现；随着迭代的进行，逐步偏重于局部搜索，择压力来实现；随着迭代的进行，逐步偏重于局部搜索，择压力来实现；随着迭代的进行，逐步偏重于局部搜索，择压力来实现；随着迭代的进行，逐步偏重于局部搜索，通过使用较大的选择压力来实现。通过使用较大的选择压力来实现。通过使用较大的选择压力来实现。通过使用较大的选择压力来实现。五五.GA.GA的各种变形（的各种变形（2222）现在学习的是第24页，共53页2525适值的标定方法适值的标定方法I.I.线性标定：线性标定：函数表达式：函数表达式：,为目标函数，为目标函数，为适值函数为适值函数五五.GA.GA的各种

18、变形（的各种变形（2323）现在学习的是第25页，共53页2626a.a.对对对对 ，=1 =1，=+，函数表达式函数表达式函数表达式函数表达式 ：+，b.b.对对对对 ，=-1 =-1，=+,函数表达式：函数表达式：函数表达式：函数表达式：+，上述中的上述中的上述中的上述中的 是一个较小的数，目的是使种群中最差的个体仍然有是一个较小的数，目的是使种群中最差的个体仍然有是一个较小的数，目的是使种群中最差的个体仍然有是一个较小的数，目的是使种群中最差的个体仍然有繁殖的机会，增加种群的多样性。繁殖的机会，增加种群的多样性。繁殖的机会，增加种群的多样性。繁殖的机会，增加种群的多样性。五五.GA.GA

19、的各种变形（的各种变形（2424）现在学习的是第26页，共53页2727II.II.动态线性标定动态线性标定(最常用最常用)：线性标定中的参数随着：线性标定中的参数随着迭代次数的增加而变化时就得到了动态线性标定迭代次数的增加而变化时就得到了动态线性标定优点：计算容易不占用时间优点：计算容易不占用时间 函数表达式：函数表达式：，为迭代指标为迭代指标a.a.最常用最大化最常用最大化 =1,函数表达式：函数表达式：五五.GA.GA的各种变形（的各种变形（2525）第第k k代的最小目标函数值代的最小目标函数值现在学习的是第27页，共53页2828b.b.加入的意义加入的意义（同线性标定中（同线性标定

20、中 的意义）的意义）加入使最坏个体仍有繁殖的可能，加入使最坏个体仍有繁殖的可能，随随 的增的增大而减小大而减小c.c.的取值：的取值：，调节调节 和和 ，从而来调节，从而来调节五五.GA.GA的各种变形（的各种变形（2626）现在学习的是第28页，共53页2929五五.GA.GA的各种变形（的各种变形（2727）d.d.引入引入 的目的：的目的：调节选择压力，即好坏个体选择概率的调节选择压力，即好坏个体选择概率的调节选择压力，即好坏个体选择概率的调节选择压力，即好坏个体选择概率的差，使广域搜索范围宽保持种群的多样性，而差，使广域搜索范围宽保持种群的多样性，而差，使广域搜索范围宽保持种群的多样性

21、，而差，使广域搜索范围宽保持种群的多样性，而局域搜索细保持收敛性。如下图表示：局域搜索细保持收敛性。如下图表示：开始：希望选择压力小开始：希望选择压力小后来：希望选择压力大后来：希望选择压力大k k现在学习的是第29页，共53页3030III.III.幂律标定：幂律标定：函数表达式：函数表达式：的取值，的取值，1时选择压力加大时选择压力加大 1时选择压力减小时选择压力减小IV.IV.对数标定：对数标定：函数表达式：函数表达式：对数标定的作用：缩小目标函数值的差别对数标定的作用：缩小目标函数值的差别五五.GA.GA的各种变形（的各种变形（2828）现在学习的是第30页，共53页3131V.V.指

22、数标定：指数标定：函数表达式：函数表达式：指数标定的作用：扩大差别指数标定的作用：扩大差别VI.VI.窗口技术：窗口技术：函数表达式：函数表达式：为前为前W代中的最小目标值，它考虑了各代代中的最小目标值，它考虑了各代的波动，这样的波动，这样 具有记忆性具有记忆性五五.GA.GA的各种变形（的各种变形（2929）现在学习的是第31页，共53页3232G.G.正规化技术：正规化技术：函数表达式：函数表达式：正规化技术的作用：正规化技术的作用：将将 映射到映射到(0,1)区间，抑制超级染色体区间，抑制超级染色体正规化技术的实质：特殊的动态标定正规化技术的实质：特殊的动态标定即即其中：其中：五五.GA

23、.GA的各种变形（的各种变形（3030）现在学习的是第32页，共53页33335.4 选择策略选择策略传统的传统的GA选择和遗传是一起进行的，即使选择和遗传是一起进行的，即使后代不如父代，却无法纠正。下面介绍的选择后代不如父代，却无法纠正。下面介绍的选择策略都是先遗传后选择。这样，样本空间扩大策略都是先遗传后选择。这样，样本空间扩大了，可供选择的个体增多了。了，可供选择的个体增多了。五五.GA.GA的各种变形（的各种变形（3131）现在学习的是第33页，共53页3434I.I.截断选择：截断选择：选择选择最好的前最好的前T个个个体，让每一个有个体，让每一个有1/T的选择概的选择概率，平均得到率

24、，平均得到NP/T个繁殖机会。个繁殖机会。例：例：NP=100,T=50即即100名学生，成绩前名学生，成绩前50名的选出。每人的选择概名的选出。每人的选择概率为率为150，有平均，有平均2个机会。个机会。缺点：这种方法将花费较多的时间在适应值的缺点：这种方法将花费较多的时间在适应值的 排序上。排序上。五五.GA.GA的各种变形（的各种变形（3232）现在学习的是第34页，共53页3535II.顺序选择：顺序选择：a.a.步骤：步骤：从好到坏排序所有个体从好到坏排序所有个体 定义最好个体的选择概率为定义最好个体的选择概率为 ,则第则第 个个体的个个体的选择概率为：选择概率为：五五.GA.GA的

25、各种变形（的各种变形（3333）现在学习的是第35页，共53页3636由于由于 有限时要归一化，则有下面的公式：有限时要归一化，则有下面的公式：，其中，其中顺序选择的优点：选择概率可以离线计算，节省算顺序选择的优点：选择概率可以离线计算，节省算法执行时间，且选择压力可控；法执行时间，且选择压力可控；缺点：把选择概率固定化了，选择压力不可调节。缺点：把选择概率固定化了，选择压力不可调节。五五.GA.GA的各种变形（的各种变形（3434）现在学习的是第36页，共53页3737b.b.举例举例:且：且：采用旋轮法，随机产生采用旋轮法，随机产生 当当 ，选择个体，选择个体五五.GA.GA的各种变形（的

26、各种变形（3535）前前前前i-1i-1个个体的选择概率个个体的选择概率前前i i个个体的选择概率个个体的选择概率个个体的选择概率个个体的选择概率现在学习的是第37页，共53页3838III.III.正比选择：个体正比选择：个体i的选择概率的选择概率 令：令：，用动态标定来调节选择压力，采用用动态标定来调节选择压力，采用旋轮法旋轮法来共来共同完成种群的选择。同完成种群的选择。五五.GA.GA的各种变形（的各种变形（3636）现在学习的是第38页，共53页39395.5 停止准则停止准则指定最大代数（常用）：该方法简单但不准确。指定最大代数（常用）：该方法简单但不准确。检查种群中适值的一致性：保

27、持历史上最好检查种群中适值的一致性：保持历史上最好的个体。计算公式：的个体。计算公式：或或第二种方法因很难实现，所以很少使用。第二种方法因很难实现，所以很少使用。五五.GA.GA的各种变形（的各种变形（3737）现在学习的是第39页，共53页4040背包问题背包问题个物品，对物品个物品，对物品 ，价值为，价值为 ，重量为，重量为 ，背包容量是背包容量是 。如何选取物品装入背包，使背。如何选取物品装入背包，使背包中的价值最大。包中的价值最大。六六.应用（应用（1）现在学习的是第40页，共53页4141模型模型:（二进制编码方法）（二进制编码方法），装入物品，装入物品，不装入物品，不装入物品六六.

28、应用（应用（2）现在学习的是第41页，共53页4242例如，对于一个例如，对于一个7个项目的背包问题，背包容量W=100，具体数据见下表，考察如下编码X=（1 1 0 0 1 1 0）这表示项目这表示项目1、2、5 5和和6被装入了背包，经过计算可知产生的解不可行。背包问题示例背包问题示例i1234567wi40503010104030pi4060101032060Pi/wi11.20.3310.30.52现在学习的是第42页，共53页4343如何处理约束来保持可行性如何处理约束来保持可行性I.I.拒绝策略：拒绝策略：可行解不易达到时，很难达到一个初始种群可行解不易达到时，很难达到一个初始种群

29、II.II.修复策略：修复策略：将不可行解修复为可行的，但将失去多样性。将不可行解修复为可行的，但将失去多样性。六六.应用（应用（3）现在学习的是第43页，共53页4444III.III.惩罚策略：惩罚策略：要求设计适当的惩罚函数，但设计不好会掩盖要求设计适当的惩罚函数，但设计不好会掩盖目标函数的优化。目标函数的优化。下面，我们将分别采用惩罚策略和解码法来下面，我们将分别采用惩罚策略和解码法来处理上面的背包问题。处理上面的背包问题。六六.应用（应用（4）现在学习的是第44页，共53页4545a.a.罚函数法罚函数法令适值函数令适值函数 ，其中，其中 是目标函数是目标函数 令令 ，其中，其中注：

30、注：与与 是是 的两个端点的两个端点六六.应用（应用（5）罚函数罚函数现在学习的是第45页，共53页4646函数式的意义：函数式的意义：的作用是使的作用是使，保证，保证 可行也惩罚，只有当可行也惩罚，只有当 时不惩罚。时不惩罚。罚函数法的目的：把解拉向边界，尽量装满。罚函数法的目的：把解拉向边界，尽量装满。六六.应用（应用（6）现在学习的是第46页，共53页4747b.b.解码法解码法First Fit Heuristic(优先适合启优先适合启发式发式)解码法是一段修复程序解码法是一段修复程序(修复可行性的方法修复可行性的方法)步骤：步骤：I.I.将选上物品按将选上物品按 降序排列；降序排列；

31、II.II.选前选前 个物品，使个物品，使；解码法的关键：如何在解码法的关键：如何在GA中解决可行性问题中解决可行性问题编码方法：采用顺序编码编码方法：采用顺序编码六六.应用（应用（7）现在学习的是第47页，共53页4848例：例：=7用顺序用顺序(3 2 5 1 4 6 7)表示选择物品的顺序表示选择物品的顺序用优先适合启发式保留前用优先适合启发式保留前K位，使解可行位，使解可行即：即：=3，(3 2 5)问题：编码长度是可变的，如何做交叉和变异问题：编码长度是可变的，如何做交叉和变异六六.应用（应用（8）3030505010104040100100现在学习的是第48页，共53页4949变长

32、顺序编码的遗传算法插入式交叉算法变长顺序编码的遗传算法插入式交叉算法a)a)在在 上选一个随机的断点；上选一个随机的断点；b)b)在在 上随机选一个基因片断插入上随机选一个基因片断插入 的断点处；的断点处；c)c)去掉去掉 上的重复基因；上的重复基因；d)d)按优先适合启发式得到可行解按优先适合启发式得到可行解见下页例题见下页例题六六.应用（应用（9 9）现在学习的是第49页，共53页5050例题例题：六六.应用（应用（1010）去掉重复基因：去掉重复基因：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 5X X现在学习的是第50页，共53页5151（5）变长顺序编码的遗传算法插入式变异算法）变长顺序编码的遗传算法插入式变异算法a)a)随机删除一个基因；随机删除一个基因；b)b)在染色体中随机插入一个没有的基因；在染色体中随机插入一个没有的基因；c)c)对于以上原始后代用优先适合启发式方法产生对于以上原始后代用优先适合启发式方法产生一个可行解。一个可行解。六六.应用（应用（11 11）现在学习的是第51页，共53页5252现在学习的是第52页，共53页感谢大家观看现在学习的是第53页，共53页