模拟退火

发现以前没写过模拟退火相关的东西，就在这里提一下吧

Brief Introduction

模拟退火和爬山类似，都是一个不断逼近最优解的随机算法

爬山是每次都贪心地往更优方向走；而退火则是以一定概率接受一个更劣的解

具体流程如下：

• 设定一个温度值$T$，随机求一个初始解$x_0$

• 不断随机对当前解$x$进行变动，求出一个新解$x' = x + \Delta x$（一般而言变动的$\Delta x$应与当前温度成正比）

  • 若新解比当前解更优，则接受该解

  • 否则，以$e^{\frac{\Delta f}{T}}$的概率接受这个劣解

    其中，$\Delta f$为新解的函数值与当前解的函数值的差

    注：这里无论哪个函数值更大，都需要保证$\Delta f < 0$，只有保证$\Delta f < 0$才有退火的一些理论依据，具体我也不太懂

• 使温度不断下降，即$T = T \times \Delta T$。一般$\Delta T$取$0.95-0.99$的数，模拟降温过程

• 如此反复，直到$T < eps$，其中$eps$为一个趋近于$0$的数

Adjustment

模拟退火的调参就是根据具体的问题，对其中的几个参数$T, \Delta T, eps$，以及退火的次数进行调整，从而使得退火出来的解更优的过程

一般$eps$比较好确定，而$T$和$\Delta T$就要通过不断测试，手动二分等方法来具体确定

19.5.20 UPD 关于退火的一些技巧

记得要多退几次火，不要一次退到底，多退几次会更优

记得while (1)循环。。。

一开始可以多随几个局面（或者随多少秒的局面），从比较优秀的局面开始退火