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