1、第十三章第十三章 模拟退火算法模拟退火算法徐从富徐从富浙江大学人工智能研究所浙江大学人工智能研究所2003年年11月月本章主要参考文献：本章主要参考文献：1 张颖张颖, 刘艳秋刘艳秋. 软计算方法软计算方法. 科学出版社科学出版社, 2002. pp109-133.2 Kirkpatrick, Gelatt et al. Optimization by simulated annealing , 1983.3 Arts, Korst. Simulated Annealing and Boltzmann Machines, 1989. 4 Ingber. Very fast simulated
2、reannealing , 1989. 5 Ingber. Simulated annealing : Practice versus theory , 1993. 6 Greening. Parallel simulated annealing techniques, 1990. 7 Azencott. Simulated Annealing : Parallelization Techniques, 1992. 8 Hajek, Sasaki. The time complexity of maximum matching by simulated annealing. 1988.9 Wh
3、ite. Concepts of scale in simulated annealing, 1984.10 Eglese. Simulated annealing : a tool for operational research, 1990. 11 Chiang, Chow. the convergence rates of annealing processes, 1988. 12 Durand, White. Permissible error in parallel simulated annealing, 1991. 13 Diekmann, Lulling et al. A ge
4、neral purpose distributed implementation of simulated an. , 1991. 14 Durand. Trading Accuracy for Speed in Parallel Simulated Annealing A. , 1990. 本章基本内容：本章基本内容：13.1 概述概述13.2 模拟退火算法的收敛性分析模拟退火算法的收敛性分析13.3 模拟退火算法的关键参数控制模拟退火算法的关键参数控制13.4 模拟退火算法的应用模拟退火算法的应用13.1 概概 述述 1982年，年，Kirkpatrick等将热力学中的等将热力学中的退火思
5、退火思想想引入组合优化领域，提出一种解决引入组合优化领域，提出一种解决大规模组合大规模组合优化问题优化问题（特别是（特别是NP完全问题）的有效近似算完全问题）的有效近似算法法模拟退火模拟退火（Simulated Annealing，简称简称SA）算法。算法。 SA算法源于对算法源于对固体退火过程固体退火过程的模拟，采用的模拟，采用Metropolis接受准则接受准则，并用一组称为，并用一组称为冷却进度表冷却进度表的的参数控制算法进程，使算法在多项式时间里给出参数控制算法进程，使算法在多项式时间里给出一个一个近似最优解近似最优解。 从本质上说，从本质上说，SA算法是进化计算中的一种特算法是进化计
6、算中的一种特殊方法。殊方法。13.1.1 物理退火过程物理退火过程1 1、基本概念、基本概念 物理中的固体退火是先将固体加热至熔化，物理中的固体退火是先将固体加热至熔化，再再徐徐徐徐冷却，使之凝固成规整晶体的热力学。冷却，使之凝固成规整晶体的热力学。 （1）熔解熔解：当固体加热至溶解温度时，其规：当固体加热至溶解温度时，其规则性被彻底破坏，固体熔化为液体，粒子排列从则性被彻底破坏，固体熔化为液体，粒子排列从较有序的结晶态转变为无序的液态。较有序的结晶态转变为无序的液态。 熔解过程的目的熔解过程的目的：消除系统中原先可能存在：消除系统中原先可能存在的非均匀状态，使随后进行的冷却过程以某一平的非均
7、匀状态，使随后进行的冷却过程以某一平衡态为始点。衡态为始点。 熔解过程与系统的熔解过程与系统的熵增熵增过程相联系，系统能过程相联系，系统能量随温度的升高而增大。量随温度的升高而增大。 （2）退火退火：冷却时，液体粒子的热运动渐渐：冷却时，液体粒子的热运动渐渐减弱，随着温度的减弱，随着温度的徐徐徐徐降低，粒子运动渐趋有序。降低，粒子运动渐趋有序。当温度降至当温度降至结晶温度结晶温度后，粒子运动变为围绕晶体后，粒子运动变为围绕晶体格点的微小振动，液体凝固成固体的晶态。这个格点的微小振动，液体凝固成固体的晶态。这个过程称为退火。过程称为退火。 退火过程必须退火过程必须 “徐徐徐徐”进行的原因进行的原
8、因：使系统：使系统在每一温度下都达到平衡态在每一温度下都达到平衡态，最终达到固体的基，最终达到固体的基态。态。 退火过程中系统的退火过程中系统的熵值熵值不断减小，系统能量不断减小，系统能量也随温度降低趋于最小值。也随温度降低趋于最小值。 （3）淬火效应淬火效应：冷却时，若急剧降低温度，：冷却时，若急剧降低温度，则固体只能冷凝为则固体只能冷凝为非均匀的亚稳态非均匀的亚稳态，系统能量也，系统能量也不会达到最小值。不会达到最小值。2 2、自由能减少定律、自由能减少定律 退火过程中系统在每一温度下达到平衡态的退火过程中系统在每一温度下达到平衡态的过程，可以用封闭系统的等温过程来描述。过程，可以用封闭系
9、统的等温过程来描述。（1）自由能减少定律）自由能减少定律 根据根据Boltzmann有序性原理有序性原理，退火过程遵循应，退火过程遵循应用于热平衡封闭系统的热力学定律用于热平衡封闭系统的热力学定律自由能减自由能减少定律少定律。 自由能减少定律自由能减少定律：对于与周围环境交换热量：对于与周围环境交换热量而温度保持不变的封闭系统，系统状态的自发变而温度保持不变的封闭系统，系统状态的自发变化总是朝着自由能减少的方向进行，当自由能达化总是朝着自由能减少的方向进行，当自由能达到最小值时，系统达到平衡态。到最小值时，系统达到平衡态。（2）自由能的计算公式）自由能的计算公式 自由能的计算公式如下：自由能的
10、计算公式如下：F = E TS其中，其中，F为为自由能自由能，E是系统的是系统的内能内能，T是系统是系统温温度度，S是系统的是系统的熵熵。 设设i和和j是恒温系统的两个状态，即是恒温系统的两个状态，即Fi = Ei TSi 和和 Fj = Ej TSj有有()()jijijiFFFEET SSE TS 关于自由能计算公式的说明：关于自由能计算公式的说明： 若系统状态由若系统状态由i自发变化到自发变化到j，则应有则应有 F0。显然，显然，能量减少能量减少（ E0）有有利于自发变化。因此，任一恒定温度下，系统状利于自发变化。因此，任一恒定温度下，系统状态从非平衡态自发变化到平衡态，都是能量和熵态从
11、非平衡态自发变化到平衡态，都是能量和熵竞争的结果，竞争的结果，温度温度决定着这两个因素的相对权重。决定着这两个因素的相对权重。 在高温下，熵占统治地位，有利于变化的方在高温下，熵占统治地位，有利于变化的方向就是熵增加的方向，因而显出粒子的无序状态。向就是熵增加的方向，因而显出粒子的无序状态。而低温对应于低熵，低温下能量占优势，能量减而低温对应于低熵，低温下能量占优势，能量减少的方向有利于自发变化，因而得到有序（低熵）少的方向有利于自发变化，因而得到有序（低熵）和低能的晶体结构。和低能的晶体结构。13.1.2 Metropolis算法算法1 1、Metropolis准则准则 1953年，年，Me
12、tropolis等人利用等人利用Monte Carlo技技术来模拟固体在恒定温度下达到热平衡的过程的术来模拟固体在恒定温度下达到热平衡的过程的方法。称为方法。称为Metropolis算法算法或或Metropolis准则准则。 重要性采样法重要性采样法：Metropolis算法倾向于能量较算法倾向于能量较低的状态，而热运动又妨碍它准确落入最低态的低的状态，而热运动又妨碍它准确落入最低态的物理形态，所以物理形态，所以在采样时着重取那些有关键作用在采样时着重取那些有关键作用的状态的状态，这样就可以较快地得到较好的结果。，这样就可以较快地得到较好的结果。 若初始状态为若初始状态为i，其能量为其能量为E
13、i，然后用摄动装，然后用摄动装置使随机选取的某个粒子的位移随机地产生一微置使随机选取的某个粒子的位移随机地产生一微小变化，得到一个新状态小变化，得到一个新状态j，新状态的能量是新状态的能量是Ej。（1） 若若Ej Ei，则考虑到热运动的影响，该新状，则考虑到热运动的影响，该新状态态j是否为是否为“重要重要”状态，要依据固体处于该状态状态，要依据固体处于该状态的概率来判断的概率来判断。 在大量迁移（即固体状态的变换）后，系统在大量迁移（即固体状态的变换）后，系统趋于能量较低的平衡态，固体状态的概率分布趋趋于能量较低的平衡态，固体状态的概率分布趋于于Gibbs正则分布正则分布，即，即exp()ij
14、EErkT其中，其中，k为为Boltzmann常数，在常数，在SA算法中，算法中，k=1。r是一个小于是一个小于1的数。用随机数发生器产生一个的数。用随机数发生器产生一个0, 1区间的随机数区间的随机数 ，若若r ，则新状态，则新状态j作为作为“重要重要”状态，否则舍去状态，否则舍去。 若新状态若新状态j是重要状态，就以是重要状态，就以j取代取代i成为当前成为当前状态，否则仍以状态，否则仍以i为当前状态，再重复以上新状态为当前状态，再重复以上新状态的产生过程。的产生过程。 由上述由上述Gibbs正则分布公式可知，正则分布公式可知，高温高温下可接下可接受与当前状态受与当前状态能差较大能差较大的新
15、状态为重要状态，而的新状态为重要状态，而在在低温低温下只能接受与当前状态下只能接受与当前状态能差较小能差较小的新状态的新状态为重要状态。这与不同温度下热运动的影响完全为重要状态。这与不同温度下热运动的影响完全一致，在温度趋于一致，在温度趋于0时，就不能接受任一时，就不能接受任一Ej Ei的的新状态新状态j了。了。 上述接受新状态的准则就称为上述接受新状态的准则就称为Metropolis准则准则，相应的算法被称为相应的算法被称为Metropolis算法算法。13.1.3 模拟退火算法模拟退火算法1 1、基本思想基本思想 1982年，年，Kirkpatrick等人意识到等人意识到固体退火过固体退火
16、过程程与与组合优化问题组合优化问题之间存在之间存在类似性类似性，并设计了一，并设计了一种对种对Metropolis准则进行迭代的组合优化算法。故准则进行迭代的组合优化算法。故称之为称之为模拟退火（模拟退火（SA）算法算法。 模拟退火算法从某个初始解出发，持续进行模拟退火算法从某个初始解出发，持续进行“产生新解产生新解判断判断接受接受/舍弃舍弃”的迭代过程，以的迭代过程，以求得给定控制参数值时组合优化问题的相对最优求得给定控制参数值时组合优化问题的相对最优解解。然后减小控制参数然后减小控制参数t的值，重复执行的值，重复执行Metropolis算法，就可在控制参数算法，就可在控制参数t趋于趋于0时
17、，最终时，最终求得组合优化问题的求得组合优化问题的整体最优解整体最优解。固体退火固体退火模拟退火模拟退火微观状态微观状态i优化问题的一个解优化问题的一个解i微观状态微观状态i的能量的能量Ei目标函数目标函数f(i)温度温度t控制参数控制参数t固体退火与模拟退火中的参数对照：固体退火与模拟退火中的参数对照： 模拟退火算法用模拟退火算法用Metropolis准则产生组合优化准则产生组合优化问题解的序列，并由如下转移概率问题解的序列，并由如下转移概率P：1, ( )( )(), ( )( )( )( )exp()if jf iP ijf jf if if jt确定是否接受从当前解确定是否接受从当前解
18、i到新解到新解j的转移。的转移。1 1、SA算法的操作步骤算法的操作步骤 设存在设存在邻域结构邻域结构和和产生器产生器，再设，再设Lk表示表示Metropolis算法第算法第k次迭代时产生的次迭代时产生的变换个数变换个数（也（也称称Markov链长链长），），tk表示表示Metropolis算法第算法第k次迭次迭代时控制参数代时控制参数t的值（的值（ tk= T(tk-1)），），T(t)表示控制表示控制参数更新函数，参数更新函数，tf表示终止温度。以表示终止温度。以最小化目标函最小化目标函数数为例，为例，SA算法的算法的具体操作步骤具体操作步骤为：为： 步步1：随机产生一个初始解，作为当前最
19、优点，：随机产生一个初始解，作为当前最优点，并计算目标函数值；并计算目标函数值； 步步2：设置初始温度：设置初始温度t0、终止温度终止温度tf及控制参及控制参数更新函数数更新函数T(t)； 步步3： tk= T(tk-1)。设置设置Lk，令循环计数器初，令循环计数器初值值k = 1； 步步4：对当前最优点作一随机变动，产生一新：对当前最优点作一随机变动，产生一新解，计算新解的目标函数值，并计算目标函数值解，计算新解的目标函数值，并计算目标函数值的增量的增量 ； 步步5：若：若 = 0，则以概率，则以概率(p = exp( /t)接受该新解为当接受该新解为当前最优点；前最优点； 步步6： 若若k
20、 = tf，则转则转“步步3”；若；若t tf，则输则输出当前最优点，算法结束。出当前最优点，算法结束。【说明】：【说明】： 模拟退火算法依据模拟退火算法依据Metropolis准则接受新解，准则接受新解，因此除接受因此除接受优化解优化解外，还在一个限定范围内接受外，还在一个限定范围内接受“恶化解恶化解”，这正是模拟退火算法与其它局部搜，这正是模拟退火算法与其它局部搜索算法的索算法的本质区别本质区别所在。所在。 （1）开始时）开始时t值大，可能接受较差的恶化解；值大，可能接受较差的恶化解； （2）随着）随着t值的减小，只能接受较好的恶化解；值的减小，只能接受较好的恶化解； （3）最后在）最后在
21、t值趋于值趋于0时，就不再接受任何恶化解。时，就不再接受任何恶化解。 这就使得模拟退火算法既可以从局部最优的这就使得模拟退火算法既可以从局部最优的“陷阱陷阱”中跳出，更有可能求得组合优化的中跳出，更有可能求得组合优化的整体整体最优解最优解，又不失，又不失简单性简单性和和通用性通用性。13.2 模拟退火算法的收敛性分析模拟退火算法的收敛性分析 Markov链链是描述和分析模拟退火算法的重要是描述和分析模拟退火算法的重要数学工具。数学工具。13.2.1 模拟退火算法的模拟退火算法的Markov链描述链描述 请参见张颖等软计算方法请参见张颖等软计算方法pp113-115。13.2.2 模拟退火算法的
22、收敛性模拟退火算法的收敛性 理论证明，理论证明，SA算法实现算法实现全局收敛的时间性能全局收敛的时间性能很差很差。但是，鉴于许多大规模工程问题的复杂性。但是，鉴于许多大规模工程问题的复杂性以及工程中要求以及工程中要求满意解满意解即可的前提，具有通用特即可的前提，具有通用特性的性的SA算法仍是一种算法仍是一种有效而实用的优化算法有效而实用的优化算法。详。详细分析请参见张颖等软计算方法细分析请参见张颖等软计算方法pp115-121。13.3 模拟退火算法的关键参数控制模拟退火算法的关键参数控制 关键参数关键参数包括：包括： （1）初始温度：）初始温度：t0; （2）温度更新函数：温度更新函数：T(
23、t); （3）Markov链长（内循环终止准则）：链长（内循环终止准则）：Lk； （4）终止温度（外循环终止准则）终止温度（外循环终止准则） ：tf。 上述参数也称为：上述参数也称为：退火程序退火程序或或冷却进度表冷却进度表。 退火程序是影响退火程序是影响SA算法实验性能的重要因素，算法实验性能的重要因素，其合理选取是算法应用的关键。通常只能其合理选取是算法应用的关键。通常只能依据一依据一定的启发式规则或大量的试验加以选取定的启发式规则或大量的试验加以选取。【注】：详见张颖等软计算方法【注】：详见张颖等软计算方法pp121-126。13.4 模拟退火算法的应用模拟退火算法的应用13.4.1 模
24、拟退火算法的一般要求模拟退火算法的一般要求 SA算法应用的算法应用的一般形式一般形式是：从选定的初始解是：从选定的初始解开始，再借助于控制参数，递减时产生一系列开始，再借助于控制参数，递减时产生一系列Markov链中，利用一个新解产生装置和接受规则，链中，利用一个新解产生装置和接受规则，重复进行重复进行“产生新解产生新解计算目标函数差计算目标函数差判断是判断是否接受新解否接受新解接受（或舍弃）新解接受（或舍弃）新解”这四个任务这四个任务的试验，不断对当前解迭代，从而达到使的试验，不断对当前解迭代，从而达到使目标函目标函数最优数最优（最大或最小）的执行过程。（最大或最小）的执行过程。 SA算法有
25、算法有3个要求：个要求： （1）目标函数）目标函数：包括解空间、目标函数、初：包括解空间、目标函数、初始解三部分。始解三部分。 （2）新解的产生和接受机制）新解的产生和接受机制。又分为四步：。又分为四步： 步步1：产生新解；：产生新解； 步步2：计算目标函数差；：计算目标函数差； 步步3：判断新解是否被接受；：判断新解是否被接受； 步步4：当新解被接受时，用新解代替当前解。：当新解被接受时，用新解代替当前解。 （3）合理选取冷却进度表中的相关参数值）合理选取冷却进度表中的相关参数值。 详见张颖等软计算方法详见张颖等软计算方法pp126-128。13.4.2 面向典型组合优化问题的面向典型组合优
26、化问题的SA算法算法 （1）旅行商（）旅行商（TSP）问题问题 （2）最大截（）最大截（Max Cut Problem, MCP）问题问题 （3）01背包背包(Zero-one Knapsack Problem, ZKP)问题问题 （4）调度（）调度（Scheduling problem, SCP）问题问题 此外，还有此外，还有机械零件装配问题机械零件装配问题等。等。【注】：详见张颖等软计算方法【注】：详见张颖等软计算方法pp128-133。 【总结】【总结】： SA算法具有广泛的应用性，可用于求解很多算法具有广泛的应用性，可用于求解很多组合优化问题。组合优化问题。SA算法是一种随机性的近似算
27、法，算法是一种随机性的近似算法，其效率和所得解的质量依赖于退火程序，还受到其效率和所得解的质量依赖于退火程序，还受到所用的随机序列及表达问题数据结构的影响。所用的随机序列及表达问题数据结构的影响。 在实际应用时，应根据问题的具体情况适当在实际应用时，应根据问题的具体情况适当选择，以尽量提高算法的效率和解的质量。对某选择，以尽量提高算法的效率和解的质量。对某些具体问题或实例而言，些具体问题或实例而言，SA算法的性能不一定优算法的性能不一定优于目前已有的启发性算法，但由于该算法特有的于目前已有的启发性算法，但由于该算法特有的灵活性和鲁棒性，其优越性仍是很明显的。灵活性和鲁棒性，其优越性仍是很明显的。Thanks！
