一、定义

模拟退火算法（Simulated Annealing，SA）是一种通用概率演算法，用来在一个大的搜寻空间内找寻命题的最优解。“模拟退火”算法是源于对热力学中退火过程的模拟，在某一给定初温下，通过缓慢下降温度参数，使算法能够在多项式时间内给出一个近似最优解。最早的思想是由Metropolis在1953年提出，Kirkpatrick等人把模拟退火思想与组合最优化的相似点进行类比，将模拟退火算法引入到组合优化领域。模拟退火算法是解决传统方法难处理的NP完全问题(Nondeterministic Polynomial Complete Problem)，TSP（Traveling Salesman Problem）货郎担问题的有效方法之一。

模拟退火算法是一种高效、通用、易实现的优化算法，适合于解决大规模组合优化问题的通用而有效的近似算法。

模拟退火算法是一种贪心算法，也是一种随机算法，它有较强的局部搜索能力，对参数依赖性较强，并不一定能找到全局的最优解，但可以比较快的找到问题的近似最优解。

SA特别适合并行运算，描述简单、初始条件限制少、使用灵活且效率高，所以被广泛应用。

二、与贪心算法、爬山算法、 梯度下降算法的比较

爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。

爬山算法实现很简单，其主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。如图2-1所示：假设C点为当前解，爬山算法搜索到A点这个局部最优解就会停止搜索，因为在A点无论向那个方向小幅度移动都不能得到更优的解。

图2-1

模拟退火其实也是一种贪心算法，与爬山算法不同，它是下降寻找谷底，并且它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。如图2-2所示，它的搜索路径是A->B->C->D->E->F-G, 最终找到了G这个全局最优解。

图2-2

关于普通贪心算法与模拟退火，有一个有趣的比喻：

普通贪心算法：兔子朝着比现在低的地方跳去。它找到了不远处的最低的山谷。但是这座山谷不一定最低的。 它不能保证局部最优值就是全局最优值。

模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向低处，也可能踏入平地。但是，它渐渐清醒了并朝最低的方向跳去。

梯度下降法和模拟退火算法都是求最优解的方法，但它们也有所不同。利用一阶导数去求极值的梯度下降法，可以求得局部最优解，但不能直接搜索到全局最优解；由于退火算法加入了候选解，候选解由一定的概率密度分布从解空间随机采样获得，故可以取到全局最优解。

三、基本原理

模拟退火算法的出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。物理中固体物质的退火过程由加温阶段、平衡阶段、冷却阶段这三部分组成。加温阶段对应算法的设定初温，平衡阶段对应算法的采样过程，该过程须遵循Metropolis准则，冷却阶段对应算法控制参数下降。模拟退火基本原理如图3-1与图3-2所示。

图3-1 固体退火过程示意图

图3-2 模拟退火算法流程示意图

在把模拟退火算法应用于最优化问题时，一般可以将温度T当做控制参数，目标函数值f视为内能E，而固体在某温度T时的一个状态对应一个解。然后算法试图随着控制参数Ｔ的降低，使目标函数值f(内能E)也逐渐降低，直至趋于全局最小值(退火中低温时的最低能量状态)，就像固体退火过程一样。

四、主要思想

就函数最小值问题来说，模拟退火的主要思想是：在搜索区间（二维平面中）随机游走（即随机选择点），再以Metropolis抽样准则，使随机游走逐渐收敛于局部最优解。而温度即是Metropolis算法中的一个重要控制参数，可以认为这个参数的大小控制了搜索过程向局部或全局最优解移动的快慢。

冷却参数表、领域结构和新解产生器、接受准则和随机数产生器（即Metropolis算法）一起构成算法的三大支柱。

Metropolis是一种有效的重点抽样法：系统从能量一个状态变化到另一个状态时，相应的能量从E1变化到E2，概率为p = exp[ - (E2- E1)/T ]。如果E2 < E1，系统接收此状态，否则，以一个随机的概率接收此或丢弃此状态。这种经常一定次数的迭代，系统会逐渐趋于一引稳定的分布状态。

重点抽样时，新状态下如果向下则接受（局部最优），若向上（全局搜索），以一定机率接受。模拟退火方法从某个初始解出发,经过大量解的变换后,可以求得给定控制参数值时组合优化问题的相对最优解。然后减小控制参数T的值，重复执行Metropolis算法，就可以在控制参数T趋于零时，最终求得组合优化问题的整体最优解。控制参数的值必须缓慢衰减。

其中温度是一个Metropolis的重要控制参数，模拟退火可视为递减控制参数T时Metroplis算法的迭代。开始T值大，可能接受较差的恶化解，随着T的减小，只能接受较好的恶化解，最后在T趋于0时，就不再接受任何恶化解了。

在无限高温时，系统立即均匀分布，接受所有提出的变换。T的衰减越小，T到达终点的时间越长，但可使马可夫链长越小，到达准平衡分布的时间越短，

五、Metropolis准则

模拟退火算法使用Metropolis准则产生组合优化问题解的序列，并使用对应的转移概率P确定是否接受当前解到新解的转移。

1、准则的由来

同样的问题，如果使用蒙特卡洛(MonteCarlo)算法模拟，需要大量采样，工作量很大。因而1953年Metropolis提出了这样一个重要性采样的方法， 即设从当前状态i生成新状态j。若新状态的内能小于状态i的内能(即Ej<Ei)，则接受新状态j作为新的当前状态； 否则，以概率接受状态j， 这就是通常所说的Metropolis准则。

2、准则详解

Metropolis准则，其实就是以概率p接受新状态。

若在温度T，当前状态i → 新状态j，则概率p满足：

当Ej < Ei时，接受新状态的概率p=1, 即完全接受 j 为当前状态；当Ej ≥ Ei时，若概率 p=exp[-(Ej-Ei)/T]大于[0,1)区间的随机数，则仍接受状态 j 为当前状态；若不成立，则保留状态 i 为当前状态。

温度T越小，则降温概率p就越小；温度越高，降温概率p就越大，p越大，则j状态是重要状态的概率就越大。若j是重要状态，则取代i成为当前状态，否则舍弃新状态。再重复以上新状态产生过程。

很明显，在高温下，可接受与当前状态能量差较大的新状态；在低温下，只接受与当前状态能量差较小的新状态。这与不同温度下热运动的影响完全一致，在温度趋于零时，就不能接受任何成立时的新状态j了。

上述接受新状态的准则称为Metropolis准则，相应的算法被称为Metropolis算法。

六、算法实现步骤ＳＡ算法具体步骤:1、流程图表示

图6-1

最简单的状态产生函数：ω’ = ω + R (R是个随机数）。

2、文字描述表示

模拟退火算法用冷却进度表来控制算法的进程，是算法在控制参数T徐徐降温并趋于零时最终求得组合优化问题的相对全局最优解。其中优化问题的一个解i及其目标函数f(i)分别与固体的一个微观状态ｉ及其能量Ｅi相对应。

3、从新解的产生与接受来表示

模拟退火算法新解的产生和接受可分为如下四个步骤：

第1步，由一个产生函数从当前解产生一个位于解空间的新解。为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。

第2步，计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。

第3步，判断新解是否被接受。判断的依据是一个接受准则，最常用的接受准则是Metropolis准则: 若Δt′<0则接受S′作为新的当前解S，否则以概率exp(-Δt′/T)接受S′作为新的当前解S。

第4步，当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。

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

七、算法要素1、状态空间

状态空间，即解空间，也称为搜索空间，是经过编码的可能解组成的集合。

2、状态产生函数

应尽可能保证产生的候选解遍布整个状态空间，可采用附加扰动、随机产生、移位、平滑、边界取值等多种算子作为模拟退火的状态产生函数。状态产生函数通常由产生的候选解的方式和候选解产生的概率分布两部分组成。候选解一般采用按照某一概率密度函数对解空间进行随机采样来获得。概率分布可以是均匀分布、正态分布、指数分布等。

3、状态转移概率状态转移概率是指从一个状态向另一个状态的转移概率。通俗的理解是接受一个新解为当前解的概率。它与当前的温度参数T有关，随温度下降而减小。一般采用Metropolis准则。4、初始温度

实验表明，初始温度越高，得到高质量解的概率越大，但算法计算的时间越长。兼顾算法求解的质量和执行效率，选择初温的方法常有:随机产生一组状态，确定最大值和最小值间的差值d，利用函数得到初温，如 T0= dp，其中p为初始接受概率; 或均匀抽样一组状态，以各状态的目标值的方差为初温。

5、冷却进度表

冷却进度表是指从某一高温状态T向低温状态冷却时的降温管理表，也即温度衰减函数，也可称为退火策略。

最简单的控制参数衰减函数（指数降温）为：

其中a常取值0.5~0.9, 这种退火策略很常用。

经典的模拟退火衰减函数（对数降温）为：可以选择其它的衰减函数：

衰减函数应选择小的比较合适，可避免过长的马尔可夫链和迭代次数增加。

6、内循环终止的准则

内循环终止的准则，也称为Metropolis抽样稳定准则，用于决定各温度下产生候选解的个数，该准则包括有：目标函数的平均值是否稳定；连续若干步目标函数值变化较小；按一定的步数抽样。

7、外循环终止的准则

外循环终止的准则，即决定算法何时结束，主要包括：循环迭代的次数设置；终止温度的阈值设置；检验系统熵值是否稳定；检验算法收敛到最优值连续若干步保持不变。其中终止温度的设置常用的是Kirkpatrick等提出准则：在若干个马尔可夫链中解无任何变化（恶化或优化）就终止算法。迭代次数L的选取与冷却进度表密切相关，一般T衰减小，则 L值就适当大。

八、参数的选择

模拟退火算法的应用很广泛，可以求解NP完全问题，但其参数难以控制，其主要问题有以下几点：

1、状态转换步长

状态转换很重要，状态的搜索、跳转策略直接影响着算法的性能。可采用附加扰动、随机产生、移位、平滑、边界取值等多种算子作为状态产生函数X(i+1) = G(Xi)。

比如根据具体的问题去分析，状态有没有边界，如果有边界的话，在状态跳转时要用边界限制。状态转换是从当前状态至下一状态，每一次跳动都是随机的，但不是完全随机的，是在一定范围内进行的跳动。那么，两个问题来了，

范围怎么确定?范围确定后，状态怎么转换?

退火的跳动幅度是随着温度的下降逐渐降低的，因此，跳动范围须与温度建立关系，随温度下降，跳动范围减少。这个减少可以是线性的，也可以是非线性的。范围确定了，下一次状态的跳转可由高斯随机数生成，通过控制高斯方差就可以控制跳动范围。

状态转换完全随机会怎样？完全随机意味着 状态开始时乱跳，温度降下来后也乱跳，这就就违背了退火算法思想。

2、控制参数初值T0的选取

温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一。初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。

一般要求初始值T0的值要充分大，即一开始就处于高温状态，且Metropolis的接收率约为1。 在无限高温时，系统立即均匀分布，接受所有提出的变换。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。

3、衰减函数的选取　

衰减函数用于控制温度的退火速度，一个常用的指数函数为：T(n + 1) = K*T(n)，其中K是一个非常接近于1的常数。

T的衰减越小，T到达终点的时间越长，但可使马可夫链长越小，到达准平衡分布的时间越短，

4、马可夫链长度L（内循环迭代次数）的选取

马可夫链长度L是指每一次随机游走过程，要迭代多少次，才能趋于一个准平衡分布，即一个局部收敛解位置。

原则是，在衰减参数T的衰减函数已选定的前提下，L应选得在控制参数的每一取值上都能恢复准平衡。

5、终止条件

有很多种终止条件的选择，各种不同的条件对算法的性能和解的质量有很大影响。这里介绍一个常用的终止条件，即上一个最优解与最新的一个最优解的之差小于某个容差，就可停止此次马尔可夫链的迭代。

小结

有效的参数选择判据是：

算法的收敛：主要取决于衰减函数和马可夫链的长度及停止准则的选择；算法的实验性能：最终解的质量和CPU的时间。例子：使用模拟退火法求函数f(x,y) = 5sin(xy) + x^2 + y^2的最小值。

解：根据题意，我们设计参数为：

Metropolis的步长为0.02

初始温度为100

衰减参数为0.95

马可夫链长度为10000

结束条件为根据上一个最优解与最新的一个最优解的之差小于某个容差。

九、算法设计的注意事项

1) 设计合适的状态产生函数，使其根据搜索进程的需要表现出状态的全空间分散性或局部区域性；

2) 设计高效的退火策略；

3) 避免状态的迂回搜索；

4) 采用并行搜索结构；

5) 为避免陷入局部极小，改进对温度的控制方式；

6) 选择合适的初始状态；

7) 设计合适的算法终止准则。

十、模拟退火算法改进策略

通过对模拟退火算法的要素的改进或与其它算法相结合可提高模拟退火算法的性能。

自身要素的改进提升初温。算法初始化，增加升温或重升温过程，将温度适当提高，以激活各状态的接受概率，可以避免算法在局部极小解处停滞不前。增加记忆功能。增加存储环节，将当前最好状态记录下来，避免搜索过程由于因根据 Metropolis准则接受当前解时，可能丢掉当前遇到的最优解。增加补充搜索过程。在退火结束后，把当前最优解设置为初始状态，再次执行模拟退火过程或局部性的搜索。多次搜索策略。对每一当前状态，采用多次搜索策略，取代标准SA算法的单次比较方式。与其它搜索算法相结合。

混合模拟退火算法，模拟退火与遗传算法相结合。近年来，模拟退火算法与遗传算法的融合在计划调度、机器人研究、软硬划分等方向均有应用。因此，今后要进一步深入研究 SA 与 GA 算法的结合，充分利用双方的优势，使其在相应的科学领域发挥更大的作用。

十一、应用

模拟退火算法可以较高的效率求解很多问题, 应用也非常广泛。

1、最大截问题(Max Cut Problem)

2、0-1背包问题(Zero One Knapsack Problem)

3、图着色问题(Graph Colouring Problem)

4、调度问题(Scheduling Problem)

5、在VLSI设计中的应用

利用模拟退火算法进行VLSI的最优设计，是目前模拟退火算法最成功的应用实例之一。用模拟退火算法几乎可以很好地完成所有优化的VLSI设计工作。如全局布线、布板、布局和逻辑最小化等等。

6、在神经网计算机中的应用

模拟退火算法具有跳出局部最优陷阱的能力。在Boltzmann机中，即使系统落入了局部最优的陷阱，经过一段时间后，它还能再跳出来，再系统最终将往全局最优值的方向收敛。

7、在图像处理中的应用

模拟退火算法可用来进行图像恢复等工作，即把一幅被污染的图像重新恢复成清晰的原图，滤掉其中被畸变的部分。因此它在图像处理方面的应用前景是广阔的。

8、模拟退火算法的其他应用

除了上述应用外，模拟退火算法还用于其它各种组合优化问题，如TSP和Knapsack问题等。大量的模拟实验表明，模拟退火算法在求解这些问题时能产生令人满意的近似最优解，而且所用的时间也不很长。

十二、附录附录1 模拟退火算法的数学模型