模拟退火算法 第一节教程教案.ppt

　模拟退火(simulated annealing)算法是局部有哪些信誉好的足球投注网站算法的扩展．它源于对固体退火过程的模拟;采用Metropolis接受准则；并用一组称为冷却进度表的参数控制算法进程，使算法在多项式时间里给出一个近似最优解． 　模拟退火算法最早的思想由Metropolis在1953年提出，Kirkpatrick在1983年成功地应用在组合最优化问题中． 第2章　模拟退火算法 一　固体退火过程 　退火是一种物理过程，固体退火是先将固体加热至熔化，再徐徐冷却使之凝固成规整晶体的热力学过程． 　退火过程中，系统在每一温度下达到平衡态，系统状态的分布满足一定的概率分布，即在温度 T，系统达到平衡态后，分子停留在状态 r 满足波兹曼(Boltzmann)概率分布 2.1　模拟退火算法及模型 其中，E(r)为状态 r 的能量，kB ?0为波兹曼常数， 为分子能量的一个随机变量， 称为波兹曼因子．Z(T)为概率分布的标准化因子， 　先研究由(2.1)确定的函数随 T 变化的趋势．选定两个能量 E1 E2，在同一个温度 T ，有 D 为状态空间． 　在同一个温度，(2.2)表示分子停留在能量小状态的概率比停留在能量大状态的概率要大．当温度相当高时，(2.1)的概率分布使得每个状态的概率基本相同，接近平均值1??D?，?D?为状态空间 D 中状态的个数．此时，具有最低能量状态的波兹曼概率接近并超出平均值1??D?． 当 rmin 是 D中具有最低能量的状态时，得 由 所以， 关于温度 T是单调下降的．又有 其中，D0是具有最低能量的状态集合， 因此得到，当 T 趋向于 0 时， 当温度趋向于 0时，(2.1)决定的概率渐近 由此可以得到，在温度趋向于 0时，分子停留在最低能量状态的概率趋向1．综合上面的讨论，分子在最低能量状态的概率变化趋势由图(a)表示． 对于非能量最小的状态，由(2.2)和分子在能量最小状态的概率是单调减小的事实，在温度较高时，分子在 这些状态的概率在 附近，依赖于状态的不同， 使(2.1)决定的概率在(0 ,t)是单调升的；再由(2.4)可知，当温度趋于 0时，(2.1)定义的概率趋于 0．概率变化曲线见图(b)． 可能超过 由(2.3)和(2.4)可知存在一个温度t， 0.002 0.016 0.117 0.865 t=0.5 0.181 0.221 0.269 0.325 t=5 0.232 0.243 0.256 0.269 t=20 例2.1　简化概率分布(2.1)为 其中q(t)为标准化因子．设共有四个能量点x=1, 2, 3, 4, 在此 观察 t = 20, 5, 0.5, 三个温度点概 率分布变化． 二． Metropolis准则 　固体在恒定温度下达到热平衡的过程可以进行模拟． 　1953年，Metropolis等提出重要性采样法．他们用下述方法产生固体的状态序列： 　先给定以粒子相对位置表征的初始状态 i，作为固体的当前状态，该状态的能量是 Ei ．然后用摄动装置使随机选取的某个粒子的位移随机地产生一微小变化，得到一个新状态 j，新状态的能量是Ej ．如Ej Ei ，则该新状态就作为重要状态．如Ej Ei ，则考虑热运动的影响，该新状态是否重要状态，要依据固体处于该状态的几率来 判断．由(2.1)知，固体处于 i 和 j 的概率的比值等于相应Boltzmann因子的比值，即 r是一个小于1的数．用随机数发生器产生一个[0 ,1)区间的随机数?，若r ?，则新状态 j 作为重要状态，否则舍去．若新状态 j是重要状态，就以 j 取代 i 成为当前状态，否则仍以 i 为当前状态，再重复以上新状态产生过程．在大量固体状态的变换后，系统趋于能量较低的平衡状态，固体状态的概率分布趋于(2.1)式的Boltzmann概率分布． 　由(?)式可知，高温下可接受与当前状态能差较大的新状态为重要状态．而在低温下只能接受与当前状态能差较小的新状态为重要状态.这与不同温度下热运动的影响完全一致．在温度趋与零时，就不能接受任一 Ej Ei 的新状态 j了． 　上述接受新状态的准则称为Metropolis准则，相应的算法称为Metropolis算法．这种算法的计算量显著减少．　 三．模拟退火算法 　对固体退火过程的研究给人们以新的启示．1982年，Kirkpatrick等首先意识到固体退火过程与组合优化问题之间存在的类似性， Metropolis等对固体在恒定温度下达到热平衡的模拟也给他们以启迪：应该把Metropolis准则引入到过程中来．最终他们得到一种对Metropolis算法进行迭代的组合优化算法，这种算法模拟固体退火过程，称之为模拟退火算法． 　我们可以将组合优化问题同金属物体退火进行类比： 组合优化问题　 金