[数学]模拟退火算法.pdf

智能算法 第五章：模拟退火算法 谷俊峰 工业装备结构分析国家重点实验室 工程力学系 运载工程与力学学部 提纲 5.1 模拟退火算法简介 5.2 模拟退火算法基本原理 5.3 模拟退火算法的改进 5.4 模拟退火算法的应用 5.5 本章小结 5.1 模拟退火算法简介 模拟退火的思想 想象在不平的表面上如何使一个乒乓球掉到最深的裂缝中—如果 只让其在表面滚动，则它只会停留在局部极小点 / 如果晃动平 面，可以使乒乓球弹出局部极小点 / 技巧是晃动足够大使乒乓球 弹出局部极小点，但又不能太大把它从全局极小点中赶出 模拟退火的思路 开始使劲晃动(先高温加热)然后慢慢降低摇晃的强度(逐渐降 温)[退火过程] 算法的目的 解决NP复杂性问题； 克服优化过程陷入局部极小； 克服初值依赖性。 5.1 模拟退火算法简介 模拟退火算法的发展： 1953年N. Metropolis等人在研究二维相变时提出了SA 算法 1983年Kirkparick等用这种方法设计大规模集成电路，SA算 法开始用于组合优化问题的求解中。 1984年S. German和D. German给出了退火率和退火时间的对 数成反比的SA算法。 1985年Cerny V. 运用SA算法求解TSP这一“NP完全问题”获 得成功。 1986年Harold Szu 提出了一种退火率与时间成反比的快速模 拟退火算法(FSA) 。从此，SA算法进入了各个领域的研究。 5.2 模拟退火算法基本原理 5.2.1 物理退火过程 5.2.1 物理退火过程 物理退火过程 什么是退火： 退火是指将固体加热到足够高的温度，使分子呈随机排列状 态，然后逐步降温使之冷却，最后分子以低能状态排列， 固体达到某种稳定状态。 5.2.1 物理退火过程 物理退火过程的发展阶段 1. 加温过程。其目的是增强粒子的热运动，使其偏离平衡位置。当温度足 够高时，固体将溶解为液体，溶解过程与系统的熵增过程联系，系统能 量也随温度的升高而增大，使得每一粒子的状态都具有充分的随机性。 2. 等温过程。物理学的知识告诉我们，对于与周围环境交换热量而温度不 变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当 自由能达到最小时，系统达到平衡态。 3. 冷却过程。目的是使粒子的热运动减弱并渐趋有序，系统能量逐渐下 降，从而得到低能的晶体结构。在常温时达到基态，内能减为最小。 5.2.1 物理退火过程 数学表述: 物体加热至一定温度后，所有分子在状态空间D中自由运动，随着温度的下 降，分子逐渐停留在不同的状态。在温度最低时，分子重新以一定的结构 排列。 在温度T, 分子停留在状态r满足Boltzmann概率分布: 1 ⎛ ( ) ⎞ { ( )} exp⎜E r ⎟ P E E r ⎜− ⎟ ( ) Z T k T ⎝ B ⎠ E 表示分子能量的一个随机变量，E (r )