模拟退火

引入

模拟退火是一种随机化算法。当一个问题的方案数量极大（甚至是无穷的）而且不是一个单峰函数时，我们常使用模拟退火求解。

解释

根据爬山算法的过程，我们发现：对于一个当前最优解附近的非最优解，爬山算法直接舍去了这个解。而很多情况下，我们需要去接受这个非最优解从而跳出这个局部最优解，即为模拟退火算法。

什么是退火？（选自百度百科）

退火是一种金属热处理工艺，指的是将金属缓慢加热到一定温度，保持足够时间，然后以适宜速度冷却。目的是降低硬度，改善切削加工性；消除残余应力，稳定尺寸，减少变形与裂纹倾向；细化晶粒，调整组织，消除组织缺陷。准确的说，退火是一种对材料的热处理工艺，包括金属材料、非金属材料。而且新材料的退火目的也与传统金属退火存在异同。

由于退火的规律引入了更多随机因素，那么我们得到最优解的概率会大大增加。于是我们可以去模拟这个过程，将目标函数作为能量函数。

过程

先用一句话概括：如果新状态的解更优则修改答案，否则以一定概率接受新状态。

我们定义当前温度为 $T$ ，新状态 $S^{'}$ 与已知状态 $S$ （新状态由已知状态通过随机的方式得到）之间的能量（值）差为 $Δ E$ （ $Δ E ⩾ 0$ ），则发生状态转移（修改最优解）的概率为

P (Δ E) = {\begin{cases} 1, & S^{'} is better than S, \\ e^{\frac{- Δ E}{T}}, & otherwise . \end{cases}

注意：我们有时为了使得到的解更有质量，会在模拟退火结束后，以当前温度在得到的解附近多次随机状态，尝试得到更优的解（其过程与模拟退火相似）。

如何退火（降温）？

模拟退火时我们有三个参数：初始温度 $T_{0}$ ，降温系数 $d$ ，终止温度 $T_{k}$ 。其中 $T_{0}$ 是一个比较大的数， $d$ 是一个非常接近 $1$ 但是小于 $1$ 的数， $T_{k}$ 是一个接近 $0$ 的正数。

首先让温度 $T = T_{0}$ ，然后按照上述步骤进行一次转移尝试，再让 $T = d \cdot T$ 。当 $T

本页面最近更新：2025/8/29 18:05:34，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Ir1d, abc1763613206, Mout-sea, Siyuan, sshwy, Tiphereth-A, 7F88FF, ChungZH, Enter-tainer, Ghastlcon, Henry-ZHR, HeRaNO, hsfzLZH1, iamtwz, kenlig, ouuan
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用