知识卡片

结构图卡 · 3765.a

背包先验可行再退火接受

理解等级:高级

普通 Metropolis 准则只看目标变化,背包问题还有承重约束,所以用扩充后的准则,按顺序判断候选:

  1. 候选总重超过背包容量:接受概率为 0,直接拒绝。
  2. 可行且总价值增加(Δf > 0,Δf 为新解价值减当前价值):一定接受。
  3. 可行但价值不增(Δ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
这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《智能算法导论》第 118 项《11.5.1 基于模拟退火算法的0-1背包问题》(源文件:`_epub-src/EPUB/xhtml/chapter11_0013.xhtml`;式 11-7) - 结论依据:式 11-7 将超容量情形设为零概率、可行且价值增加设为必然接受,其余分支使用温度控制的指数概率;因此容量可行性先于退火对目标变化的接受判断。Δf = −10 的两档温度演算为依据该式补充的教学示例,非书中数据。 - 原始内容:0-1背包问题是一个有约束优化问题,所以此处采用扩充后的Metropolis准则;其中,t为温度控制参数。