为了了解退火算法，这里先介绍爬山算法作为对比来抛砖引玉。

爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解,直到达到一个局部最优解。

如下图所示，红色曲线是我们的优化函数，现在我们的目标是找到该函数的最大值。假设初始位置是D，那么很显然根据爬山算法，我们的解会逐渐朝着E点移动，当到达E点时，由于在其周围邻域内并没有比E更高的点，算法即刻停止。但显然可以看到此时陷入了局部最优解当中，无法找到全局最优解。

那么模拟退火算法是如何解决这一问题的呢？

模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。

模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以图1为例，模拟退火算法在搜索到局部最优解E后，会以一定的概率接受到F的移动。也许经过几次这样的不是局部最优的移动后会到达G点，进而上升到H点，于是就跳出了局部最大值E。

模拟退火算法来源于固体退火原理，是一种基于概率的算法，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。 模拟退火算法(Simulated Annealing，SA)最早的思想是由N. Metropolis等人于1953年提出。1983年，S. Kirkpatrick 等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。

本质思想为以概率接受新状态：