知识卡片
排列变异改变邻域结构
排列编码的变异只调整城市的位置,不增删城市,所以子代仍是合法路线。三种常见做法从同一父代出发,改动的“幅度”不同。
示例(补充演算):父代路线 1-2-3-4-5-6(回到 1),城市间距离对称。
| 变异 | 操作 | 子代 | 路线中被换掉的边 |
|---|---|---|---|
| 相反变异 | 把第 2~4 位倒序 | 1-4-3-2-5-6 | 2 条(1-2、4-5) |
| 插入变异 | 取第 5 位插到第 2 位 | 1-5-2-3-4-6 | 3 条 |
| 交换变异 | 交换第 2 位和第 5 位 | 1-5-3-4-2-6 | 4 条 |
“邻域”指一次变异能到达的所有候选。被换掉的边越多,一步跳得越远:相反变异更像细调,交换变异跳得更远。这就是不同算子定义不同搜索邻域的含义。选择算子再按适应度决定哪些候选进入下一代;比较算子时应控制同一问题实例与计算预算。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 1 . 3 . 2 基 于 遗 传 算 法 的 旅 行 商 问 题 · 查看原书依据
4. 变异算子 常见的用于序列表示的变异方法有相反变异(inversion mutation)、插入变异(insertion mutation)、交换变异(swap mutation)和启发式变异(heuristic operators),下面分别对这些变异算子做相应的介绍。
参考来源
- 位置:《智能算法导论》第 1 章 1.3.2 节“变异算子”“选择算子”(`EPUB/xhtml/chapter1_0008.xhtml`);表 1.9–1.13。
- 结论依据:原文分别给出相反、插入、交换、启发式变异的步骤与图例。6 城市路线及“被换掉的边”计数为依据原书各变异步骤补充的教学示例与推导(假设距离对称),非书中图例数据。
- 原始内容:常见的用于序列表示的变异方法有相反变异(inversion mutation)、插入变异(insertion mutation)、交换变异(swap mutation)和启发式变异(heuristic operators)