模拟退火算法

前言

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

所以主要讲解思路把。

引入

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

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

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

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

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

模拟退火的概念

比如说这样一个图:

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}$的)