遗传算法课件PPT课件.ppt
《遗传算法课件PPT课件.ppt》由会员分享,可在线阅读,更多相关《遗传算法课件PPT课件.ppt(53页珍藏版)》请在三一办公上搜索。
1、1,第三章 遗传算法,2,五.遗传算法的各种变形5.1其它编码方法5.2遗传运算中的问题5.3适值函数的标定(Scaling)5.4选择策略5.5停止准则六.应用,遗传算法,3,5.1 其它编码方法顺序编码:用1到N的自然数的不同顺序来编码,此种编码不允许重复,即 且,又称自然数编码。该法适用范围很广:指派问题、旅行商问题和单机调度问题等等。合法性问题:是否符合采用的编码规则的问题,五.GA的各种变形(1),4,实数编码:,R为实数集 特征:方便运算简单,但反映不出基因的特征整数编码类似于顺序编码,但编码允许重复适用于:新产品投入,时间优化,伙伴挑选例:3212345 对顺序编码来说是不合法的
2、,而对整数编码来说是合法的;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):用特别的修复程序解决简单的双切点交
3、叉引起的非法性,步骤:选切点X,Y;交换中间部分;确定映射关系;将未换部分按映射关系恢复合法性。,五.GA的各种变形(5),8,PMX例题:,五.GA的各种变形(6),9,顺序交叉(OX)Order Crossover:可看做是带有不同修复程序的部分映射交叉的变形。OX步骤:选切点X,Y;交换中间部分;从切点Y后第一个基因起列出原顺序,去掉已有基因;从切点Y后第一个位置起,按顺序填入。,五.GA的各种变形(7),10,OX例题:,五.GA的各种变形(8),11,OX的特点:较好的保留了相邻关系、先后关系,满足了TSP问题的需要,但不保留位值特征。,五.GA的各种变形(9),12,循环交叉(CX
4、)Cycle Crossover基本思想:子串位置上的值必须与父母的相同位置上的位值相等。CX步骤:选 的第一个元素作为 的第一位,选 的第一个元素作为 的第一位;,五.GA的各种变形(10),13,到 中找 的第一个元素赋给 的相对位置,重复此过程,直到 上得到 的第一个元素为止,称为一个循环;对最前的基因按、基因轮替原则重复以上过程;重复以上过程,直到所有位都完成。,五.GA的各种变形(11),14,CX例题:,五.GA的各种变形(12),15,CX的特点:与OX的特点不同的是,CX较好的保留了位值特征,适合指派问题;而OX较好的保留了相邻关系、先后关系满足了TSP问题的需要。,五.GA的
5、各种变形(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),凸组合交叉:可以克服上面简单交叉操作导致的解的不可行性。约束是个凸集,可行性可以保持,但是分散性
6、太差,又出现了向中间汇集的问题。,20,变异位值变异:任选一位加(变异步长),例:,五.GA的各种变形(18),21,向梯度方向变异缺点:只能用于目标函数可微的问题。例:对于最大化问题可采用如下操作:优点:考虑到了问题本身的性质,效率较高。但染色体种群也可能因此而趋于聚集,导致种群的多样性较差。,五.GA的各种变形(19),22,5.3 适值函数的标定(Scaling),五.GA的各种变形(20),23,标定的目的:使适值函数不会太大,有一定差别选择压力的概念:选择压力是种群好、坏个体被选中的概率 之差,差大称为选择压力大。注意:上述概念中的“差大小”是相对于适值函数而言的。,五.GA的各种变
7、形(21),24,局部搜索、广域搜索与选择压力的关系 局部搜索与广域搜索是GA中的一对矛盾,只注重局部搜索很可能陷入局优,只注重广域搜索则会导致精确开发能力不强。因此,好的算法要将以上二者综合考虑。一般来说,算法开始时应注重广域搜索,通过使用较小的选择压力来实现;随着迭代的进行,逐步偏重于局部搜索,通过使用较大的选择压力来实现。,五.GA的各种变形(22),25,适值的标定方法线性标定:函数表达式:,为目标函数,为适值函数,五.GA的各种变形(23),26,对,=1,=+,函数表达式:+,对,=-1,=+,函数表达式:+,上述中的是一个较小的数,目的是使种群中最差的个体仍然有繁殖的机会,增加种
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 遗传 算法 课件 PPT
链接地址:https://www.31ppt.com/p-5856795.html