模拟退火算法(浅谈)
模拟退火启发自统计力学的研究:材料中粒子的不同结构对应于粒子的不同能量水平。高温条件下,粒子能量较高,可以*运动和重新排列。低温条件下, 粒子能量较低,能够形成低能状态的晶体。在我们优化一个目标函数时,事先我们也并不知道最优值为多大,确定一个值的好坏,只能通过和前一个值进行比较,这也是为什么容易陷入局部极小。
模拟退火算法在遇到一个新解的时候,分两种情况来决定是否接受该新解。我们用CUR和PRE分别表示新解和旧解
- 如果新解比旧解好,无条件地接受新解(这一条保证可以往极值方向前进,不管是不是全局最优)
- 如果新解不如旧解,可能会接受新解(在算法中加上一些随机性,这一条让算法具备了跳出局部最小的能力)
模拟退火算法的Algorithm如下
我们用C来表示一个解。算法初始时,我们随机赋予一个可行解。温度T从开始下降到
。在for循环体内,首先我们计算当前解C的能量(能量越大,则表示解越好。对应到旅行商问题,能量就是经过所有城市的总路程),然后使用next()方法得到一个新的解N(产生的新解和温度T是无关的,比如对于旅行商问题来说,新解可以通过替换两个随机选择的城市的位置来产生)。接下来,我们就比较这两个解的能量差异,满足条件的话,就将新解更新。需要注意的是,温度并不用于产生新解,只是用于决定是否该接受较差的新解。