模拟退火算法.ppt

文档介绍：(d*=)(1953)提出,1983年Kirkpatrick等将其应用于组合优化。算法的目的解决NP复杂性问题;克服优化过程陷入局部极小;克服初值依赖性。:退火是指将固体加热到足够高的温度,使分子呈随机排列状态,然后逐步降温使之冷却,最后分子以低能状态排列,固体达到某种稳定状态。——增强粒子的热运动,消除系统原先可能存在的非均匀态;等温过程——对于与环境换热而温度不变的封闭系统,系统状态的自发变化总是朝自由能减少的方向进行,当自由能达到最小时,系统达到平衡态;冷却过程——使粒子热运动减弱并渐趋有序,系统能量逐渐下降,从而得到低能的晶体结构。,,选定两个能量E1<E2,有在同一个温度,分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。<1>|D|为状态空间D中状态的个数,D0是具有最低能量的状态集合:当温度很高时,每个状态概率基本相同,接***均值1/|D|;状态空间存在超过两个不同能量时,具有最低能量状态的概率超出平均值1/|D|;当温度趋于0时,分子停留在最低能量状态的概率趋于1。(1953)——以概率接受新状态固体在恒定温度下达到热平衡的过程可以用MonteCarlo方法(计算机随机模拟方法)加以模拟,虽然该方法简单,但必须大量采样才能得到比较精确的结果,计算量很大。