著名的模拟退火算法，它是一种基于蒙特卡洛思想设计的近似求解最优化问题的方法。

　　美国物理学家 N.Metropolis 和同仁在1953年发表研究复杂系统、计算其中能量分布的文章，他们使用蒙特卡罗模拟法计算多分子系统中分子的能量分布。这相当于是本文所探讨之问题的开始，事实上，模拟退火中常常被提到的一个名词就是Metropolis准则，后面我们还会介绍。

　　美国IBM公司物理学家 S.Kirkpatrick、C. D. Gelatt 和 M. P. Vecchi 于1983年在《Science》上发表了一篇颇具影响力的文章：《以模拟退火法进行最优化（Optimization by Simulated Annealing）》。他们借用了Metropolis等人的方法探讨一种旋转玻璃态系统（spin glass system）时，发觉其物理系统的能量和一些组合最优（combinatorial optimization）问题（著名的旅行推销员问题TSP即是一个代表例子）的成本函数相当类似：寻求最低成本即似寻求最低能量。由此，他们发展出以 Metropolis  方法为本的一套算法，并用其来解决组合问题等的寻求最优解。

　　几乎同时，欧洲物理学家 V.Carny 也发表了几乎相同的成果，但两者是各自独立发现的；只是Carny“运气不佳”，当时没什么人注意到他的大作；或许可以说，《Science》杂志行销全球，“曝光度”很高，素负盛名，而Carny却在另外一本发行量很小的专门学术期刊《J.Opt.Theory Appl.》发表其成果因而并未引起应有的关注。

　　Kirkpatrick等人受到Metropolis等人用蒙特卡罗模拟的启发而发明了“模拟退火”这个名词，因为它和物体退火过程相类似。寻找问题的最优解（最值）即类似寻找系统的最低能量。因此系统降温时，能量也逐渐下降，而同样意义地，问题的解也“下降”到最值。

       固体退火：

       1.先将固体加热至溶化然后徐徐冷却。

       2.退火要徐徐进行使得系统在每一温度下都达到平衡。

       3.冷却时不能急剧减温。

       模拟退火算法：

       1、从某个初始解i0出发，经过L次解的变换（每次根据Metropoils算法求解），求得在给定温度下的相对最优解。

       2、减小控制参数T，重新变换解（如上）

       3、求得在控制参数T趋于0时的最优解

　　在热力学上，退火（annealing）现象指物体逐渐降温的物理现象，温度愈低，物体的能量状态会低；够低后，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低。大自然在缓慢降温（亦即，退火）时，可“找到”最低能量状态：结晶。但是，如果过程过急过快，快速降温（亦称「淬炼」，quenching）时，会导致不是最低能态的非晶形。

　　如下图所示，首先（左图）物体处于非晶体状态。我们将固体加温至充分高（中图），再让其徐徐冷却，也就退火（右图）。加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小（此时物体以晶体形态呈现）。

　　似乎，大自然知道慢工出细活：缓缓降温，使得物体分子在每一温度时，能够有足够时间找到安顿位置，则逐渐地，到最后可得到最低能态，系统最安稳。

　　1953年Metropolis提出了这样一个重要性采样的方法，即设从当前状态i生成新状态j，若新状态的内能小于状态i的内能即(EjT时，出现能量差为dE的降温的概率为p(dE)，表示为: 

　　其中: k是波尔兹曼常数，值为k=1.3806488(13)×10−23，

　　　　  exp表示自然指数，

　　　　  dE初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。】

（2）控制参数 T 的衰减函数

　　衰减函数可以有多种形式，一个常用的衰减函数是

　　其中，k为降温的次数，α 是一个常数，可以取为0.5~0.99，它的取值决定了降温过程的快慢。

　  【为了保证较大的搜索空间，a一般取接近于1的值，如0.95、0.9】

（3）退火速度：Markov链长度

　　Markov链长度的选取原则是：在控制参数T的衰减函数已经选定的前提下，Lk应能使在控制参数T的每一取值上达到准平衡。

　　从经验上说，对简单的情况可以令Lk=100n，n为问题规模。

　  【循环次数增加必定带来计算开销的增大，实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。】

（4）控制参数T的终值Tf (停止准则)。或者若干个相继的Mapkob链解没有产生变化，就是连续好多个解都没变化。

　　算法停止准则：对Metropolis准则中的接受函数

 　　分析可知，在T比较大的高温情况，指数上的分母比较大，而这是一个负指数，所以整个接受函数可能会趋于1，即比当前解 xi 更差的新解 xj 也可能被接受因此就有可能跳出局部极小而进行广域搜索，去搜索解空间的其他区域；而随着冷却的进行，T减小到一个比较小的值时，接收函数分母小了整体也小了，即难于接受比当前解更差的解，也就不太容易跳出当前的区域。如果在高温时，已经进行了充分的广域搜索，找到了可能存在的最好解的区域，而在低温再进行足够的局部搜索，则可能最终找到全局最优了。因此，一般终止温度 Tj 应设为足够小的正数，比如0.01~5。

　　【一般终止温度 Tj 应设为足够小的正数，比如0.01~5。】

　　模拟退火算法（simulated annealing，SA）是一种通用概率算法，用来在一个大的搜寻空间内寻找问题的最优解。

　　优点：能够有效解决NP难问题、避免陷入局部最优解。

　　　　    计算过程简单，通用，鲁棒性强，适用于并行处理，可用于求解复杂的非线性优化问题。

　　　　　模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；

　　　　    模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率收敛于全局最优解的全局优化算法；

　　　　　 模拟退火算法具有并行性

　　缺点：收敛速度慢，执行时间长，算法性能与初始值有关及参数敏感等缺点。

　　　　　由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。

　　　　（1)如果降温过程足够缓慢，多得到的解的性能会比较好，但与此相对的是收敛速度太慢；

 　　　　 (2)如果降温过程过快，很可能得不到全局最优解。

　　适用环境：组合优化问题。

　　改进：

　　　　(1)设计合适的状态产生函数，使其根据搜索进程的需要表现出状态的全空间分散性或局部区域性。

　　　　(2)设计高效的退火策略。

　　　　(3)避免状态的迂回搜索。

　　　　(4)采用并行搜索结构。

　　　　(5)为避免陷入局部极小，改进对温度的控制方式。

　　　　(6)选择合适的初始状态。

　　　　(7)设计合适的算法终止准则。

　　　　-------------------------------------------------------------------------------------------------------------------------------

　　　　(8)增加升温或重升温过程。在算法进程的适当时机，将温度适当提高，从而可激活各状态的接受概率，以调整搜索进程中的当前状态，避免算法在局部极小解处停滞不前。

　　　　(9)增加记忆功能。为避免搜索过程中由于执行概率接受环节而遗失当前遇到的最优解，可通过增加存储环节，将一些在这之前好的态记忆下来。

　　　　(10)增加补充搜索过程。即在退火过程结束后，以搜索到的最优解为初始状态，再次执行模拟退火过程或局部性搜索。

　　　　(11)对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态，而非标准SA的单次比较方式。

　　　　(12)结合其他搜索机制的算法，如遗传算法、混沌搜索等。

　　　　(13)上述各方法的综合应用。