遗传算法课件PPT.ppt

第三章 遗传算法
1
精选可编辑ppt



(Scaling)


六. 应用
遗传算法
2
精选可编辑ppt
其它编码方法
顺序编码：用1到N的自然数的不同顺序来
编码，此种编码不允许重复，即
且 ，又称自然数编码。
该法适用范围很广：指派问题、旅行商问题和单机调度问题等等。
合法性问题：是否符合采用的编码规则的问题
（1）
3
精选可编辑ppt
实数编码： ,R为实数集
特征：方便运算简单，但反映不出基因的特征
整数编码类似于顺序编码，但编码允许重复
适用于：新产品投入，时间优化，伙伴挑选
例：3212345 对顺序编码来说是不合法的，而
对整数编码来说是合法的；010200不合法的01
编码；
（2）
4
精选可编辑ppt
遗传运算中的问题
在顺序编码遗传运算的过程中会遇见不合法
的编码，应战的策略有二:拒绝或修复。
例如：经双切点交叉后，后代编码不合法
21 ¦ 345 ¦ 67 21 ¦ 125 ¦ 67
43 ¦ 125 ¦ 76 43 ¦ 345 ¦ 76
我们采用下面的修复策略使以上的编码合法。
（3）
5
精选可编辑ppt
顺序编码的合法性修复：
交叉修复策略，分为以下几种：
部分映射交叉
顺序交叉
循环交叉
（4）
6
精选可编辑ppt
部分映射交叉(PMX) ( Partially Mapped Crossover)：用特别的修复程序解决简单的双切点交叉引起的非法性，步骤：
⑴选切点X,Y；
⑵交换中间部分；
⑶确定映射关系；
⑷将未换部分按映射关系恢复合法性。
（5）
7
精选可编辑ppt
PMX例题：
（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
8
精选可编辑ppt
顺序交叉( OX )Order Crossover：可看做是带有不同修复程序的部分映射交叉的变形。
OX步骤：
⑴ 选切点X,Y；
⑵ 交换中间部分；
⑶ 从切点Y后第一个基因起列出原顺序，去掉已有基因；
⑷ 从切点Y后第一个位置起，按顺序填入。
（7）
9
精选可编辑ppt
OX例题：
（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
10
精选可编辑ppt