智能优化算法 3：模拟退火算法

基本原理

模拟退火算法（Simulated Annealing，SA）的基本思想来源于固体退火过程。在退火过程中，固体被加热到高温，使得原子可以自由移动，然后逐渐降低温度，系统逐渐冷却并达到稳定状态，最终原子排列在能量最低的基态。

具体来说，模拟退火算法通过在解空间中随机采样，并允许一定的“退步”来避免陷入局部最优解，从而接近全局最优解。算法的关键在于“接受概率”，即是否接受一个较差解的概率随着温度的降低而降低。

把问题看作固体内部粒子，把最优解看作平衡态，用程序模拟退火的过程，就是模拟退火算法。

数学模型

热力学定义与 Boltzmann 分布

在统计物理学中，Boltzmann 分布描述了一个系统在温度 T 下，系统在不同能量状态 $E_i$ 的概率分布。具体形式为：

$P_i(T)=\frac{exp(\frac{-E_i}{k_B T})}{Z}$

$P_i(T)$ 是系统在温度 T 下处于状态 i 的概率
$k_B$ 是 Boltzmann 常数
$Z$ 是配分函数，表示系统所有可能状态（共 n 个）的概率之和，确保概率总和为 1，即
$Z=\sum_j exp(\frac{-E_j}{k_B T})$

模拟退火算法中的应用

假设热力学系统 S 有 n 个离散的状态，其中状态 i 的能量表示为 $E_i$ 。设在温度 $T_k$ 下系统达到热平衡，此时处于状态 i 的概率为：

$P_i(T_k)=C_k exp(\frac{-E_i}{T_k})$

上式可以被理解为对 Boltzmann 分布的简化形式，其中 $C_k$ 是一个归一化常数（类似于配分函数的倒数），确保所有状态概率之和为 1，即

$C_k=\frac{1}{\sum_{i=1}^n exp(\frac{-E_i}{T_k})}$

在模拟退火算法中，该方程用于计算接受一个较差解的概率，这个概率决定了算法是否接受一个能量较高的新解，以便跳出局部最优解并朝向全局最优解。

也就是智能优化算法中的从当前状态转移到新状态的转移（接受）概率。

温度对概率的影响

假设在同一温度 T 下，有两个不同的能量状态 $E_1 < E_2$ ，那么

$\frac{P_1(T)}{P_2(T)}=exp(-\frac{E_2-E_1}{T})$

因为 $E_1 < E_2$ ，所以 $exp(-\frac{E_2-E_1}{T})<1$ ，即 $P_1(T)<P_2(T)$ 。这说明在相同温度下，系统处于能量小状态的概率比处于能量大状态的概率要大。此时，模拟退火算法可以在部分高质量解区域进行重点搜索，提高搜索效率。

当 $T_k$ 很大，即温度高时， $\frac{E_i}{T_k} \rightarrow 0$ ，因此

$P_i(T_k)=C_k exp(\frac{-E_i}{T_k}) \rightarrow C_k = \frac{1}{\sum_{i=1}^n exp(\frac{-E_i}{T_k})} = \frac {1} n$

这表示在温度高时，系统处于任意能量状态的概率基本相同，接近 1/n。此时，模拟退火算法可以在解空间任何区域进行搜索（广域搜索），避免早熟收敛。

当 $T_k \rightarrow 0$ 时， $\frac{E_i}{T_k} \rightarrow \infty$ ，此时系统将无限接近能量最低状态，且低温下对能量差异非常敏感，即 $E_i$ 和 $E_j$ 的小差别会带来 $P_i(T_k)$ 和 $P_j(T_k)$ 的巨大差异。此时，模拟退火算法无限接近全局最优解（能量最低状态）。

算法模拟

模拟退火算法（SA）的模拟有三个要求：

初始温度足够高
降温过程足够慢
终止温度足够低

SA 通过接受较差解的策略来避免陷入局部最优解，最终收敛到全局最优解。这种接受较差解的概率由 Boltzmann 分布控制，其公式为：

$P(E,E',T)=exp(\frac{-\Delta E}{T})$

其中：

$E$ 是当前解的目标函数值
$E'$ 是新解的目标函数值
$\Delta E = E'-E$ 是目标函数值的变化
$T$ 是当前温度

模拟退火算法的构造

算法主要分为以下三个部分：

初始解和初始温度：
- 选择一个初始解 $S_0$ 。
- 设定一个初始温度 $T_0$ （足够高）
退火调度：
- 设定温度下降的策略（退火调度），如线性降温、指数降温等。
终止条件：
- 设定算法的终止条件，如温度降到一定阈值或者经过一定次数的迭代后停止。

具体的算法步骤如下：

初始化：
- 选择初始解 $S$
- 设定初始温度 $T$
- 设定温度下降的策略，例如 $T=rate*T$
- 设定初始迭代次数 $k=0$
迭代过程：
- 生成新解：从当前解 $S$ 的邻域中随机选择一个新解 $S'$
- 计算能量差：计算新解与当前解的能量差 $\Delta E = E(S')-E(S)$
- 接受概率：根据 Boltzmann 分布计算接受新解的概率 $P(E,E',T)=exp(\frac{-\Delta E}{T})$ $P (E, E^{'}, T) = e x p (\frac{- Δ E}{T})$
  - 如果 $\Delta E < 0$ （温度降低），接受新解（即 $S \leftarrow S'$ ）
  - 如果 $\Delta E \ge 0$ ，以概率 $P$ 接受新解
- 更新温度：根据退火调度函数更新温度 $T$
- 更新迭代次数： $k \leftarrow k+1$
终止条件：
- 如果达到终止条件，输出当前解 $S$ 作为最终结果
- 否则，返回步骤 2 继续迭代

SA 算法解决调度问题

问题定义

调度问题（Scheduling Problem）通常涉及将一组任务（作业）分配给有限的资源（例如机器、工人或时间段），以优化某个目标。常见的目标包括最小化总完成时间、最小化延迟或最大化资源利用率。

有 n 个作业，每个作业需要一定的处理时间。
有 m 台机器，每台机器可以并行处理一个作业。

目标：将这些作业分配到机器上，使得所有机器的总完成时间（Makespan）最小化。

Makespan：所有机器的最大完成时间，即最后一个完成作业的时间。

假设有两个机器和 4 个作业，执行时间分别为 [2, 4, 6, 8]。一种可能的分配是：
- 机器 1：作业 1 (2), 作业 3 (6)
- 机器 2：作业 2 (4), 作业 4 (8)
机器 1 的总完成时间是 2 + 6 = 8
机器 2 的总完成时间是 4 + 8 = 12
Makespan 是两者中的最大值，即 12

调度问题的目标就是找到一种分配，使得这个最大值最小。

算法实现

完整代码