知识卡片
背包先验可行再退火接受
普通 Metropolis 准则只看目标变化,背包问题还有承重约束,所以用扩充后的准则,按顺序判断候选:
- 候选总重超过背包容量:接受概率为 0,直接拒绝。
- 可行且总价值增加(Δf > 0,Δf 为新解价值减当前价值):一定接受。
- 可行但价值不增(Δf ≤ 0):以
exp(Δf/t)的概率接受,t 为温度。
背包是求最大值,所以变差时 Δf 为负,exp(Δf/t) 落在 0 到 1 之间。示例(补充演算):Δf = −10 时,t = 100 的接受概率为 e^(−0.1) ≈ 0.90,t = 10 时为 e^(−1) ≈ 0.37。温度只调节对较差可行解的容忍度,不能替代第 1 步的容量检查。
原书将重量约束中的选择变量写作 x(x),疑似记号错误,卡片不据此推导公式。
结构图:
flowchart TD
A[产生候选背包] --> B{候选重量超过容量?}
B -- 是 --> C[拒绝]
B -- 否 --> D{价值变化 Δf 大于 0?}
D -- 是 --> E[接受]
D -- 否 --> F["按 exp(Δf/t) 概率接受"]
C --> G[保留当前解]
E --> H[转到候选解]
F --> I{随机判定接受?}
I -- 是 --> H
I -- 否 --> G
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 1 1 . 5 . 1 基 于 模 拟 退 火 算 法 的 0 - 1 背 包 问 题 · 查看原书依据
根据新解的产生方式可知,算法迭代一次后,背包中重量的变化为: 价值的变化为: (5)接受准则:0-1背包问题是一个有约束优化问题,所以此处采用扩充后的Metropolis准则 其中,t为温度控制参数。
参考来源
- 位置:《智能算法导论》第 118 项《11.5.1 基于模拟退火算法的0-1背包问题》(源文件:`_epub-src/EPUB/xhtml/chapter11_0013.xhtml`;式 11-7)
- 结论依据:式 11-7 将超容量情形设为零概率、可行且价值增加设为必然接受,其余分支使用温度控制的指数概率;因此容量可行性先于退火对目标变化的接受判断。Δf = −10 的两档温度演算为依据该式补充的教学示例,非书中数据。
- 原始内容:0-1背包问题是一个有约束优化问题,所以此处采用扩充后的Metropolis准则;其中,t为温度控制参数。