模拟退火算法 第一节模拟退火算法.ppt

《模拟退火算法 第一节模拟退火算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、模拟退火(simulatedannealing)算法是局部搜索算法的扩展．它源于对固体退火过程的模拟;采用Metropolis接受准则；并用一组称为冷却进度表的参数控制算法进程，使算法在多项式时间里给出一个近似最优解．模拟退火算法最早的思想由Metropolis在1953年提出，Kirkpatrick在1983年成功地应用在组合最优化问题中．第2章　模拟退火算法一　固体退火过程退火是一种物理过程，固体退火是先将固体加热至熔化，再徐徐冷却使之凝固成规整晶体的热力学过程．退火过程中，系统在每一温度下达到平衡态，系

2、统状态的分布满足一定的概率分布，即在温度T，系统达到平衡态后，分子停留在状态r满足波兹曼(Boltzmann)概率分布2.1模拟退火算法及模型其中，E(r)为状态r的能量，kB0为波兹曼常数，为分子能量的一个随机变量，称为波兹曼因子．Z(T)为概率分布的标准化因子，先研究由(2.1)确定的函数随T变化的趋势．选定两个能量E1

3、，接近平均值1D，D为状态空间D中状态的个数．此时，具有最低能量状态的波兹曼概率接近并超出平均值1D．当rmin是D中具有最低能量的状态时，得由所以，关于温度T是单调下降的．又有其中，D0是具有最低能量的状态集合，因此得到，当T趋向于0时，当温度趋向于0时，(2.1)决定的概率渐近由此可以得到，在温度趋向于0时，分子停留在最低能量状态的概率趋向1．综合上面的讨论，分子在最低能量状态的概率变化趋势由图(a)表示．对于非能量最小的状态，由(2.2)和分子在能量最小状态的概率是单调减小的事实，在温度

4、较高时，分子在这些状态的概率在附近，依赖于状态的不同，使(2.1)决定的概率在(0,t)是单调升的；再由(2.4)可知，当温度趋于0时，(2.1)定义的概率趋于0．概率变化曲线见图(b)．可能超过由(2.3)和(2.4)可知存在一个温度t，从上面的讨论得到，在温度很低时，能量越低的状态的概率值越高，在极限状况，只有能量最低的点概率不为０．即有1.系统在T平衡时，系统状态的概率分布趋于(2.1)式，0.0020.0160.1170.865t=0.50.1810.2210.2690.325t=50.2320.24

5、30.2560.269t=20例2.1简化概率分布(2.1)为其中q(t)为标准化因子．设共有四个能量点x=1,2,3,4,在此观察t=20,5,0.5,三个温度点概率分布变化．二．Metropolis准则固体在恒定温度下达到热平衡的过程可以进行模拟．1953年，Metropolis等提出重要性采样法．他们用下述方法产生固体的状态序列：先给定以粒子相对位置表征的初始状态i，作为固体的当前状态，该状态的能量是Ei．然后用摄动装置使随机选取的某个粒子的位移随机地产生一微小变化，得到一个新状态j，新状态的能量是Ej

6、．如EjEi，则考虑热运动的影响，该新状态是否重要状态，要依据固体处于该状态的几率来判断．由(2.1)知，固体处于i和j的概率的比值等于相应Boltzmann因子的比值，即r是一个小于1的数．用随机数发生器产生一个[0,1)区间的随机数，若r>，则新状态j作为重要状态，否则舍去．若新状态j是重要状态，就以j取代i成为当前状态，否则仍以i为当前状态，再重复以上新状态产生过程．在大量固体状态的变换后，系统趋于能量较低的平衡状态，固体状态的概率分布趋于(2.1)式的Bo

7、ltzmann概率分布．由()式可知，高温下可接受与当前状态能差较大的新状态为重要状态．而在低温下只能接受与当前状态能差较小的新状态为重要状态.这与不同温度下热运动的影响完全一致．在温度趋与零时，就不能接受任一Ej>Ei的新状态j了．上述接受新状态的准则称为Metropolis准则，相应的算法称为Metropolis算法．这种算法的计算量显著减少．三．模拟退火算法对固体退火过程的研究给人们以新的启示．1982年，Kirkpatrick等首先意识到固体退火过程与组合优化问题之间存在的类似性，Metropoli

8、s等对固体在恒定温度下达到热平衡的模拟也给他们以启迪：应该把Metropolis准则引入到过程中来．最终他们得到一种对Metropolis算法进行迭代的组合优化算法，这种算法模拟固体退火过程，称之为模拟退火算法．我们可以将组合优化问题同金属物体退火进行类比：组合优化问题金属物体假设算法用以解决如下组合优化问题：解费用(目标)函数最优解状态能量能量最低的状态模拟退火算法Step1任选一个初始解x0；x