1.概念
介绍模拟退火前,请先了解爬山算法。
因为模拟退火算法是爬山算法的改进版,
它在爬山算法的基础上引入了随机化。
爬山算法是完完全全的贪心法,
有可能只能搜索到局部的最优值。
模拟退火其实也是一种贪心算法,
但是它的搜索过程引入了随机因素。
模拟退火算法以一定的概率来接受一个比当前解要差的解,
因此有可能会跳出这个局部的最优解,达到全局的最优解。
2.主要思想
模拟退火算法来源于固体退火原理,
将固体加温至充分高,再让其徐徐冷却,
加温时,固体内部粒子随温升变为无序状,内能增大,
而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,
最后在常温时达到基态,内能减为最小。
从描述上看退火能够使固体获得内能的最小值,
这里用模拟退火算法来解决问题时,
该算法通过模拟固体的退火过程,
目的是期望获得问题的最小值作为最优解,
如果期望获得是最大值,
等价为将目标函数乘以-1后再求解最小值,
得到的最小值乘以-1即为所求最大值。
所以模拟退火算法和爬山算法一样都可以获得问题的最优解,
而且求解问题的最大值或者最小值其实是等价的。
3.算法步骤
- 随机选择一个退火的状态作为起点S;
- 每次拿相邻点N与当前点S进行比对;
- 如果N<S,则取N作为退火的当前状态;
- 如果N>S,则以一定的概率P(dE)接受该状态;
- 重复第2、3步或者第2、4步,直至概率P(dE)随着时间推移逐渐降低,最后变为0;
- 重复第2、3步(由于P(dE)=0不可能进入第4步),直至该点的邻近点中不再有比其小的点;
- 选择该点作为退火的最终状态,认为其内能最小,作为该算法获得的最优解。
概率P(dE)就是模拟退火算法的核心,
其物理原理如下:
根据热力学的原理,在温度为T时,
出现能量差为dE的降温的概率为P(dE),表示为:
P(dE) = exp( dE/(kT) )
其中k是一个常数,exp表示自然指数,且dE<0。
公式解读:
温度越高,出现一次能量差为dE的降温的概率就越大;
温度越低,则出现降温的概率就越小。
又由于dE总是小于0(退火过程能量下降),
因此dE/kT < 0 ,所以P(dE)的函数取值范围是(0,1) 。
总之随着温度T的降低,P(dE)会逐渐降低。
4.特点
模拟退火算法具有跳出局部最优陷阱的能力,
很好的解决了爬山算法的局限性。
大量的模拟实验表明,在有限的时间和处理性能内,
模拟退火算法在求解这些问题时能产生令人满意的近似最优解。