细说|模拟退火算法

Doris232

模拟退火算法（Simulated Annealing，SA）算法的思想最早是由Metropolis等提出的。其出发点是基于物理中固体物质的退火过程与一般的组合优化问题之间的相似性。模拟退火法师一种通用的优化算法，其物理退火过程由以下三部分组成：

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

其中，加温过程对应算法的设定初温，等温过程对应算法的 Metropolis 抽样过程，冷却过程对应控制参数的下降。这里能量的变化就是目标函数，要得到的最优解就是能量最低态。Metropolis准则 是 SA 算法收敛于全局最优解的关键所在，Metropolis准则以一定的概率接受恶化解，这样就使算法跳离局部最优的陷阱。
模拟退火算法可以用以求解不同的非线性问题，对于不可微甚至不连续的函数进行优化，能以较大概率球的全局最优解。该算法还具有较强的鲁棒性、全局收敛性、隐含并行性以及广泛性和适应性，并且可以处理不同类型的优化设计变量（离散的、连续的、全局收敛的和混合的），不需要任何的辅助信息，对目标函数和约束函数没有任何要求。利用 Metropolis算法并适当控制温度下降的过程，在优化问题中具有很强的竞争力。
模拟退火算法（SA）的实现过程主要如下：