模拟退火算法
前言
首先模拟退火算法很简单,代码也很短。
所以主要讲解思路把。
引入
原子运动是无规则的,温度越高运动地越剧烈。
如果从高温度瞬间降到低温度,那么原子从剧烈运动瞬间几乎达到静止。
那么原子会散乱地分布在空间中,无法形成宏观上的晶体。
如果想要形成晶体,就得回到高温度,再徐徐降火,回到低温度,达到最低能态,这个过程被称之为“退火”。
以上过程被称之为“退火”的概念,从剧烈走向稳定。
模拟退火的概念
比如说这样一个图:
这个函数存在许多局部极值点,如果设计了一个函数找到了目前最深的点,就跳不出去了,这明显不是我们想要的全局最优解。
但如果设计一个有概率能跳出目前最深点(局部最优解)的函数呢?
为了解决局部最优解问题,$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就会衰减一点。。
算法流程
- 随机一个新点$x_{n+1}$
- 计算出$\Delta E$,按上述准则进行
- 对T进行衰变,即$T=T*d$,$d$是一个$(0,1)$数,越接近$1$衰变的越慢。
- 反复直到$T\rightarrow 0$
对于随机,需要很好的心态。
一些优化
根据题目的意思,
- 适当调整随机的范围
- 改变$kT$,$k$的大小。
- 多进行几次,可以尝试榨干时间
- 采用较为随机的随机数。
适用范围
- 坐标系内:随机生成一个点,或者生成一个向量。
- 序列问题: $random\_shuffle$或者随机交换两个数。
- 网格问题:可以看做二维序列,每次交换两个格子即可。
(这一小段是来自$\text{M_sea}$的)
最后一次更新于2020-05-21
0 条评论