模拟退火算法的教程讲解教学课件

模拟退火算法SimulatedAnnealingalgorithm信息与计算科学卿铭模拟退火算法的思想模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却;加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到某种稳定状态,基态,内能减为最小模拟退火算法的思想物理退火过程加温过程增强粒子的热运动,消除系统原先可能存在的非均匀态;等温过程对于与环境换热而温度不变的封闭系统,系统状态的自发变化总是朝自由能减少的方向进行,当自由能达到最小时,系统达到平衡态冷却过程使粒子热运动减弱并渐趋有序,系统能量逐渐下降,从而得到低能的晶体结构。1模拟退火算法的思想缓慢降温(退火,annealing)时,可达到最低能量状态,较为柔韧;但如果快速降温(淬火quenching),会导致不是最低能态的非晶形,较硬易断令大自然知道慢工出细活:缓缓降温,使得物体分子在每一温度时,能够有足够时间找到安顿位置,则逐渐地,到最后可得到最低能态,系统最稳定。模拟退火算法(SimulatedAnnealing,SA)最早的思想是由N.Metropolis等人于1953年提出。1983年,S.Kirkpatrick等成功地将退火思想引入到组合优化领域。它是基于Monte〔arlo迭代求解策略的一种随机寻优算法,其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发,伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解,即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性,从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。◆模拟退火算法是一种通用的优化算法,理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用。组合优化与物理退火的相似性比较组合优化问题金属物体解粒子状态最优解能量最低的状态设定初温熔解过程Metropolis抽样过程等温过程控制参数的下降冷却目标函数能量从某一初始温度开始,伴随温度的不断下降,结合概率突跳特性在解空间中随机寻找全局最优解2模拟退火算法的原理令根据Metropolis准在温度T时趋于平衡的概率为eXp(△E/(kT),其中E为温度T时的内能,△E为其改变量,k为Boltzmann常数。用固体退火模拟组合优化问题,将内能E模拟为且标函数值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退火由初始解i和控制参数初值t开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t值,算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程令退火过程由冷却进度表(oolingschedule控制,包括控制参数的初值t及其衰减因子△t、每个t值时的迭代次数L和停止条件S。2物理退火过程的数学表示在温度T,分子停留在状态r满足Boltzmann概率分布P{E=E(r)}=E(r)expZ(T)kBTE表示分子能量的一个随变量,E(r)表示状态的能量k>0为Boltzmann常数。Z(T)为概率分布的标准化因子z()=>cp-E62物理退火过程的数学表示在同一个温度T,选定两个能量E1<E2,有(PE=E}-PE=E)z()二k7ErExplkTE2-E1可知0(1)在同一个温度,分子停留在能量小状态的概率大于停留在能量大状态的概率(2)温度越高,不同能量状态对应的概率相差越小温度足够高时,各状态对应概率基本相同(3)随着温度的下降,能量最低状态对应概率越来越大;温度趋于0时,其状态趋于1模拟退火算法基本思想:在一定温度下,搜索从一个状态随机地变化到另一个状态;随着温度的不断下降直到最低温度,搜索过程以概率1停留在最优解2物理退火过程的数学表示能量最低状态非能量最低状态若D为状态空间D状态的个数,D是具有最低能量的状态集合