文档介绍：模拟退火算法
Simulated Annealing Algorithm
信息与计算科学
卿铭
模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却;加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到某种稳定状态,基态,内能减为最小。
1 模拟退火算法的思想
物理退火过程
加温过程——增强粒子的热运动,消除系统原先可能存在的非均匀态;
等温过程——对于与环境换热而温度不变的封闭系统,系统状态的自发变化总是朝自由能减少的方向进行,当自由能达到最小时,系统达到平衡态;
冷却过程——使粒子热运动减弱并渐趋有序,系统能量逐渐下降,从而得到低能的晶体结构。
1 模拟退火算法的思想
缓慢降温(退火,annealing)时,可达到最低能量状态,较为柔韧;但如果快速降温(淬火,quenching),会导致不是最低能态的非晶形,较硬易断。
大自然知道慢工出细活:
缓缓降温,使得物体分子在每一温度时,能够有足够时间找到安顿位置,则逐渐地,到最后可得到最低能态,系统最稳定。
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物理退火过程的数学表示
若|D|为状态空间D中状态的个数,D0是具有最低能量的状态集合:
当温度很高时,每个状态概率基本相同,接***均值1/|D|;
状态空间存在超过两个不同能量时,具有最低能量状态的概率超出平均值1/|D| ;
当温度趋于0时,分子停留在最低能量状态的概率趋于1。
能量最低状态非能量最低状态
2物理退火过程的数学表示