模拟退火算法（Simulated Annealing， SA）

概念：

模拟退火算法(Simulated Annealing，SA)最早的思想是由N. Metropolis [1] 等人于1953年提出。1983 年,S. Kirkpatrick 等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。

模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。

基于神经网络动态转移过程，状态掉进了局部最优解里了，就是能量函数没有达到最低，只是掉进了局部能量最低的状态，这和我们梯度容易获得局部最优解差不多，大家这样理解就好，想要深入理解的建议自己多参考文献。为了解决伪吸引子的问题，人们提出了模拟退火算法和玻尔兹曼机彻底解决了伪吸引子的问题。

模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。

物理退火过程：

加温过程——增强粒子的热运动，消除系统原先可能存在的非均匀态；
等温过程——对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝*能减少的方向进行，当*能达到最小时，系统达到平衡态；
冷却过程——使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。

热力学中的退火现象指物体逐渐降温时发生的物理现象：

温度越低，物体的能量状态越低，到达足够的低点时，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低。缓慢降温时，可达到最低能量状态；但如果快速降温，会导致不是最低能态的非晶形。

模仿自然界退火现象而得，利用了物理中固体物质的退火过程与一般优化问题的相似性从某一初温度开始，伴随温度的不断下降，结合概率突跳特性在解空间中随机寻找全局最优解。

组合优化问题	金属物体
解	粒子状态
最优解	能量最低的状态
设定初温	溶解过程
Metropolis抽样过程	等温过程
控制参数的下降	冷却
目标函数	能量

模拟退火算法的计算步骤

①初始化,任选初始解，给定初始温度，终止温度，令迭代指标。
注：选择时，要足够高，使
初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L
循环由此开始，对k=1, …, L做第2至第步5。
②随机产生一个领域解，，(其中N(i)表示i的领域)。计算目标值增量
产生新解S′，计算增量ΔT=C(S′)-C(S)，其中C(S)为代价函数
③若,令转步④（j比i优秀无条件赋值）
否则产生，若，则令，此时，即完成赋值。
注：高时，进行广域搜索；低时，局域搜索。
若ΔT<0则接受S′作为新的当前解，否则以概率exp(-ΔT/T)接受S′作为新的当前解.
④若达到热平衡（内循环次数大于）时，转至步⑤，否则转步②。
如果满足终止条件则输出当前解作为最优解，结束程序。
终止条件通常取为连续若干个新解都没有被接受时终止算法。
⑤降低，若停止，否则转步②
注：降低的方法有以下两种
1.较好的方法，其中。
2.
T逐渐减少，且T->0，然后转第2步。