模拟退火算法

模拟退火算法的原理及实现。

搜索算法

启发式搜索

按照预定的控制策略实行搜索,在搜索过程中获取的中间信息补用来改进控制策略,称为盲目搜索,反之,称为启发式搜索

常见的深度优先广度优先搜索算法都属于盲目搜索,而爬山法模拟退火算法遗传算法蚁群算法等都属于启发式搜索

模拟退火算法

模拟退火算法属于启发式算法。

来源

模拟退火算法是来源于固体退火原理,将固体加温至充分高,再让其嘘嘘冷却,加温时,固体内部粒子随温度升高变为无序状,内能增大,而徐徐冷却时粒子逐渐有序,每个温度都达到平衡状态,最后在常温时达到基态,内能减为最小。

根据Metropolis准则,固体内部粒子在温度T时趋于平衡的概率为exp(△E/(kT)),其中E为温度T时的内能,△E为其改变量,k为Boltzmann常数。

$$f(n)=\begin{cases}1, \quad if \quad E(x_{new}) < E(x_{old})\\
exp(-\frac{E(x_{new})-E(x_{old})}{T}), \quad if \quad E(x_{new}) > E(x_{old}) \end{cases}$$

主要思想

用固体退火模拟组合优化问题,可以将内能E模拟为目标函数值f,温度T演化成控制参数。

算法流程

  • 随机产生一个初始解$ x_0 $, 令$ x_{best} = x_0 $, 并计算目标函数值$E(x_0)$
  • 设置初始温度$ T_0 $,迭代次数为N,i=0记录迭代次数
  • 当i < N, 并且不满足终止条件,
    • 对当前最优解$ x_{best} $按照某一邻域函数产生一个新的解$ x_{new} $。计算新的目标函数值$ E(x_{new}) $,从而得到目标函数值的增量$△E = E(x_{new}) - E(x_{best})$
    • 应用Metropolis准则,当△E < 0时,总是接受移动$x_{best}=x_{new}$,否则以一定概率接受移动$p=exp(-△E/T(i))$
    • i += 1
  • 输出当前最优解,计算结束

伪代码

来自wikipedia

1
2
3
4
5
6
7
8
9
s := 0; e := E(s)
k := 0 ## //k为评估次数
while k < kmax and e > emax //kmax最大评估次数,emax可接受的最大结果
sn := neighbour(s) //随机选取一个邻居状态
en := E(sn) //能量结果
if random() < P(e, en, temp(k/kmax)) then
s := sn; e := en //如果满足metropolis准则,则移动到该邻居节点
k += 1 //评估完成,次数+1
return s

冷却进度

这面两种方法都能够让模拟退火算法收敛于局部最小。

经典模拟退火算法的降温方式,从下面的公式中可以得出,该算法是一种指数的变化趋势

$T(t)=\frac {T_0} {lg(1+t)}$

快速模拟退火算法的降温方式,稳定变化

$T(t)=\frac {T_0} {1 + t}$

终止条件

  • 设置终止的目标值
  • 迭代次数限制
  • 连续若干步保持不变
  • 系统熵是否稳定

改进策略

  • 增加升温或重升温策略,调整搜索进程中的状态,避免陷入局部最优
  • 增加移动的记忆功能,避免遗失当前遇到过的最优解
  • 结合其他搜索方法