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

搜索算法

启发式搜索

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

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

模拟退火算法

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

来源

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

根据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}$

终止条件

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

改进策略

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