模拟退火算法详解

一、引言

模拟退火算法（Simulated Annealing，简称SA）是一种通用概率型优化算法，用来在一个大的搜寻空间内找寻问题的最优解。其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。

二、算法原理

物理退火过程

加温过程：增强粒子的热运动，使其偏离平衡位置。当温度足够高时，固体将熔为液体，从而消除系统原先存在的非均匀状态。
等温过程：与周围环境交换热量而温度不变。对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态。
冷却过程：使粒子热运动减弱，系统能量下降、晶体结构得以形成。
Metropolis准则

固体在恒定温度下达到热平衡的过程可以用Monte Carlo方法进行模拟。虽然该方法简单，但必须大量采样才能得到比较精确的结果，因而计算量很大。1953年，Metropolis等提出重要性采样法，即用Metropolis准则对产生的新状态进行简略判断，从而减少计算量。

假设在状态x(i)时，系统受到某种扰动而使其状态变为x(j)。与此相对应，系统的能量也从E(i)变为E(j)，定义系统由状态x(i)变为x(j)的接收概率为p（概率可以根据具体的优化问题来设定）：

当E(j) < E(i)时，系统接受状态x(j)为新的当前状态；

当E(j) >= E(i)时，系统以概率exp[-(E(j)-E(i))/