知识卡片
贪心修复退火邻域不可行解
一种背包 SAA 以传统贪心方案为基础,再加入遗传算法的变异和倒位操作扩大搜索。倒位指把染色体上一段基因顺序颠倒,例如 1-2-3-4 把中间两位置倒成 1-3-2-4。每代产生不可行解(通常是超重)后,用贪心算法修正再继续迭代。修复把候选带回可行域,但具体贪心排序规则须由实现另行定义,原文没有给出,不能据此声称修复后的质量或收敛保证。
结构图:
flowchart TD
A[贪心方案基础] --> B[变异与倒位扩大搜索]
B --> C[生成新候选解]
C --> D{满足背包约束?}
D -- 否 --> E[用贪心算法修正]
D -- 是 --> F[进入后续迭代处理]
E --> F
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 1 1 . 5 . 1 基 于 模 拟 退 火 算 法 的 0 - 1 背 包 问 题 · 查看原书依据
该算法融合了遗传算法中变异算子和倒位算子的思想,扩大了解的搜索范围,同时,在迭代过程中,对每一代产生的不可行解利用贪心算法进行修正。实验结果表明,该算法在一定程度上提高了SAA的全局寻优能力,能求得最优解或近似最优解。
参考来源
- 位置:《智能算法导论》第 118 项《11.5.1 基于模拟退火算法的0-1背包问题》(源文件:`_epub-src/EPUB/xhtml/chapter11_0013.xhtml`)
- 结论依据:原文将变异、倒位用于扩大搜索范围,并明确每代不可行解由贪心算法修正;没有说明贪心修复的排序细节。倒位的四位示意为术语解释,非书中染色体。
- 原始内容:该算法融合了遗传算法中变异算子和倒位算子的思想,扩大了解的搜索范围,同时,在迭代过程中,对每一代产生的不可行解利用贪心算法进行修正。