模拟退火
引入
模拟退火是一种随机化算法。当一个问题的方案数量极大（甚至是无穷的）而且不是一个单峰函数时，我们常使用模拟退火求解。
解释
根据 爬山算法 的过程，我们发现：对于一个当前最优解附近的非最优解，爬山算法直接舍去了这个解。而很多情况下，我们需要去接受这个非最优解从而跳出这个局部最优解，即为模拟退火算法。
什么是退火？（选自 百度百科）
退火是一种金属热处理工艺，指的是将金属缓慢加热到一定温度，保持足够时间，然后以适宜速度冷却。目的是降低硬度，改善切削加工性；消除残余应力，稳定尺寸，减少变形与裂纹倾向；细化晶粒，调整组织，消除组织缺陷。准确的说，退火是一种对材料的热处理工艺，包括金属材料、非金属材料。而且新材料的退火目的也与传统金属退火存在异同。
由于退火的规律引入了更多随机因素，那么我们得到最优解的概率会大大增加。于是我们可以去模拟这个过程，将目标函数作为能量函数。
过程
先用一句话概括：如果新状态的解更优则修改答案，否则以一定概率接受新状态。
我们定义当前温度为 \(T\)，新状态 \(S'\) 与已知状态 \(S\)（新状态由已知状态通过随机的方式得到）之间的能量（值）差为 \(\Delta E\)（\(\Delta E\geqslant 0\)），则发生状态转移（修改最优解）的概率为
注意：我们有时为了使得到的解更有质量，会在模拟退火结束后，以当前温度在得到的解附近多次随机状态，尝试得到更优的解（其过程与模拟退火相似）。
如何退火（降温）
模拟退火时我们有三个参数：初始温度 \(T_0\)，降温系数 \(d\)，终止温度 \(T_k\)。其中 \(T_0\) 是一个比较大的数，\(d\) 是一个非常接近 \(1\) 但是小于 \(1\) 的数，\(T_k\) 是一个接近 \(0\) 的正数。
首先让温度 \(T=T_0\)，然后按照上述步骤进行一次转移尝试，再让 \(T=d\cdot T\)。当 $T
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用