模拟退火是一种通用概率算法，用来在固定时间内寻求一个大的寻找空间内找到的最优解。

简介

模拟退火来自冶金学的专有名词退火。退火是将材料加热后再经特定速率冷却，目的是增大晶粒体积，并且减少晶格中的缺陷。材料中的原子原来会停留在使内能有局部最小值的位置，而随机在其他位置中移动。退火冷却时速度较慢，使得原子有较多可能可以找到内能比原来更低的位置。

模拟退火的原理也和金属退火的原理近似：我们将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。

模拟退火问题大方向是属于贪心算法一类，关于贪心算法的介绍，详见我的这篇文章

详探贪心算法

模拟退火

考虑寻找一个低能量系统的问题，其状态由一个马尔科夫链排序。

其中 F 表示的是物理系统中的自由能量。

温度 T 可视为一种伪温度，它控制表示神经元“突触噪声”的热波动。它的精确标度因而无关紧要。相应的，我们可以定义概率 p_i 和抛分函数(partition函数) Z 如下：

和

由F = < E > - TH观察到当温度 T 趋近于零，系统的自由能量F趋近平均能量 。由 F -> < E >，我们观察到由自由能量最小化原则，该马尔科夫链的平稳分布(即Gibbs分布)，当 T -> 0 时塌陷到平均能量 < E > 的全局最小点。换句话说，序列中的低能状态在低温时受到更强的支持。这些观察促使我们提出问题：为什么不简单应用 Metropolis 算法产生大量的代表该随机系统在低温下的构成(Configuration)？我们不提倡使用使用这种策略是因为在很低温度下马尔科夫链到热平衡的收敛速度特别慢。而提高计算效率更好的方法是在较高温度运行随机系统，这是达到平衡状态的收敛相当快，接着随温度的精细下降保持系统的平衡态。也就是我们使用两个相关成分的组合：

• 一个决定温度下降速度的调度表
• 一个算法迭代求解每个温度表给出的新的温度下的平衡分布，这是利用前面温度时的最终状态作为新温度时的起始点

我们刚才提到的两步格式是被广泛使用的以模拟退火著称的随机松弛技术的精华。

模拟退火的最初的目的是寻找刻画复杂大系统的代价函数的全局最小点。正式因为如此，他提供一个求解非凸最优化问题的有力工具

当优化一个非常庞大的大系统（即具有许多自由度的系统）时不要求总是下降而是试图要求大部分时间在下降

模拟退火在两方面与传统的迭代优化算法不同：

• 算法不会陷入局部最小，因为当系统在非零度温度上运行时脱离局部最小总是可能的
• 模拟退火是自适应的，在高温时看见系统的终态的大致轮廓，而它的具体细节在低温度时才呈现出来。

演算步骤

初始化

生成一个可行的解作为当前解输入迭代过程，并定义一个足够大的数值作为初始温度。

迭代过程

迭代过程是模拟退火算法的核心步骤，分为新解的产生和接受新解两部分：

• 由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。
• 计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。
• 判断新解是否被接受，判断的依据是一个接受准则，最常用的接受准则是Metropolis准则：若Δt′<0则接受S′作为新的当前解S，否则以概率exp（-Δt′/T）接受S′作为新的当前解S。
• 当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。

模拟退火算法与初始值无关，算法求得的解与初始解状态S（是算法迭代的起点）无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率1收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。

停止准则

温度T降至某最低值时，完成给定数量迭代中无法接受新解，停止迭代，接受当前寻找的最优解为最终解。

退火方案

在某个温度状态T下，当一定数量的迭代操作完成后，降低温度T，在新的温度状态下执行下一个批次的迭代操作。

退火进度表

如前面所提到的，模拟退火过程的基础是 Metropolis 算法，其间温度 T 慢慢下降。也就是说，温度 T 起调节作用。假定温度下降没有对数快，则模拟退火过程将手链于一个具有最小能量的构型。遗憾的是这种退火进度太慢了–慢的不切实际。实际上，我们必须求诸于算法的渐进收敛的有限时间逼近。这种逼近所付出的代价是算法不再以概率 1 保证找到全局最小点。然而算法的逼近结果在许多实际应用中能产生近似最优解。

为了实现模拟退火算法的有限时间接近，我们必须设定一系列控制算法的有限序列值，以及每一温度值下有限的转移尝试次数。Kirlpatrick 等给出的退火进度表的感兴趣的参数设定如下：

• 温度的初始值。温度的初始值 T₀ 选的足够高使得所有提出的转移实际都能被模拟退火算法所接受
• 温度的下降。一般地说，冷却是按指数形式完成的，并且温度值的改变量都很小。特别地，下降函数定义为： T_k = α * T_k-1, k = 1,2,3… 其中 α 小于但接近于1。α 的典型值介于 0.8 到 0.99 之间。对每一温度，有足够的转移的尝试，使得平均每次实验有 10 次转移被接受。
• 温度的最后值。如果在三次相连的温度下没有得到预期的接收次数，则系统被冻结且退火停止。

后一个标准可以改进，要求接受率小于一预定值，而接受率定义为转移接受的次数除以提出转移的次数。

模拟退火用于组合优化

模拟退火特别适用于解组合优化问题。组合优化的目标是针对有很多可能解的有限离散系统，最小化它的代价函数。本质上讲模拟退火利用 Metropolis 算法通过多粒子物理系统和组合优化问题间的类比一些列解。

在模拟退火中，我们把上面式子中的 p_i 的 Gibbs 分布中的能量 E_i 解释成能量的代价，而温度 T 解释为控制参数。在组合优化问题中对每一构型赋予一数值的代价以描述这个特殊的构型和解的差异。模拟退火程序中下一个需要考虑的问题是确认构型和从已有构型以局部方式产生新的构型。这就是 Metropolis 算法发挥作用之处。因此我们概括统计物理的术语和组合优化术语之间的关系如下表所示。

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/*
 *  J(y)：在状态y时的评价函数值
 *  Y(i)：表示当前状态
 *  Y(i+1)：表示新的状态
 *  r： 用于控制降温的快慢
 *  T： 系统的温度，系统初始应该要处于一个高温的状态
 *  T_min ：温度的下限，若温度T达到T_min，则停止搜索
*/
while( T > T_min ) {
　　dE = J( Y(i+1) ) - J( Y(i) ) ;  
	 //表达移动后得到更优解，则总是接受移动
　　if ( dE >= 0 ) 
　　		//接受从Y(i)到Y(i+1)的移动
        Y(i+1) = Y(i) ;  
　　else {t
    // 函数exp( dE/T )的取值范围是(0,1) ，dE/T越大，则exp( dE/T )也越大
        if ( exp( dE/T ) > random( 0 , 1 ) ) 
        		 //接受从Y(i)到Y(i+1)的移动
            Y(i+1) = Y(i); 
　　}
　　//降温退火 ，0<r<1 。r越大，降温越慢；r越小，降温越快
　　T = r * T ;  
　　//若r过大，则搜索到全局最优解的可能会较高，但搜索的过程也就较长。
　　//若r过小，则搜索的过程会很快，但最终可能会达到一个局部最优值
　　i ++ ;
}

小结

模拟退火用白话来讲就像当于一个进化版的爬山算法（爬山算法：只能搜索到局部的最优解），而模拟退火在搜索过程中引入了随机因素。

即模拟算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，从而达到全局的最优解。

简单描述：

• 若J( Y(i+1) )>= J( Y(i) ) (即移动后得到更优解)，则总是接受该移动
• 若J( Y(i+1) )< J( Y(i) ) (即移动后的解比当前解要差)，则以一定的概率接受移动，而且这个概率随着时间推移逐渐降低（逐渐降低才能趋向稳定）

模拟退火算法是一种随机算法，并不一定能找到全局的最优解，可以比较快的找到问题的近似最优解。 如果参数设置得当，模拟退火算法搜索效率比穷举法要高。