简介与适用范围
模拟退火是一种随机化算法。当一个问题的方案数极大（甚至是无穷的）而且不是一个单峰函数时，我们常使用模拟退火求解。
解释
根据爬山算法的求解过程，我们发现：爬山算法在对于一个当前最优解附近的非最优解直接舍去了，然而很多情况下，我们需要去接受这个非最优解从而跳出此局部最优解，即为模拟退火算法。
何为退火？
当固体的温度很高时，内能比较大，内部粒子处于快速无序运动状态，当温度渐渐降低时，固体内能减小，粒子运动速度会渐渐下降，逐渐趋于有序，内部粒子基本趋于稳定，达到一个平衡状态。这个过程在金属锻造中经常出现，称为金属退火。
基本策略
- 在当前位置上进行一次扰动，从 x x x 跳至当前位置 x ′ x' x′
- 求出新位置的函数值 y ′ y' y′，如果新位置的函数值更优，则 x − > x ′ x->x' x−>x′
- 如果新位置的函数值更劣，则有一定概率 P P P 跳到新位置，也有一定的概率 P ′ P' P′ 留在原位置。
其中 P P P 满足一下公式（假设函数值小更优）
P = { 1 f ( x ′ ) ≤ f ( x ) e f ( x ) − f ( x ′ ) k T f ( x ′ ) > f ( x ) P=\left\{\begin{matrix}\qquad 1 \qquad f(x')\leq f(x)\\\\ \ e^{\frac{f(x)-f(x')}{kT}} \ f(x')>f(x)\end{matrix}\right. P=⎩⎨⎧1f(x′)≤f(x) ekTf(x)−f(x′) f(x′)>f(x)
当下一个解更优时，则跳到下一个解；如果下一个解更劣时，有一定的概率跳到下一个解。 T T T 表示初始温度， K K K 表示温度下降的速率。
可以看出，当温度越高时，越有可能跳出局部最优解；当温度越小时，越趋向于稳定，越不容易跳出局部最优解。
在温度固定的情况下，模拟退火算法需要迭代多次，迭代的次数越多，越容易找到局部最优解。这个迭代次数称为⻢尔科夫链。
但⻢尔科夫链越⻓，所需要的时间也越多。