知识卡片
退火按温度进度表迭代
模拟退火把目标函数映射为能量,把温度映射为控制参数 t。从初始解和 t 的初值出发,反复执行:
- 对当前解产生一个候选新解。
- 计算目标差 Δ(新解减当前解)。
- 按 Metropolis 准则决定是否接受:Δ < 0 直接接受,否则以 exp(−Δ/T) 的概率接受,见 [[较差候选仍可按温度概率接受]]。
- 按冷却进度表降低 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 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 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 的值逐渐减少,