第三节 模拟退火算法

一、导言

模拟退火（Simulated Annealing, SA）算法是一种通用的随机搜索算法，是对局部搜索算法的扩展。与一般局部搜索算法不同，SA算法以一定的概率选择邻域中目标值相对较小的状态，是一种理论上的全局最优算法。虽然早在1953年Metropolis等就提出了模拟退火算法的思想，但直到1983年Kirkpatrick成功地将SA算法应用在组合最优化问题中，才真正创建了现代的模拟退火算法。

二、物理退火与模拟退火

在SA算法中，优化问题中的一个解xi及其目标函数c（xi）分别可以看成物理退火中物体的一个状态和能量函数，而最优解x*就是最低能量的状态。而设定一个初始高温、基于 Metropolis准则的搜索和控制温度参数t的下降分别相当于物理退火的加温、等温和冷却过程。下表描述了一个组合优化问题的求解过程与物理退火过程之间的对应关系。

三、模拟退火算法流程

图2-1给出了模拟退火算法的流程。

四、模拟退火算法的要素

在SA算法执行过程中，算法的效果取决于一组控制参数的选择，关键技术的设计对算法性能影响很大。

（一）状态表达

同前面介绍的遗传算法（GA）和禁忌搜索（TS）中的编码含义相同，状态表达是利用一种数学形式来描述系统所处的一种能量状态。

（二）邻域定义与移动

同TS算法一样，SA算法也是基于邻域搜索的。邻域定义的出发点应该是保证其中的解能尽量遍布整个解空间，其定义方式通常是由问题的性质所决定的，在前文介绍的TS算法中已经对邻域的定义方法做了阐述，这里就不再加以讨论了。

（三）热平衡

热平衡的达到相当于物理退火中的等温过程，是指在一个给定温度Tk下，SA算法基于Metropolis准则进行随机搜索，最终达到一种平衡状态的过程。

（四）降温函数

降温函数用来控制温度的下降方式，这是SA算法中的外循环过程。

常用的降温函数有如下两种。

（1）Tk+1=Tk ·r，其中r∈（0.95～0.99）, r越大温度下降越慢。这种方法的优点是简单易行，温度每一步都以相同的比率下降。

（2）Tk+1=Tk-ΔT, ΔT是温度每一步下降的长度。这种方法的优点是易于操作，而且可以简单控制温度下降的总步数，温度每一步下降的大小都相等。

五、批量计划问题的模拟退火算法

在现有文献中，多位国外学者都采用模拟退火算法求解了针对不同情况的批量计划问题，本书介绍Tang求解线型结构批量计划问题的模拟退火算法。

（一）二进制表达

解的表达是采用一个二进制矩阵，矩阵中每一位置上的值为“0”或“1”。

（二）移动策略

移动策略依赖模拟退火算法的设计。一个简单的但并不十分有效的方式是随机选择一种物料与时间点，如果该点没有装配需求则分配一个装配需求，否则取消装配需求。图2-2显示了移动策略的执行过程。尽管只有a32被选择进行移动，但其在线型生产系统中的上级与下级物料的状态值也需要进行调整。

（三）降温过程

最困难的部分是降温过程，确定一个合适的退火温度通常是一件非常麻烦的事情。这里，初始温度根据初始温度接受概率（0.95）来确定，降温系数为0.8～0.9的值。在每一温度下的移动次数由二进制矩阵的规模来决定。

（四）停止准则

模拟退火在几个连续温度下都没有改进当前最好解或已经达到了预先设定的迭代次数时，停止整个程序过程。