读了论文《Investigation on the choice of the initial temperature in the Simulated Annealing:A Mushy State SA for TSP》，记录一下。

模拟退火算法（SA）

概念：模拟退火是一种被广泛研究的局部搜索元启发式算法，用于解决离散的和较小程度上的连续优化问题。模拟退火算法的关键是通过一种机制（允许移动到更差的目标值）跳出局部最优，以期找到全局最优。

应用：模拟退火算法通常用于解决离散优化问题，在较小程度上也用于解决连续优化问题

原理：模拟退火类似于固体的物理退火过程，在这个过程中，晶体固体被加热，然后让它非常缓慢地冷却，直到它达到最规则的晶格结构(即它的最小晶格能态)。

物理金属退火过程

算法流程：

1. 输入：初始解S0、初始温度T0、温度下降速率α、结束温度Tn、最大迭代次数max_iter

2. 输出：最优解S*

3. 初始化：i=1、T=T0、S=S0

4. while i < max_iter or T > Tn: // 判断终止条件

5.    S' = F(S)  // F(S)指通过邻域操作生成新的解

6.    if S' < S: 

7.        S = S' // 新的解得到改进

8.    if S' >= S:

9.        if random() < :  // 通过计算概率接受更差的解

10.            S=S'

11.    if S < S*: 

12.        S*=S // 更新全局最优解

分析：目标值是求最小时，为了跳出局部最优，需要接受较差的解。如果新的解 S' 的成本比原本的解 S 的成本更大，那么以一定概率接受 S'。这里体现在9。当温度越低，接受差解的概率也越低，当新旧解相差越大，接受新解的概率也越小。

主要影响因素：初始温度T0、温度下降速率α。初始温度越大、下降速率越低，找到全局最优解的可能性越大，但相对的，时间开销也越大。