模拟退火算法学习

算法学习

---

前言：听起来挺 $NB$

---

百度百科

    模拟退火算法（Simulate Anneal，SA）是一种通用概率演算法，用来在一个大的搜寻空间内找寻命题的最优解
    模拟退火的出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法是一种通用的优化算法，其物理退火过程由加温过程、等温过程、冷却过程这三部分组成。
    bulabula 一大堆 (唉)

---

由来

    模拟退火是一种非常好用的随机化算法，它是爬山算法的改进版

---

通俗的解释

    仿照物体降温的过程来进行随机，通过随机判断找的局部最优解，或者以一定的概率接受非最优解，通过对其选择找到全局最优解
    知乎上有个非常通俗的解释

---

实现

上述一大堆，并没有什么用

考虑物体退火的过程(温度由高到低)定义变量
$T$ 为当前温度，体现程序的运行程度
$\Delta T$ 表示温度的改变量，就是每次给 $T$ 降温, 一般取 $[0.95,0.99]$ 总之要 $<1$
$f(T)$ 表示 $T$ 温度时的全局最优解
怎么接受非最优解呢？
先来看一个式子

$$rand()<=e^{\frac{f(T)-f(T*\Delta T)}{T}}*Maxrand$$
科学家经分析(还是某daolao吹) 当满足上式时接受非最优解最优

---

算法流程

1.初始化最高温度
2.计算出下一步的随机解 $f(T')$
3.若 $f(T')$ 优于 $f(T)$ 或者满足上式则进行转移
4.降温

---

例题

[Cogs] 线性网络