http://blog.csdn.net/lanchunhui/article/details/51112227

机器学习基础（四十五）—— 模拟退火（Simulated Annealing）

机器学习（123） 

版权声明：本文为博主原创文章，未经博主允许不得转载。

模拟退火算法是受物理学领域启发而提出的一种优化算法。所谓的退火是指将合金加热后再慢慢冷却的过程。大量的原子因为受到激发而向周围跳跃，然后又逐渐稳定到一个低能阶的状态，所以这些原子能够找到一个低能阶的配置（configuration）。

退火算法以一个问题的随机解开始。它用一个变量来表示温度，这一温度开始时非常高，而后逐渐变低：

退火算法的每一次迭代期间，算法会首先随机地选择某个数字，然后朝某个方向变化。算法最为关键的部分在于，如果新的变化带来的新的成本更低，则新的题解就会成为当前题解，这个爬山算法类似。不过如果成本值更高的话，则新的题解仍将可能成为当前题解（这是不同于爬山算法的地方）。这也是避免出现局部最小值的一种改进。

某些情况下，我们能够得到一个更优的解之前转向一个更差的解是很有必要的。模拟算法之所以管用，不仅在于它总是会接受一个更优的解，而且在退货的开始阶段会（以一定概率）接受表现较差的解。随着退火过程（温度减少）的不断进行，算法越来越不可能接受较差的解。知道最后节点，它将只会接受更优的解。更高成本的题解，其被接受的概率如下： 

T 温度（表示接受较差解的意愿）开始非常高，指数部分接近于0，所以概率几乎为1.随着温度的递减，高成本和低成本值之间的差异越来越重要——差异越大，概率越低。因此此算法只倾向于稍差的解而不会是非常差的解。