知识卡片

结构图卡 · 3741.e

退火按温度进度表迭代

理解等级:高级

模拟退火把目标函数映射为能量,把温度映射为控制参数 t。从初始解和 t 的初值出发,反复执行:

  1. 对当前解产生一个候选新解。
  2. 计算目标差 Δ(新解减当前解)。
  3. 按 Metropolis 准则决定是否接受:Δ < 0 直接接受,否则以 exp(−Δ/T) 的概率接受,见 [[较差候选仍可按温度概率接受]]。
  4. 按冷却进度表降低 t,直到满足停止条件,输出当前解作为近似最优解。

冷却进度表是这套循环的“节奏表”,规定四件事:t 的初值、t 怎样衰减、每个温度下尝试多少个候选、何时停止。原文举出的停止条件是连续若干个新解都没有更新。

注意原书一处不一致:正文步骤要求温度乘以一个 0 到 1 之间的固定常数,配图却画成随机因子,两种表述不强行合并。物理类比帮助组织搜索,具体全局收敛仍需满足相应假设。

结构图:

flowchart TD
  A[初始解与控制参数初值] --> B[产生候选新解]
  B --> C[计算目标函数差]
  C --> D{按准则接受?}
  D -- 是 --> E[更新当前解]
  D -- 否 --> F[保留当前解]
  E --> G[按冷却进度表调整参数]
  F --> G
  G --> H{达到停止条件?}
  H -- 否 --> B
  H -- 是 --> I[输出当前近似解]
这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 1 1 . 2 模 拟 退 火 算 法 实 现 · 查看原书依据

      用固体退火模拟组合优化问题,将内能E模拟为目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的SAA:由初始解i和控制参数初值t开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t值,算法终止时的当前解即为所得近似最优解,这是基于蒙特卡洛迭代求解法的一种启发式随机搜索过程。

    参考来源

    - 位置:《智能算法导论》第11章《1 1 . 2 . 1 模 拟 退 火 算 法 基 本 思 想》(源文件:`_epub-src/EPUB/xhtml/chapter11_0004.xhtml`) - 结论依据:正文明确给出初始解/参数、产生新解、计算目标差、接受或舍弃、逐步衰减和终止输出顺序,并列出冷却进度表的四类控制项。 - 原始内容:由初始解 i 和控制参数初值 t 开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减 t 值,算法终止时的当前解即为所得近似最优解 - 位置:《智能算法导论》第11章《1 1 . 2 . 2 模 拟 退 火 算 法 流 程》(源文件:`_epub-src/EPUB/xhtml/chapter11_0005.xhtml`) - 结论依据:正文说明每温度下的迭代次数、连续若干解不更新的停止条件和固定比例降温;图11.1却标注随机因子,覆盖记录保留两者差异。 - 原始内容:终止条件通常取为连续若干个新解都没有更新时终止算法。 - 原始内容:步骤7: T 乘以一个大于0小于1的常数, T 的值逐渐减少,