文档介绍：~oosOz)总第979觏伍薜技术协作信息模拟退火算法和应用●潘蔚论文递营摘要:,其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法在某一初温下,伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解,即在局部优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法。关键词:模拟退火算法;,以它作为当前最优点,并计算目标函数模拟退火算法最早是针对组合优化提出的,其目的在于:(1)为具有NP值。复杂性的问题提供有效的近似求解算法;(2)克服优化过程陷人局部极小;(3):0—1、0。克服初值依赖性。模拟退火算法的基本思想出于物理退火过程。:t—l。简单而言,物理退火过程由以下三部分组成:,产生一新的最优点,。其目的是增强粒子的热运动,使其偏离平衡位置。值,并计算目标函数值的增量△。。物理学的知识告诉我们,△<0,则接受该新产生的最优点为当前最优点;的封闭系统,系统状态的自发变化总是朝自由能减少的方向进行,当自由能如果△I>0,则以概率P=exp(一A/0)接受该新产生的最优点为当前达到最小时,系统达到平衡态。最优点。。其目的是使粒子的热运动减弱并渐趋有序,<终止步数,则:￡+1+1,转向第④步。下降,从而得到低能的晶体结构。,则:0一T(1),转向第③步;模拟退火算法的构成要素如下:如果已达到冷却状态,则:输出当前最优点,计算结束。(1)搜索空间n。在模拟退火算法中,降温的方式对算法有很大影响。如果温度下降过快,搜索空间也称状态空间,它由可行解的集合所组成,其中一个状态X就可能会丢失极值点;如果温度下降过慢,算法的收敛速度又大大降低。其中代表一个可行解。具有代表性的有:能量函数也就是需要进行优化计算的目标函数,其最小点为所求的(1)经典退火方式降温公式为:T(1):—;特点是温度下降很缓慢,因鼓优群。tg/t+I)(31状态转移规则P。此,算法的收敛速度也是很慢。状态转移规则是指从一个状态(一个可行解)向另一个状态(另卜4"N(2)快速退火方式降温公式为:T(t):_'!l0__;这种退火方式的特点是在行解)的转移概率,它与当前的温度参数T有关。HOtt(4)冷却进度表T(D。高温区,温度的下降是比较快的,而在低温区,降温的速率较小。式中Ⅱ可冷却进度表是指从某~高温状态TO向低温状态冷却时的降温管理以改善退火曲线的形态。妻这两种方式都能够使得模拟退火算法收敛于全局最小点。假设图1-1所示为某一能量函数的描述图形。如果搜索过程陷入局部最优点A,若要使搜索过程脱离这个局部最优点而达到c点,则必须使系统至少具有B点所对应的能量。亦即,这里必须允许能量函数值可以一时增大。假设在状态时,系统受到某种扰动而可能会使其状态变为。与此相对应,系统的能量也可能会从E(xO变成E(x。系统由状态)(dd变成x一的接受概率可由下面的Metropolis规则来确定:{exp(一塾怨)<E(XoU;上式的含