模拟退火算法

前言

首先模拟退火算法很简单,代码也很短。

所以主要讲解思路把。

引入

原子运动是无规则的,温度越高运动地越剧烈。

如果从高温度瞬间降到低温度,那么原子从剧烈运动瞬间几乎达到静止。

那么原子会散乱地分布在空间中,无法形成宏观上的晶体。

如果想要形成晶体,就得回到高温度,再徐徐降火,回到低温度,达到最低能态,这个过程被称之为“退火”。

以上过程被称之为“退火”的概念,从剧烈走向稳定。

模拟退火的概念

比如说这样一个图:

2.PNG

这个函数存在许多局部极值点,如果设计了一个函数找到了目前最深的点,就跳不出去了,这明显不是我们想要的全局最优解。

但如果设计一个有概率能跳出目前最深点(局部最优解)的函数呢?

为了解决局部最优解问题,$1983$年,Kirkpatrick等提出了模拟退火算法(SA)能有效的解决局部最优解问题。

通过模拟“退火”的过程来求解。

首先我们得了解一个很自然的东西,

Metropolis(蒙特卡洛)准则

根据热力学公式,当温度为T时,出现能量差为$\Delta E$的降温的概率为$P_T(\Delta E)$,

$P_T(\Delta E)=exp(\frac{\Delta E}{kT})$,

$k$是一个常数,有兴趣的同学可以深入了解(之后顺带告诉我T^T

类似地,根据这个公式,

提出了一个准则,由$x(n)$到$x(n+1)$的过程,$\Delta E=E(n+1)-E(n)$,其进入$x(n+1)$的概率为

$P=\begin{cases}1~~~~~~~~~~~~~~~~&\Delta E<0\\exp(-\frac{\Delta E}{kT})&\Delta E\ge 0\end{cases}$

每进行一次,T就会衰减一点。。


算法流程

  1. 随机一个新点$x_{n+1}$
  2. 计算出$\Delta E$,按上述准则进行
  3. 对T进行衰变,即$T=T*d$,$d$是一个$(0,1)$数,越接近$1$衰变的越慢。
  4. 反复直到$T\rightarrow 0$

对于随机,需要很好的心态。

模板

一些优化

根据题目的意思,

  1. 适当调整随机的范围
  2. 改变$kT$,$k$的大小。
  3. 多进行几次,可以尝试榨干时间
  4. 采用较为随机的随机数。

适用范围

  • 坐标系内:随机生成一个点,或者生成一个向量。
  • 序列问题: $random\_shuffle$或者随机交换两个数。
  • 网格问题:可以看做二维序列,每次交换两个格子即可。

(这一小段是来自$\text{M_sea}$的)