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