定义
模拟退火算法(simulated annealing，SA)，最早是由Metropolis受退火工艺启发所提出的，它是一种基于Monte Carlo迭代求解策略的随机寻优算法。它可以使系统有可能从局部最小处跳出，即能克服优化过程陷人局部极小；或者使系统克服初值依赖性。而算法的灵感来源于“退火工艺”，金属退火工艺的过程分为三步，分别是：加温、等温及冷却。整个退火过程是首先给金属加热到一定高温，使之打破原来的分子排布状态而处于随机分布的状态；持续这个状态一段时间后，系统会发生轻微的变化；然后随着对温度的缓慢降低，系统的分子排布状态逐渐会趋于平稳的状态，最终就会得到结构较的金属晶体，另外如果降温速度过快，淬火现象就会产生，那么得到的金属晶体就会出现结构缺陷。 由于金属退火工艺与常见的优化问题之间存在异曲同工之处，所以近年来该算法在某些常见的组合优化问题都有使用，该算法相对于其他优化算法具有更大的优点。模拟退火方法以Metropolis概率准则，在可行解的空间内进行随机搜索，反复抽样比较两次评价函数的差值从而决定是否保留新的解，进而得到全局最优。其中模拟退火算法的关键在于Metropolis准则，该准则是以一定的概率接收一些使结果变差的边沿状态，从而能够跳出局部最优。模拟退火算法相对于其他优化算法，对于目标函数的要求并非苛刻，能够在较大的概率下求得最优解，同时陷入局部最优解的概率低。对于连续型变量或者离散型变量均适用，同时对于目标函数和限制条件并没有任何要求。
原理
其算法流程图如图所示。
当系统处于状态 xold 时，由于受到外界影响产生扰动后，其状态变为 xnew ，而系统的 目标函数也会从 f xold 变成 f xnew ，系统由状态 xold 变为状态 xnew 的接受概率 P：
如果两个目标函数的差值f 0 ，则接收 xnew 的状态为当前状态；如果两个目标函数的差值f <0，则根据 Metropolis 准则以概率接收一些使结果变差的边沿状态，判断是否接收xnew 的状态为当前状态。产生一个在(0~1)的均匀分布的随机数q ，比较根据 Metropolis 准则，即公式(4.1)所计算的随机数 p 和q 的大小，根据两者值进行下一步状态的运行处理：当 p q时，接收 xnew 的状态为当前状态；否则继续保留状态 xold 为当前状态；p和随机数q 多次进行比较和状态迁移后，就达到了当前温度的平衡状态；然后继续降低温度，寻找每个当前温度下的平衡状态；重复上述过程，即使得最终“退火”的温度接近零摄氏度，这也就是跳出局部极值获得最大值的过程。
参考文献
[1] 卢宇婷, 林禹攸, 彭乔姿,等. 模拟退火算法改进综述及参数探究[J]. 大学数学, 2015,31(6):96-103.
[2] Metropolis N, Rosenbluth A W, Rosenbluth M N, et al. Equation of State Calculations by Fast Computing Machines[J]. Journal of Chemical Physics, 1953, 21(6):1087-1092.
[3] 李树有, 都志辉, 吴梦月,等. 模拟退火算法的并行实现及其应用[J]. 物理学报, 2001,50(7):1260-1263.
[4] 魏延, 谢开贵. 模拟退火算法[J]. 红河学院学报, 1999(4):7-11
[5] 罗静. 空间光耦合自动对准技术研究[D]. 陕西:西安理工大学,2018.
