当前位置：首页 > article >正文

模拟退火算法

article 2025/1/15 20:57:35

模拟退火算法(SA) 是一种导向性随机搜索的启发式算法，它是受加热金属的退火规律所启发而提出的一种求解组合优化问题的逼近算法。这个规律就是，在某个温度下,金属分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。

1 受热金属物体分子状态分

在温度度t下,金属物体的分子呈现出不同的状态，停留在状态r满足Boltzmann 概率分布

其中， $E(r)$ 表示分子在状态r 的能量，k>0为Boltzmann 常数, 而 $\bar{E}$ 表示分子能量的一个随机变量。设分子状态空间U是有限的，那么Z(t)应为

根据Boltzmann概率分布,分子有如下运动规律：

温度t很高时,金属物体的分子停留在任何状态的概率近似相等；
在同一温度t下,金属物体的分子停留在能量低的状态比在能量高的状态的概率大；
分子在能量最低状态的概率关于温度t下降；
分子停留在最低能量状态的概率随温度降低趋于1；
分子在非能量最低状态的概率随温度降低趋于0。

设金属分子的状态概率分布为

其中状态取为r=2,3,4,5,6, 而

可以由以下Boltzmann 函数曲线直观的看到上述分子运动规律。

2 基本模拟退火算法

基本步骤：

初始化可行解和温度；
根据 Boltzmann 概率退火；
重复第2步直到稳定状态（内循环）；
降温；
重复第2步至第4步直到满足终止条件或直到给定的步数（外循环）；
输出最好的解作为最优解。

3 模拟退火算法实现技术

3.1 初始化过程

初始可行解： $s_{0}$ ，根据问题随机产生；

初始温度 $t_{0}$ ，理论上要求应保证平稳分布中产生任意可行解的概率相等，即 $exp(-\Delta f_{ij}/t_{0})\approx 1$ ，其中 $\Delta f_{ij}=f(s_{i})-f(s_{i})$ 。取 $t_{0}=K\Delta _{0}$ ， $K$ K 为充分大的数,而

3.2 退火

退火过程就是在一给定温度下，由一个状态变到另一个状态，每一个状态到达的次数服从一个概率分布，即基于Metropolis 接受准则的过程，该过程达到平稳时停止。在状态 $s_{i}$ 时,产生的状态 $s_{j}$ 被接受的概率为

3.3 降温

一种降温方式为 $t_{k+1}=d(t_{k})$ ，其中 $d(t_{k})=\alpha t_{k}$ 。

另一种降温方法为 $t_{k}=\frac{M-k}{M}t_{0}$ ，其中M为温度下降的总次数。

3.4 内循环终止准则

固定步数：即在每一温度迭代相同的步数；
由接受和拒绝的比率控制迭代步数：
给定一个迭代步数上限U和一个接受次数指标r，在温度t实施退火过程，当接受次数等于r时，不再迭代，否则一直迭代到步数上限U。
或者给定一个接受指标R和迭代步数下限L，在温度t实施退火过程，迭代到步数L时，开始计算接受次数与总次数的比率，一旦比率超过R，不再迭代，否则一直迭代到步数上限U。
同样可以用拒绝次数控制终止准则。