智能优化方法--遗传算法.ppt

* ⑷变长顺序编码的遗传算法插入式交叉算法 在 上选一个随机的断点； 在 上随机选一个基因片断插入 的断点处； 去掉 上的重复基因； 按优先适合启发式得到可行解 见下页例题 六.应用（9） * 例题： 六.应用（10） 去掉重复基因： 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 5 X * 最小生成树问题(Minimum Spanning Tree) 问题的提出 难点：对于下面的红色的图形，如何设计 一个合适的编码方法？ 六.应用（11） 1 2 3 4 5 6 1 2 4 3 5 7 6 8 9 10 * 传统的编码方法： 节点表示法： 无法避免回路，很难做遗传运算，如： {(1,2),(2,3),(2,5),(2,6),(4,6)} 六.应用（12） 1 2 3 4 5 6 1 2 4 3 5 7 6 8 9 10 * 边编码法： 无法保证是树无法保证可行性 {1,2,4,5,10} 缺点：麻烦，无法做遗传运算，无法保持合法性 六.应用（13） 1 2 3 4 5 6 1 2 4 3 5 7 6 8 9 10 * 为解决以上问题，人们提出了最小生成树 的(Pr?fer数)的编码方法。 最小生成树的定义： 用n-2位自然数唯一的表达出一棵n个节点的 生成树，而且交叉变异仍是一棵生成树。 六.应用（14） * 叶子：树中度数为1的节点 例如：1，3，4，5 最小生成树应用条件： 覆盖所有顶点 连通的 没有回路 六.应用（15） 1 2 3 4 5 6 * 编码步骤 设节点i是标号最小的叶子 令j是编码中的第一个数字，若i与j相连 删去边(i , j) 转Ⅰ,直到剩下一条边为止 六.应用（16） 1 2 3 4 5 6 * 图解：i=1,( i , j )=(1,2),j=2 ; i=3,( i , j )=(3,2) , j=2 i=4,( i , j )=(4,6),j=6 ; i=5,( i , j )=(5,2), j=2 编码：（2 2 6 2） 六.应用（17） 1 2 3 4 5 6 2 3 4 5 6 2 4 5 6 2 5 6 2 6 * 解码步骤 令Pr?fer数中的节点集为 ,不包含在 中的节点集为 ； 若i为 中最小标号的节点，j为 上最左边数字连接边(i , j)，并从 中去掉i，从 中去掉j，若j不再在 中，将j加入 中。 六.应用（18） * 重复Ⅱ，直到 中没有节点(即为空)， 中剩下(s,r) 连接(s,r) 图解过程见下页 六.应用（19） * 例： = [2，2，6，2]， = [1，3，4，5] (1,2) = [2，6，2]， = [3，4，5] (3,2) = [6，2]， = [4，5] (4,6) = [2]， = [5，6] (5,2) = [Ф]， = [2，6] 六.应用（20） 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 * 最小生成树的的优点： 对于一个 个节点的Pr?fer数的个数为 ，生成树的个数也是 。 最小生成树实现了解空间和编码空间的一一对应，交叉变异不破坏合法性。 一个好的编码方法对遗传算法至关重要。 六.应用（21） * 1 7 6 5 2 3 4 [ 2 3 2 4 4 ] 练习: * 1 7 5 [ 6 3 2 4 4 ] P=[ 1 5 7 ] 4 2 3 6 练习: * 作业: 为极大化权和的匹配问题设计一种编码方式 1 2 3 4 5 6 1 2 4 3 5 7 6 8 9 10 * 二次指派问题——机器布置问题(QAP) 机器布置问题 Facility Layout —Quadratic Assignment Problem 六.应用（22） * 问题的提出： 台机器，要布置在 个地方，机器i与k之 间的物流量为 ，位置j与L之间的距离为 ， 如何布置使费用最小。 设： 表示机器i布置在位置j； 其它。 同理对 。 六.应用（23） * 数学模型： 二次0-1规划 六.应用（24） * 用GA求解 编码——顺序编码 表