模拟退火算法（Simulated Annealing，SA）

基本思想：

模拟退火算法基于这样一种物理原理：一个高温物体降至常温，温度越高时降温的概率越大（降温越快），温度越低时降温的概率越小（降温越慢）。
模拟退火算法基于此种思想搜索，即多次降温（迭代），直到获得一个可行解。
在迭代过程中，模拟退火算法随机选择下一个状态，存在两种可能：
1.新状态更优，则接受新状态；
2.新状态更差，则以一定概率接收该状态，不过这个概率随时间推移逐渐降低。

来源：

• 出发点是基于物理中固体物质的退火过程与一般（在有限个可行解的集合中找出最优解的一类优化问题称为组合最优化问题）问题之间的相似性。
• 从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在求解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。

优质文章：

模拟退火算法--matlab实现简单问题
模拟退火算法（SA）(有点生硬)
模拟退火——算法思想与实例(这个老哥真牛逼，总结了几个算法)

关键理解：

• Metropolis算法
  爬山算法易于陷入局部最优解的缺陷是由贪心算法导致的。
  对此，N.Metropolis等人提出一种方法：
  借助以上所说的基于概率的思想，我们可以在爬山时（例如此时处于下图P点）以一定的概率选择比当前所处位置低的点，从而让程序获得摆脱这种陷阱的概率到达B点。

  
  

• 流程图

  
  
  流程图