模拟退火（Simulated Annealing，SA）是一种受固体退火过程启发的元启发式优化算法，用于在大型搜索空间中寻找近似全局最优解，它通过模拟物理退火过程（加热后缓慢冷却）来允许暂时接受较差的解，从而跳出局部最优,逐步收敛到全局最优区域。
- 固体退火过程：将金属加热至高温（原子活跃），再缓慢冷却（原子逐渐稳定到低能态），最终形成规则晶体（能量最低）。
- 优化问题对应关系：
- 系统状态 ⇔ 候选解
- 能量函数 ⇔ 目标函数
- 温度 ⇔ 控制参数（决定接受劣解的概率）
核心思想：Metropolis准则
算法以一定概率接受比当前解更差的解，避免陷入局部最优。
接受概率公式：
[
P = \begin{cases}
1, & \text{if } \Delta E < 0 \
e^{-\Delta E / T}, & \text{if } \Delta E \geq 0
\end{cases}
]
- (\Delta E = f(\text{新解}) - f(\text{当前解}))（目标函数差值）
- (T) 为当前温度（(T > 0)）
- (\Delta E < 0) 时新解更优，直接接受；(\Delta E \geq 0) 时以概率 (e^{-\Delta E / T}) 接受劣解。
算法流程
-
初始化
- 随机生成初始解 (S)，设定初始温度 (T0)、终止温度 (T{\text{min}})、降温系数 (\alpha \in (0,1))。
- 定义每个温度下的迭代次数（马尔可夫链长度）。
-
迭代过程（对每个温度 (T)）
- 内循环：在当前温度下重复以下步骤：
- 在当前解 (S) 的邻域内随机生成新解 (S')。
- 计算 (\Delta E = f(S') - f(S))。
- 若 (\Delta E < 0)，则接受 (S') 为新当前解；否则以概率 (e^{-\Delta E / T}) 接受。
- 外循环：降温 (T \leftarrow \alpha \cdot T)，检查是否满足终止条件（如 (T < T_{\text{min}}) 或解不再改善）。
- 内循环：在当前温度下重复以下步骤：
关键参数设计
- 初始温度 (T_0)：应足够高，使初始接受概率接近 1（通常通过实验调整）。
- 降温系数 (\alpha)：典型值 0.8~0.99，越小降温越快,但可能丢失全局最优。
- 马尔可夫链长度：每个温度下的迭代次数,应随问题规模增加。
- 终止条件：温度降至阈值,或连续若干温度解无变化。
为什么能跳出局部最优？
- 高温阶段：(T) 较大时，接受劣解的概率高,算法在解空间内广泛探索。
- 低温阶段：(T) 较小时，主要接受优解,趋于局部精细搜索。
- 缓慢降温：模拟了退火中的“热平衡”,给予算法足够时间逃离局部最优陷阱。
优缺点
优点：
- 通用性强，对目标函数要求低（无需连续、可微）。
- 能有效处理非线性、多峰问题。
- 实现相对简单。
缺点：
- 收敛速度慢,计算成本高。
- 参数调节依赖经验（如 (T_0, \alpha)）。
- 不保证找到精确全局最优,但可得到高质量近似解。
典型应用
- 组合优化：旅行商问题（TSP）、调度问题。
- 函数优化：连续/离散空间全局优化。
- 机器学习：神经网络参数调优、特征选择。
- 工程设计：VLSI布局、路径规划。
示例伪代码
初始化当前解 S，温度 T = T0
while T > T_min:
for i in range(马尔可夫链长度):
生成新解 S'
计算 ΔE = f(S') - f(S)
if ΔE < 0 或 random() < exp(-ΔE / T):
S = S' # 接受新解
T = α * T # 降温
输出最优解通过模拟退火，优化过程在“探索”（全局搜索）和“利用”（局部优化）之间取得平衡,成为解决复杂优化问题的经典方法。
版权声明：除非特别标注，否则均为本站原创文章，转载时请以链接形式注明文章出处。
