遗传算法课件PPT.ppt
《遗传算法课件PPT.ppt》由会员分享,可在线阅读,更多相关《遗传算法课件PPT.ppt(53页珍藏版)》请在启牛文库网上搜索。
1、第三章 遗传算法1 1五五.遗传算法的各种变形遗传算法的各种变形5.1其它编码方法其它编码方法5.2遗传运算中的问题遗传运算中的问题5.3适值函数的标定适值函数的标定(Scaling)5.4选择策略选择策略5.5停止准则停止准则六六. 应用应用 遗传算法遗传算法2 25.1 其它其它编码方法编码方法顺序编码:用顺序编码:用1到到N的自然数的不同顺序来的自然数的不同顺序来编码,此种编码不允许重复,即编码,此种编码不允许重复,即 且且 ,又称自然数编码。,又称自然数编码。该该法适用范围法适用范围很广很广:指派问题、:指派问题、旅行商旅行商问题和问题和单机调度问题等等。单机调度问题等等。合法性问题:
2、是否符合采用的编码规则的问题合法性问题:是否符合采用的编码规则的问题五五.GA.GA的各种变形的各种变形(1 1)3 3实数编码:实数编码: ,R为实数集为实数集 特征:方便运算简单,但反映不出基因的特征特征:方便运算简单,但反映不出基因的特征整数整数编码类似于顺序编码,但编码允许重复编码类似于顺序编码,但编码允许重复适用于:新产品适用于:新产品投入,时间优化,伙伴挑选投入,时间优化,伙伴挑选例:例:3212345 对顺序编码来说是不合法的,而对顺序编码来说是不合法的,而对整数编码来说是合法的;对整数编码来说是合法的;010200不合法的不合法的01编码;编码;五五.GA.GA的各种变形(的各
3、种变形(2 2)4 45.2 遗传遗传运算中的问题运算中的问题在在顺序编码顺序编码遗传运算的过程中会遇见不合法遗传运算的过程中会遇见不合法的编码,应战的策略有二的编码,应战的策略有二:拒绝或修复。拒绝或修复。例如:例如:经双切点交叉经双切点交叉后,后代编码不合法后,后代编码不合法 21 345 67 21 125 67 43 125 76 43 345 76我们采用下面的修复策略使以上的编码合法。我们采用下面的修复策略使以上的编码合法。五五.GA.GA的各种变形(的各种变形(3 3)5 5顺序编码的合法性修复:顺序编码的合法性修复:I. I.交叉交叉修复策略,分为以下几种:修复策略,分为以下几
4、种:a.a.部分映射交叉部分映射交叉b.b.顺序交叉顺序交叉c.c.循环交叉循环交叉五五.GA.GA的各种变形(的各种变形(4 4)6 6a.a.部分映射交叉部分映射交叉(PMX) ( Partially Mapped Crossover):用特别的修复程序解决简单:用特别的修复程序解决简单的双切点交叉引起的非法性,步骤的双切点交叉引起的非法性,步骤:选切点选切点X,Y;交换中间部分;交换中间部分;确定映射关系;确定映射关系;将未换部分按映射关系恢复合法性。将未换部分按映射关系恢复合法性。五五.GA.GA的各种变形(的各种变形(5 5)7 7PMX例题例题:五五.GA.GA的各种变形(的各种变
5、形(6 6)映射关系:映射关系:映射关系:映射关系:3-13-1,4-24-2,5-55-5则:则: 4 3 4 3 1 2 5 1 2 5 6 7 6 7 2 1 2 1 3 4 5 3 4 5 7 6 7 6 2 1 3 4 5 6 7 2 1 3 4 5 6 7 1 2 5 1 2 5 4 3 4 3 1 2 5 1 2 5 7 6 7 6 3 4 5 3 4 5 X XY Y8 8b.b.顺序交叉顺序交叉顺序交叉顺序交叉( OX( OX )Order Crossover)Order Crossover:可看做是带有:可看做是带有:可看做是带有:可看做是带有不同修复程序的部分映射交叉的变
6、形。不同修复程序的部分映射交叉的变形。不同修复程序的部分映射交叉的变形。不同修复程序的部分映射交叉的变形。OXOX步骤:步骤:步骤:步骤: 选切点选切点选切点选切点X,YX,Y; 交换中间部分;交换中间部分;交换中间部分;交换中间部分; 从切点从切点从切点从切点Y Y后第一个基因起列出后第一个基因起列出后第一个基因起列出后第一个基因起列出原顺序原顺序原顺序原顺序,去掉已有基,去掉已有基,去掉已有基,去掉已有基因;因;因;因; 从切点从切点从切点从切点Y Y后第一个位置起,按顺序填入后第一个位置起,按顺序填入后第一个位置起,按顺序填入后第一个位置起,按顺序填入。五五.GA.GA的各种变形(的各种
7、变形(7 7)9 9OX例题:例题:五五.GA.GA的各种变形(的各种变形(8 8)列出基因:列出基因:6 7 2 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 3 4 1 2 5 1 2 5 6 7 6 7 1 2 1 2 3 4 5 3 4 5 7 6 7 6 2 1 3 4 5 6 7 2 1 3 4 5 6 7 1 2 5 1 2 5 4 3 4 3 1 2 5 1 2 5 7 6 7 6 3 4 5 3 4 5 X XY Y1010OX的特点:的特点:较好的保留了相邻关系较好的保留了相邻关系、先后关系、先后关系,满足
8、满足了了TSP问题问题的需要的需要,但但不保留位值特征。不保留位值特征。五五.GA.GA的各种变形(的各种变形(9 9)1111c.循环交叉循环交叉(CX) Cycle Crossover基本思想:子串位置上的值必须与父母的相同基本思想:子串位置上的值必须与父母的相同位置上的位值相等。位置上的位值相等。CX步骤:步骤: 选选 的第一个元素作为的第一个元素作为 的第一位,的第一位,选选 的第一个元素作为的第一个元素作为 的第一位;的第一位;五五.GA.GA的各种变形(的各种变形(1010)1212 到到 中找中找 的第一个元素赋给的第一个元素赋给 的相对位的相对位置置,重复此过程,直到,重复此过
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 遗传 算法 课件 PPT