模拟退火算法
本篇为关于模拟退火算法$(Simulated Annealing，SA)$的个人笔记。因为网上的资料不够综合，所以自己写了一份。会根据自己的见解持续更新。
名称来源
退火指物体逐渐降温冷却的物理现象。温度越低，物体的能量越低，在结晶状态时系统的能量状态到达最低。在自然中，缓慢降温（退火）可以导致结晶，而与之相对的快速降温（淬火）会导致不是最低能态的非晶体形态。
该算法的名称借用了这个说法。
符号说明
$E$ 物体的能量
$T$ 物体的温度
$k$ 玻尔兹曼常数
物理含义
根据热力学的原理，在温度为$T$时，出现能量差为$dE$的降温的概率为$p(dE)$，表示为：
$$p(dE) = e^{-\frac{dE}{kT}}$$
温度越高，出现一次能量差为$dE$的降温的概率就越大；温度越低，则出现降温的概率就越小。
基本思想
模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而有效避免陷入局部最优并最终趋于全局最优的优化算法。
即不同于只考虑局部最优的贪心算法，模拟退火算法会以一定的概率 $p$ 接受比当前差的解，因此有可能跳出局部的最优解，到达全局最优解。
一般认为该概率 $p$ 以 $e^{- \frac{\Delta E}{kT}}$ 时为最优，即：
$$p = \left\{ \begin{aligned} &e^{-\frac{E(x_{new})-E(x_{old})}{kT}} & E(x_{new})> E(x_{old}) \\ &1 & E(x_{new}) < E(x_{old}) \end{aligned} \right.$$
由上式可知，温度越高，接受比当前差的解的概率越高；温度越低，则接受比当前差的解的概率越低。
算法证明
具有渐近收敛性，已在理论上被证明是一种以概率1收敛于全局最优解的全局优化算法。此处证明等我看到了再补充叭hhh
算法步骤
（1）设置初始温度$T$，温度下限$T_{min}$，初始解状态$x$，每个$T$值的迭代次数$L$
（2）扰动产生新解$x_{new}$
（3）计算目标函数差值$dE$，若$dE<0$，则接受新值，若否则产生随机数$random(0,1)$，当 $p$ 大于该随机数时，接受新值。此时$x = x_{new}$
（4）在当前温度下执行$L$次(2)-(3)
（5）$T= \alpha T$ $\alpha$一般取接近1的值
（6）$if$ $T \leqslant T_{min}$ $end$，$else$返回(2)
举个栗子
利用模拟退火算法解决旅行商问题。
旅行商问题$(Travelling Salesman Problem, TSP)$：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。
确定初始温度$T = 2000$，确定停止准则为连续两次解路径不发生变动，确定迭代次数$L = 20000$，确定降温系数$\alpha = 0.98$。
确定初始解路径：$\left( C_1,\cdots,C_n \right)$
扰动产生新解：任选两个城市的序号$u$和$v$，将其顺序交换。
即将
$\left( C_1,\cdots,C_{u-1},C_u,C_{u+1},\cdots,C_{v-1},C_v,C_{v+1},\cdots,C_n \right)$
变为
$\left( C_1,\cdots,C_{u-1},C_v,C_{u+1},\cdots,C_{v-1},C_u,C_{v+1},\cdots,C_n \right)$
求出路径和，若新解路径和更短，则接受该解，若否则按 $e^{- \frac{\Delta E}{kT}}$的概率接受该解。
迭代$L$次后，将$T$按系数进行降温。
若满足停止准则，则停止迭代并输出解路径。
缺点分析
$SA$算法的效果较依赖于温度变化范围，迭代次数等，若选取不当则不一定能获得全局最优解。