模拟退火算法（simulated annealing，简称SA）的思想最早是由Metropolis 等（1953）提出的，1983年Kirkpatrick等将其用于组合优化。SA算法是基于Mente Carlo迭代求解策略的一种随即巡游算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随即寻目标函数的全局最优解，即在局部优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，目前已在工程中得到了广泛的应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、图像处理等领域。本章将从优化流程、操作、算法理论与技术等方面对模拟退火算法进行介绍。 黄宝世
2.1 模拟退火算法
模拟退火算法最早是针对组合优化提出的。其目的在于：（1）为具有NP复杂性的问题提供有效的近似求解算法；（2）克服优化过程陷入局部极小；（3）克服初值依赖性。模拟退火算法的基本思想出于物理退火过程，因此我们首先简单介绍物理退火过程。
2.1.1 物理退火过程和Metropolis准则
才智中南简单而言，物理退火过程由以下三部分组成：
（1）加温过程。其目的是增强粒子的热运动，使其偏离平衡位置。当温度足够高时，固体将熔解为液体，从而消除系统原先可能存在的非均匀
态，使随后进行的冷却过程以某一平衡态为起点。熔解过程与系统的熵
增过程相联系，系统能量也随温度的升高而增大。
国家海洋局极地办（2） 等温过程。物理学的知识告诉我们，对于与周围环境交换热量而温
度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态。 （3） 冷却过程。其目的是使粒子的热运动减弱并渐趋有序，系统能量逐
渐下降，从而得到低能的晶体结构。
固体在恒定温度下达到热平衡的过程可以用Mente Carlo 方法加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，因而计算量很大。鉴于物理系统倾向于能量较低的状态，而热运动又妨碍 它准确落到最低态的图像，采样时着重取那些有重要贡献的状态则可较快达到较好的结果。因此，Metropolis 等在1953年提出了重要性采样法，即以概率接受新状态。具体而言，在温度t ，由当
前状态i 产生新状态j ，两者的能量分别为i E 和j E ，若i E <j E ，则接受新状态j 为当前状态；否则，若概率]/)(exp[kt E E p i j r --=大于[0,1)区间内的随机数则仍旧接受新状态j 为当前状态，若不成立则保留状态i 为当前状态，其中k 为Boltzmann 常数。当这种过程多次重复，即经过大量迁移厚，系统将趋于能量较低的平衡态，各状态的概率分布将趋于某种正则分布，如Gibbs 正则分布。同时，我们也可以看到，这种重要性采样过程在高温下可接受与当前状态能量差较大的新状态，而在低温下基本只接受与当前能量差较小的新状态，这与不同温度下热运动的影响完全一致，而且当温度趋于零时，就不能接受比当前状态能量高的状态。这种接受准则通常称为Metropolis 准则，它的计算量相对Mente Carlo 方法要显著减少。
2.1.2 组合优化与物理退火的相似性
前文已指出，所谓组合优化即寻最优解*s ，使得Ω∈∀i s ，)(min )(*i s C s C =，其中{}n s s s ,,21=Ω为所有状态构成的解空间，)(i s C 为状态i s 对应的目标函数值。基于Metropolis 接受准则的优化过程，可避免搜索过程陷入局部极小，并最终趋于问题的全局最优解，如图2.1.1所示。而传统的“瞎子爬山”方法显然做不到这一点，从而也对初值具有依赖性。
因此，基于Metropolis 接受准则的优化过程与物理退火过程存在一定的相似性，我们用表2.1.1归纳。
表2.1.1
2.1.3模拟退火算法的基本思想和步骤
1983年Kirkpatrick 等意识到组合优化与物理退火的相似性，并受到Metropolis 准则的启迪，提出了模拟退火算法。归纳而言，SA 算法是基于Mente Carlo 迭代求解策略的一种随机算法，其出发点是基于物理退火过程与组合优化之间的相似性，SA 由某一较高初温开始，利用具有概率突跳特性的Metropolis 抽样策略在解空间中进行随机搜索，伴随温度的不断下降重复抽样过程，最终得到问题的全局最优解。
标准模拟退火算法的一般步骤可描述如下：
ka5q1265rf（1） 给定初温0t t =，随机产生初始状态0s s =，令0=k ；
（2） Repeat ：
（2.1）Repeat ：
（2.1.1）产生新状态)(s Genete
梁茂春
s j =； （2.1.2）{
}j k j s s random t s C s C if =≥--]1,0[]/))()((exp[,1min ； （2.1.3）Until 抽样稳定准则满足；
（2.2）退温)(1k k t update
t =+并令1+=k k ； （3）Until 算法终止准则满足；
（4）输出算法搜索结果。
上述模拟退火算法可用流程框图（如图2.1.2所示）直观描述。
从算法结构知，新状态产生函数、新状态接受函数、退温函数、抽样稳定准则和退火结束准则（简称三函数两准则）以及初始温度是直接影响算法优化结果的主要环节。模拟退火算法的试验性能具有质量高、初值鲁棒性强、通用易实现的优点。但是，为寻到最优解，算法通常要求较高的初温，较慢的降温速率、较低的终止温度以及各温度下足够多次的抽样，因而模拟退火算法往往优化过程较长，这
也是SA 算法最大的缺点。因此，在保证一定优化质量的前提下提高算法的搜索效率，是对SA 进行改进的主要内容。
2.2模拟退火算法的马氏链描述
令{} ,,21s s =Ω为所有状态构成的解空间，)(k X 为k 时刻状态变量的取值。随机序列{})(k X 称为马氏链，若+∈∀Z n ，满足
{}i n X i X i X j n X =-===)1(,,)1(,)0()(Pr 10 ＝{}i n X j n X =-=)1()(Pr
并称
=-)1(,n p j i {}i n X j n X =-=)1()(Pr
为一步转移概率，记n 步转移概率为
=)(,n j i p {}i X j n X ==)0()(Pr
马氏链称为有限状态马氏链，若解空间有限。马氏链称为时齐的，若
+∈∀Z n ，=)(,n p j i )1(,-n p j i
我们约定，以下讨论的SA 算法对应的马氏链为有限状态马氏链。
考察模拟退火算法的搜索过程，算法从一个初始状态开始后，每一步状态转移均是在当前状态i 的邻域i N 中随机产生新状态j ，然后以一定概率进行接受的。可见，接受概率仅依赖于新状态和当前状态，并由温度加以控制。因此，SA 算法对应了一个马氏链。若固定每一温度t 算法均计算马氏链的变化直至平稳分布，然后下降温度，则称这种算法为时齐算法。若无需各温度下算法均达到平稳
分布，但温度需按一定的速率下降，则称这种算法为非时齐算法或非平稳马氏链算法。
马氏链可用一个有向图G=(V ，E)表示，其中V 为所有状态构成大顶点集，E ＝{}i N j V j i j i ∈∈,,),(为边集。
记j i g ，为由状态i 产生j 的概率，则
⎩⎨⎧∉∈=j i j
i N j N j i g j i g g ,0
),(/),(, 其中 ∑∈=
i N j j i g i g ),()(
它通常与温度无关。若新状态在当前状态的邻域中以同等概率产生，则
i N i g j i g /1)(/),(= 其中i N 为状态i 的邻域中状态总数。
记j i a ，为由状态i 接受状态j 的概率，接受概率通常定义为
{}]/))()((exp[,1min ,t i C j C a j i --=
其中)(∙C 为目标函数，t 为温度参数。
记j i p ，为由状态i 到状态j 的转移概率，则有
⎪⎪⎩⎪⎪⎨⎧=-≠∉≠∈=∀∑∈i N k k i i i j i j i j i i j t p i j and N j i j and N j t a g t p j
论正当防卫i ),(1,
0),()(,,,,, 模拟退火算法要实现全局收敛，直观上，它必须满足以下条件：（1）状态可达性，即对应马氏链的状态图是强连通的；（2）初值鲁棒性，即算法的最终结果不依赖初值；（3）极限分布的存在性。下面，我们从理论上对SA 算法的收敛性进行分析。
2.3 模拟退火算法的收敛性
2.3.1 时齐算法的收敛性
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议