AI0513 模拟退火算法 人工智能课程 浙江大学研究生.ppt

* * 第十三章 模拟退火算法 徐从富 浙江大学人工智能研究所 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 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] White. 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 general 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等将热力学中的退火思想引入组合优化领域，提出一种解决大规模组合优化问题（特别是NP完全问题）的有效近似算法——模拟退火（Simulated Annealing，简称SA）算法。 SA算法源于对固体退火过程的模拟，采用Metropolis接受准则，并用一组称为冷却进度表的参数控制算法进程，使算法在多项式时间里给出一个近似最优解。 从本质上说，SA算法是进化计算中的一种特殊方法。 （2）退火：冷却时，液体粒子的热运动渐渐减弱，随着温度的徐徐降低，粒子运动渐趋有序。当温度降至结晶温度后，粒子运动变为围绕晶体格点的微小振动，液体凝固成固体的晶态。这个过程称为退火。 退火过程必须 “徐徐”进行的原因：使系统在每一温度下都达到平衡态，最终达到固体的基态。 退火过程中系统的熵值不断减小，系统能量也随温度降低趋于最小值。 （3）淬火效应：冷却时，若急剧降低温度，则固体只能冷凝为非均匀的亚稳态，系统能量也不会达到最小值。 2、自由能减少定律 退火过程中系统在每一温度下达到平衡态的过程，可以用封闭系统的等温过程来描述。 （1）自由能减少定律 根据Boltzmann有序性原理，退火过程遵循应用于热平衡封闭系统的热力学定律——自由能减少定律。 自由能减少定律：对于与周围环境交换热量而温度保持不变的封闭系统，系统状态的自发变化总是朝着自由能减少的方向进行，当自由能达到最小值时，系统达到平衡态。 （2）自由能的计算公式 自由能的计算公式如下： F = E – TS 其中，F为自由能，E是系统的内能，T是系统温度，S是系统的熵。 设i和j是恒温系统的两个状态，即 Fi = Ei – TSi 和 Fj = Ej – TSj 有 关于自由能计算公式的说明：