知识卡片

结构图卡 · 3765.c

贪心修复退火邻域不可行解

理解等级:高级

一种背包 SAA 以传统贪心方案为基础,再加入遗传算法的变异和倒位操作扩大搜索。倒位指把染色体上一段基因顺序颠倒,例如 1-2-3-4 把中间两位置倒成 1-3-2-4。每代产生不可行解(通常是超重)后,用贪心算法修正再继续迭代。修复把候选带回可行域,但具体贪心排序规则须由实现另行定义,原文没有给出,不能据此声称修复后的质量或收敛保证。

结构图:

flowchart TD
  A[贪心方案基础] --> B[变异与倒位扩大搜索]
  B --> C[生成新候选解]
  C --> D{满足背包约束?}
  D -- 否 --> E[用贪心算法修正]
  D -- 是 --> F[进入后续迭代处理]
  E --> F
这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《智能算法导论》第 118 项《11.5.1 基于模拟退火算法的0-1背包问题》(源文件:`_epub-src/EPUB/xhtml/chapter11_0013.xhtml`) - 结论依据:原文将变异、倒位用于扩大搜索范围,并明确每代不可行解由贪心算法修正;没有说明贪心修复的排序细节。倒位的四位示意为术语解释,非书中染色体。 - 原始内容:该算法融合了遗传算法中变异算子和倒位算子的思想,扩大了解的搜索范围,同时,在迭代过程中,对每一代产生的不可行解利用贪心算法进行修正。