模拟退火算法(Simulated Annealing，SA)最早的思想是由N. Metropolis 等人于1953年提出。1983 年,S. Kirkpatrick 等成功地将退火思想引入到组合优化领域。
它是基于Monte-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。
模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。
爬山算法是一种简单的局部贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。 主要过程： 随机选择一个登山的起点；每次拿相邻点与当前点进行比对,取两者中较优者,作为爬坡的下一步；重复第2步，直至该点的邻近点中不再有比其大的点；选择该点作为本次爬山的顶点,即为该算法获得的最优解。
从爬山算法的流程可以看出，它的实现虽然简单，但在遇到局部最优问题时，是很容易陷入局部最优、找不到全剧最优解的，同时初始随机登山点的选择，也对算法的结果影响很大、 所以，，它亟待解决的问题就是如何避免陷入局部最优。
模拟退火来自模拟物体在加热后分子达到高度混乱状态，然后慢慢冷却，物体内部的分子各自达到自己应该的状态； 简单来说、在过去的爬山算法中，当遇到临近点没有当前点好时，直接舍弃。这样确保了一时的最优，但从全局的角度，则丧失了寻找其它可能存在的局部最优点的情况。 因此在模拟退火的算法中，对一个不佳的临近点，会在一定概率下接受它成为最新点，这个概率就是退火的核心思想啦啊啦啦。
模拟退火其实也是一种贪心的思想，但是它通过概率接受较差的解、带来了跳出局部解的机会。 那这个概率怎么算了，就要看看退火中的一个核心概念--温度T； 假设评价函数为C(x)，且结果越小，说明解越好；原解为x，评价为C(x)，此时从临近区产生一个新的解x'、评价为C(x')； C(x')-C(x)；若 <0，说明新解更好，代替原解成为最优解；反之，说明新解没有原来的解好，此时计算概率 ，由于 <0，所以p一定是0-1之间的数，所以随机生成一个0-1的随机数，若在概率范围内，就接受这个点。 这个概率与 和T有关， 取决于新的解与原来解之间的差距，越差的点被保留的概率就越低；对于T，则是T越高，点被保留的概率越大，因此这个T就像现实生活中的温度一样，会逐步减少。
模拟退火算法的思想受启发于自然界中固体由高温到低温的过程中其内部分子状态及内部能量的变化规律。 退火 指物体 逐渐降温冷却 的物理现象。
温度越低，物体的能量越低，在结晶状态是系统的能量状态到达最低。
在自然中，缓慢降温（退火）可以导致结晶，而与之相对的快速降温（淬火）会导致不是最低能态的非晶体形态。 退火的过程可以表示为下图，左边为最初的非晶态状态；经过升温，系统能量增大后到达中间的状态；再缓慢降温到达晶体态，此时能量最小 我们用一个搜索函数最优解来直观表示：C为函数的全局最优解，在只采用贪心策略的情况下，如果从A点开始搜索，最终得到的解为B点，然而这只是一个局部的较好解。 为了避免陷入局部的最优解，模拟退火算法在搜索过程中加入了一个随机因素，会以一定的概率接收一个比当前解较差的解，因此就有可能越过B与C之间的高峰，到达全局最优解 在这里，可以将解（横坐标的值）理解为固体的状态，函数值理解为系统的内能。算法以固体所处的温度T为控制参数，随着T的下降使固体内能（目标函数值）也逐渐下降，直至趋于全局最小。
根据Metropolis准则，在温度为T时， 接受 能量从 的概率为P: 在特定温度下，经过充分转换，材料达到热平衡。这时材料处于状态 的概率为 其中 表示材料当前的状态， 表示材料的状态集合， 为玻尔兹曼常数。根据上式可以得到以下结论 因此，如果我们运用退火思想放在优化问题上，在降温过程中问题的解进行充分地“热交换”，即进行充分地重新排列，同样可以帮助我们寻找最优解，理论上也会具有达到全局最优解的性能！ 可以看出，算法实际上是两层循环嵌套，外层循环控制温度，内层循环来进行扰动产生新解。
随着温度逐渐降低，算法最终由可能收敛到全局最优，这里说有可能的原因是因为，在温度很低时，虽然从地内能状态跳到高内能状态的可能性不大，但是也有可能发生。
模拟退火法具有全局优化的性质在于它不仅具有“下山性”，而且具有“上山性”，即在迭代过程中可以有条件接受目标函数衰退的设计点，但这种可能性随着控制参数的减小而降为零；同时，模拟退火法在迭代过程中新点的选取由概率决定，新点的取值在统计上满足一定的概率分布，这就使它能够跳出局部最优区域而达到全局最优点。同“贪心类”算法(如最速下降法)（Method of Steepest Descent）比较，基于Metropolis接受准则的模拟退火法可以避免搜索过程陷入局部极小，并最终趋于问题的全局最优解。
模拟退火法能够处理任何连续或离散型变量，其搜索方式能够根据目标函数的变化自适应调整。
从数学上可以证明，对任意目标函数，它总能够得到问题的全局最优点。 模拟退火算法（Simulated Annealing Algorithm）是一种随机类全局优化方法，它来源于热力学中固体物质的退火冷却过程。当某一个系统的温度以足够慢的速度下降时系统近似处于热平衡状态，最后达到系统本身的最低能量状态。 在模拟退火算法的迭代寻优过程中，T必须缓慢减少，正如退火过程中，如果温度变化太快，系统会被冻结为一种亚稳态一样，控制参数变化太快，会使优化陷入局部极值点。
马踏棋盘的问题很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。
这种算法称为为贪心算法，也叫贪婪算法或启发式算法，它对整个求解过程的局部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。
这样的调整方法叫贪心策略，至于什么问题需要什么样的贪心策略是不确定的，具体问题具体分析。实验可以证明马遍历问题在运用到了上面的贪心策略之后求解速率有非常明显的提高，如果只要求出一个解甚至不用回溯就可以完成，因为在这个算法提出的时候世界上还没有计算机，这种方法完全可以用手工求出解来，其效率可想而知。贪心算法当然也有正确的时候。求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。
贪心法的应用算法有Dijkstra的单源最短路径和Chvatal的贪心集合覆盖启发式所以需要说明的是，贪心算法可以与随机化算法一起使用，具体的例子就不再多举了。其实很多的智能算法（也叫启发式算法），本质上就是贪心算法和随机化算法结合——这样的算法结果虽然也是局部最优解，但是比单纯的贪心算法更靠近了最优解。例如遗传算法，模拟退火算法。
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有 
