知识卡片
排列编码须保持城市唯一
旅行商问题(TSP)要求每个城市恰好访问一次,所以染色体必须是城市编号的一个排列。保证这一点有两条路:
- 直接表示:染色体就是访问顺序,如 9 城市的 3-2-5-4-7-1-6-9-8。普通的片段交换会让子代出现重复或缺失的城市,因此要用部分映射交叉(PMX)等保排列算子:交换片段后,按两个父代的对应关系把重复城市换掉,使子代重新合法。
- 随机数(随机键)表示:每位基因是 (0,1) 内的实数,解码时把各位从大到小排名,名次就是该位代表的城市。例如某位是 0.23、排名第 6,就译成城市 6。任何实数向量都能译成一个合法排列,交叉变异可以照常做在实数上。
第二条思路可迁移到调度:置换流水车间调度中,最小位置值、最大顺序值(LOV)等规则同样用“按数值排序”把差分进化(DE)的连续向量译成工件排列。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 1 0 . 4 . 1 基 于 差 分 进 化 算 法 的 置 换 流 水 线 调 度 · 查看原书依据
采用最小位置值的方法可将连续空间映射为离散空间,从而使得DE算法可用于求解序列调度问题。实验表明,该算法在解决实际生产问题时,表现出良好的性能,在问题规模较大时,算法也有较高的效率。
参考来源
- 位置:《智能算法导论》第 1 章 1.3.2 节“编码方式”“交叉算子”(`EPUB/xhtml/chapter1_0008.xhtml`);图 1.3–1.8。
- 结论依据:原文比较直接表示法与随机数表示法,并以 PMX 展示交叉后子代的合法化。
- 原始内容:因为每一个城市只能经过一次,所以不同基因位上的城市编号是不重复的。
- 位置:《智能算法导论》第 10 章《10.4.1 基于差分进化算法的置换流水线调度》(源文件:`_epub-src/EPUB/xhtml/chapter10_0011.xhtml`)
- 结论依据:本节指出可用最小位置值将连续空间映射到离散序列调度;这与随机键解码同属通过排序恢复合法排列的表示思路。
- 原始内容:采用最小位置值的方法可将连续空间映射为离散空间,从而使得DE算法可用于求解序列调度问题。