模拟退火算法原理详解

当能量差大于0时，注意！这也是模拟退火最具特色的地方。既然能量差大于0，那么不就是说此时的解不如原来那个解吗？但是模拟退火算法这时不会百分百拒绝这个解。它会以一定概率解受这个新解。请你想象，以一段峰值递增的正弦函数图像为例，在第一次峰值期间，当你找到了这个峰值，如果你百分百拒绝了峰值下降时的解，不就一定遍历不到后面更高的峰值，从而陷入局部最优了吗？但是模拟退火算法不会，它会以一定概率接受新解，那么，优势显而易见。

4.概率P

如前文所言，模拟退火会以一定概率接受新解，具体公式如下：

其中，Tt是当前温度，f(B),f(A)分别代指新解与旧解。这是一个很棒的公式，你会发现：

（1）当能量差很大（新解非常烂）时，指数是一个很大的负数，概率P接近于 0，很难接受；

（2）当温度很大（初始高温）时，指数接近于 0，概率接近于 1，几乎来者不拒，尽情在全局探索。

（3）当温度逐渐趋近于 0（冷却阶段）时，P急剧变小，算法逐渐退化为只接受好解的贪心算法。

5.Metropolis 准则

这是你在阅读这种版本模拟退火算法时很大概率会见到的名词，我的理解是，这其实就是3，4两点的概括，即计算能量差，以一定概率接受新解。

6.退温函数与降温系数

退温函数就是你的温度更新函数，最常见的就是T2=a*T1。a是你的降温系数，通常是一个接近1 的常数，常取为0.95 。我认为这个退温函数并不是定死的，当你的算法理解与数学功底够强时，或许你会使用更适合你的问题的退温函数。

7.马尔科夫链

这并不是模拟退火中的重点，但是我阅读模型原理时曾见过，因此也写一下我的理解。我认为它并不是什么具体的算法，它是一种特殊的结构，或许你会在动态规划问题中再见到它。

以模拟退火为例，在你寻找解的过程，你可以得到各个温度下的解，它们组成了解空间。在你寻找解的过程中，某一时刻你找到了一个解，那么它就是你当前状态下的解，所以有了状态空间的说法。而马尔科夫链，是说你当前状态只与前一时刻的状态相关,而与更早的状态无关。它只关心当前状态，具有无记忆性。

因此，模拟退火算法的整个寻优过程，在数学上就是一个马尔科夫链模型。 或者更准确地说，是一系列随着温度变化的马尔科夫链。因为显然你只关心当前状态，而不关心它以前的温度和解是什么样的。

这里推荐我以前看的一篇文章：模拟退火原理

二、模型原理

1.基本原理

在介绍模拟退火之前，先介绍一下爬山法。

爬山法是从当前解的相邻解空间中选择一个最优解作为最新解，直到达到局部最优。坦白的说，就是一种贪心算法。而模拟退火相较爬山法，会以一定概率接受较差的解从而跳出局部最优。

模拟退火来源于物理中固体物质的退火过程，即加热固体至足够高，再让其徐徐冷却，以达到最低能量的基态。该优化算法由初始解和控制参数T开始，对当前解重复产生新解、计算目标函数查、接受或舍弃的迭代，并逐渐减小T，算法终止时的解即为最优解的近似解。整个过程模拟自然界中物理降温的过程，退火过程由冷却进度表控制，包括控制参数的初值T0以及衰减因子a、每个T值时的迭代次数和停止条件。

另外提一下，我在最早接触的时候，一直很疑惑，既然我有了退温函数，为什么还要在这个温度下迭代n次呢？我不停变温搜索最佳解不就行了？实际上是这样的：

模拟退火的搜索过程，其实涉及到一个概率上的分布。在某一温度下迭代n次，是为了找到当前温度下的热平衡状态；你可以理解为当前温度下搜索解时，我根据解更新函数不断更新，解是会有一个聚集的；即当前温度下最佳解应该是聚集在一片的，也就是热平衡所在的位置；而不好的解分布就相对比较稀疏，我们设置单一温度下的迭代就是为了找到稳定解所在的位置。然后温度降低，意味着进入稀疏区的概率更低了（参考概率P的公式），不断震动收缩，最后得到最优解，所以大多数模拟退火过程图表现为有高有低的山峰。同时这也是为什么当你的迭代次数不达标时，出现退火不充分的原因。

流程图：