知识卡片

普通读书笔记卡 · 3775.a.1

跨颜色组移动构造禁忌邻域

理解等级:中级

固定 K 个频谱组(即 K 种颜色),把一个飞蜂窝顶点 c 从当前组 Vᵢ 移到另一组 Vⱼ,记为动作 (c, Vᵢ, Vⱼ);当前解所有这类动作构成邻域。N 个顶点各有 K−1 个去向,邻域共 N(K−1) 个动作。

示例(补充):顶点 1–2、2–3 互相干扰,K=2,当前解 V₁={1,2}、V₂={3},同组干扰对 1–2 记 1 次冲突。动作 (1,V₁,V₂) 得 V₁={2}、V₂={1,3},1 与 3 不干扰,冲突降为 0。

每步选执行后冲突数(同频干扰数)最小的动作,再结合禁忌与藐视规则决定是否执行。这个算子只改变顶点所属组,不直接改变 K,适合在给定频谱数下减少冲突;问题映射见[[飞蜂窝干扰图映射频谱]]。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《智能算法导论》第 138 项《1 4 . 3 . 2 算 法 实 现 具 体 步 骤》(源文件:`_epub-src/EPUB/xhtml/chapter14_0007.xhtml`) - 结论依据:步骤5把顶点从一个集合移至另一集合定义为动作并构成邻域,步骤6按动作后的适应度选择候选,步骤7再检查禁忌与藐视规则。三顶点移动示例和 N(K−1) 计数为依据步骤定义补充的教学示例与推导,非书中数据。 - 原始内容:将当前解 S ={ V , V ,…, V k }中顶点集合 V i 中的顶点 c ,从顶点集合 V i 移动到顶点集合 V j ,记为动作( c , V i , V j ),1≤ i ≤ K ,1≤ j ≤ K , i ≠ j 。用当前解 S 的所有动作,构成当前解 S 的邻域neigh。