知识卡片

普通读书笔记卡 · 1295.i.1.g.1

排列变异改变邻域结构

理解等级:中级

排列编码的变异只调整城市的位置,不增删城市,所以子代仍是合法路线。三种常见做法从同一父代出发,改动的“幅度”不同。

示例(补充演算):父代路线 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 条

“邻域”指一次变异能到达的所有候选。被换掉的边越多,一步跳得越远:相反变异更像细调,交换变异跳得更远。这就是不同算子定义不同搜索邻域的含义。选择算子再按适应度决定哪些候选进入下一代;比较算子时应控制同一问题实例与计算预算。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《智能算法导论》第 1 章 1.3.2 节“变异算子”“选择算子”(`EPUB/xhtml/chapter1_0008.xhtml`);表 1.9–1.13。 - 结论依据:原文分别给出相反、插入、交换、启发式变异的步骤与图例。6 城市路线及“被换掉的边”计数为依据原书各变异步骤补充的教学示例与推导(假设距离对称),非书中图例数据。 - 原始内容:常见的用于序列表示的变异方法有相反变异(inversion mutation)、插入变异(insertion mutation)、交换变异(swap mutation)和启发式变异(heuristic operators)