文档介绍：模拟退火(simulated annealing);采用Metropolis接受准则;并用一组称为冷却进度表的参数控制算法进程,使算法在多项式时间里给出一个近似最优解. 模拟退火算法最早的思想由Metropolis在1953年提出,??)())(exp()(1)(TkrETZrEEPB???一固体退火过程退火是一种物理过程,固体退火是先将固体加热至熔化,再徐徐冷却使之凝固成规整晶体的热力学过程. 退火过程中,系统在每一温度下达到平衡态,系统状态的分布满足一定的概率分布,即在温度T,系统达到平衡态后,分子停留在状态r 满足波兹曼(Boltzmann) 模拟退火算法及模型????DsBTksETZ))(exp()(其中,E(r)为状态r的能量,kB?0为波兹曼常数,))(exp(TkrEB?E为分子能量的一个随机变量,(T)为概率分布的标准化因子, 先研究由()< E2,在同一个温度T,有D为状态空间.)]exp(1)[exp()(1)()(12121TkEETkETZEEPEEPBB????????0,1)exp(12?????TTkEEB因为)()()(21??????TEEPEEP 在同一个温度,(),()的概率分布使得每个状态的概率基本相同,接***均值1??D?,?D?,具有最低能量状态的波兹曼概率接近并超出平均值1??D?.??0)(min????TrEEP??)()()(exp)()()()(exp)(2?????????????????????????????????TZTksEsErETkTZTkrETrEEPDsBBB当rmin是D中具有最低能量的状态时,得由??RDTkrETZrEEPB?????0minmin1))(exp()(1)()(0,0))()(exp()()(:minmin????????TTkrEsERrEsEDsB??)(minrEEP?所以,,D0是具有最低能量的状态集合,??0,1)(0min???TDrEEPPrTOD101D在能量最低状态)(a因此得到,当T 趋向于0 时,01D当温度趋向于0时,()决定的概率渐近由此可以得到,在温度趋向于0时,,分子在最低能量状态的概率变化趋势由图(a))(b对于非能量最小的状态,由()和分子在能量最小状态的概率是单调减小的事实,在温度较高时,分子在D1这些状态的概率在附近,依赖于状态的不同,使()决定的概率在(0 ,t)是单调升的;再由()可知,当温度趋于0时,()(b).;1D可能超过由()和()可知存在一个温度t,??))(exp()(1)(TkrETZrEEPB???从上面的讨论得到,在温度很低时,能量越低的状态的概率值越高,在极限状况,????????????000001)(.2DrDrDrEEPT????0|)(lim1|)(????????DrrEEPDrrEEPTT1. 系统在T 平衡时,系统状态的概率分布趋于()式,===201?x2?x3?x4?x,)exp()(1)(txtqxp?? 简化概率分布()为其中q(t)=1, 2, 3, 4,????41)exp()(xtxtq在此观察t = 20, 5, , 三个温度点概率分布变化.