跳至主要內容

模拟退火算法

GGBOND2025/12/19大约 8 分钟算法设计智能算法

模拟退火算法

算法简介

模拟退火算法（Simulated Annealing，简称SA）是一种基于物理退火过程的全局优化算法，由Metropolis等人于1953年提出，Kirkpatrick等人在1983年将其应用于组合优化问题。

该算法模拟了金属冶炼中的退火过程：将金属加热到高温，然后缓慢冷却，使原子排列更加有序，最终达到能量最低的稳定状态。在优化问题中，我们用"温度"来控制搜索过程，用"能量"来表示解的质量（能量越低，解越好）。

模拟退火算法的最大特点是：它允许以一定概率接受比当前解更差的解，这使得算法能够跳出局部最优，从而找到全局最优解。

算法原理

基本概念

  1. 状态：问题的一个可能解
  2. 能量（目标函数）：评价解质量的指标，能量越低越好
  3. 温度：控制算法搜索过程的参数，温度越高，接受差解的概率越大
  4. 冷却：温度逐渐降低的过程
  5. 邻域：当前解附近的其他解

物理类比

在金属退火过程中：

  • 高温状态：原子运动剧烈，可以自由移动到任何位置
  • 冷却过程：温度逐渐降低，原子运动变慢，逐渐趋向稳定位置
  • 低温状态：原子基本固定，达到能量最低的稳定状态

对应到优化问题：

  • 高温阶段：算法进行广泛搜索，接受差解的概率大，避免陷入局部最优
  • 降温阶段：搜索范围逐渐缩小，接受差解的概率减小
  • 低温阶段：算法进行精细搜索，收敛到最优解

Metropolis准则

Metropolis准则是模拟退火算法的核心，它决定了是否接受新解：

如果新解的能量 < 当前解的能量：
    接受新解
否则：
    以概率 P = exp(-(E_new - E_current) / T) 接受新解

其中：

  • E_new：新解的能量
  • E_current：当前解的能量
  • T：当前温度
  • exp：指数函数

解释：

  • 如果新解更好，一定接受
  • 如果新解更差，以一定概率接受。温度越高，接受差解的概率越大；能量差越大，接受差解的概率越小

算法流程

  1. 初始化：

    • 设定初始温度 T0
    • 设定终止温度 T_end
    • 设定降温系数 α（通常在0.8-0.99之间）
    • 随机生成初始解

  2. 外层循环（降温）：

    • 当温度 T > T_end 时执行

  3. 内层循环（同一温度下的搜索）：

    • 在当前温度下进行若干次迭代
    • 每次迭代：
      • 生成当前解的邻域解
      • 计算能量差 ΔE = E_new - E_current
      • 根据 Metropolis 准则决定是否接受新解
      • 如果接受，更新当前解

  4. 降温：T = α * T

  5. 终止：当温度降到终止温度时，输出当前最优解

参数说明

  1. 初始温度 T0：

    • 应该足够高，使得初始阶段接受差解的概率接近1
    • 通常通过实验确定，或设置为使初始接受率在0.8-0.9之间的温度

  2. 终止温度 T_end：

    • 应该足够低，使得算法基本不接受差解
    • 通常设置为接近0的值，如0.001或0.0001

  3. 降温系数 α：

    • 控制降温速度，通常取0.8-0.99
    • α越大，降温越慢，搜索越充分，但耗时越长
    • α越小，降温越快，可能错过全局最优

  4. 内层迭代次数：

    • 同一温度下的搜索次数
    • 通常取100-1000次

举例说明

例子1：寻找函数最小值

假设我们要找到函数 f(x) = x² + 2x + 1 在区间 [-10, 10] 上的最小值。

问题分析：

  • 这是一个简单的二次函数，最小值在 x = -1 处，f(-1) = 0
  • 我们用模拟退火算法来寻找这个最小值

算法步骤：

  1. 初始化：

    • 初始温度 T0 = 100
    • 终止温度 T_end = 0.001
    • 降温系数 α = 0.95
    • 初始解 x = 5（随机选择）
    • 当前能量 E = f(5) = 5² + 2*5 + 1 = 36

  2. 第一次迭代（T = 100）：

    • 生成邻域解：在当前解附近随机扰动，如 x_new = 4.8
    • 计算新能量：E_new = f(4.8) = 4.8² + 2*4.8 + 1 = 33.04
    • 能量差：ΔE = 33.04 - 36 = -2.96（新解更好）
    • 接受新解，更新 x = 4.8，E = 33.04

  3. 第二次迭代（T = 100）：

    • 生成邻域解：x_new = 5.2
    • 计算新能量：E_new = f(5.2) = 5.2² + 2*5.2 + 1 = 38.44
    • 能量差：ΔE = 38.44 - 33.04 = 5.4（新解更差）
    • 计算接受概率：P = exp(-5.4 / 100) = exp(-0.054) ≈ 0.947
    • 生成随机数 r = 0.3，因为 r < P，接受新解
    • 更新 x = 5.2，E = 38.44

  4. 继续迭代：在温度100下进行多次迭代，然后降温到 T = 95

  5. 降温过程：

    • T = 95, 90.25, 85.74, ... 逐渐降低
    • 随着温度降低，接受差解的概率减小
    • 解逐渐向最优解 x = -1 靠近

  6. 终止：当温度降到0.001时，输出最优解

结果：算法最终会找到接近 x = -1 的解，能量接近0

例子2：旅行商问题（TSP）

假设有4个城市，坐标分别为：

  • A(0, 0)
  • B(1, 2)
  • C(3, 1)
  • D(2, 0)

目标是找到访问所有城市并回到起点的最短路径。

问题建模：

  • 状态：一个访问顺序，如 [A, B, C, D]
  • 能量：路径总长度
  • 邻域：交换路径中两个城市的顺序

算法步骤：

  1. 初始化：

    • 初始路径：[A, B, C, D]
    • 计算路径长度：AB + BC + CD + DA = √5 + √5 + √2 + 2 ≈ 2.24 + 2.24 + 1.41 + 2 = 7.89

  2. 生成邻域解：

    • 交换B和C：[A, C, B, D]
    • 计算新路径长度：AC + CB + BD + DA = √10 + √5 + √5 + 2 ≈ 3.16 + 2.24 + 2.24 + 2 = 9.64
    • 能量差：ΔE = 9.64 - 7.89 = 1.75（新解更差）

  3. 接受判断：

    • 假设当前温度 T = 10
    • 接受概率：P = exp(-1.75 / 10) = exp(-0.175) ≈ 0.84
    • 如果随机数小于0.84，接受新解；否则拒绝

  4. 继续搜索：

    • 在高温阶段，接受差解的概率大，可以跳出局部最优
    • 在低温阶段，只接受更好的解，收敛到最优路径

结果：经过多次迭代，算法会找到最短路径

使用场景

适用场景

  1. 组合优化问题：

    • 旅行商问题（TSP）
    • 车辆路径问题（VRP）
    • 调度问题（作业调度、生产调度）
    • 装箱问题
    • 图着色问题

  2. 连续优化问题：

    • 函数优化
    • 参数调优
    • 工程设计优化

  3. 实际应用：

    • 集成电路设计：芯片布局优化
    • 物流配送：车辆路径规划
    • 生产调度：车间作业调度
    • 网络设计：网络拓扑优化
    • 机器学习：神经网络训练、特征选择
    • 金融领域：投资组合优化

优势

  1. 全局搜索能力强：能够跳出局部最优，找到全局最优解
  2. 通用性好：适用于各种优化问题，不依赖问题的具体性质
  3. 易于实现：算法原理简单，代码实现容易
  4. 灵活性强：可以通过调整参数控制搜索过程

局限性

  1. 参数敏感：初始温度、降温系数等参数的选择对结果影响较大
  2. 收敛速度慢：相比其他算法（如梯度下降），SA收敛较慢
  3. 随机性：算法结果有随机性，可能需要多次运行
  4. 参数调优困难：需要经验来确定合适的参数

算法改进

为了提高模拟退火算法的性能，研究者提出了多种改进版本：

  1. 自适应模拟退火：

    • 根据搜索情况动态调整温度
    • 自适应调整降温系数

  2. 并行模拟退火：

    • 同时运行多个退火过程
    • 加速搜索速度

  3. 混合模拟退火：

    • 与其他算法结合，如遗传算法、禁忌搜索
    • 结合局部搜索算法进行精细搜索

  4. 快速模拟退火：

    • 采用更快的降温策略
    • 减少计算时间

参数选择建议

  1. 初始温度：

    • 通过实验确定，使初始接受率在0.8-0.9之间
    • 或者设置为问题规模的10-100倍

  2. 降温系数：

    • 通常取0.8-0.99
    • 问题越复杂，降温系数越大

  3. 终止温度：

    • 通常设置为0.001或更小
    • 或者当最优解连续多次迭代没有改进时终止

  4. 内层迭代次数：

    • 通常取100-1000次
    • 问题规模越大，迭代次数越多

总结

模拟退火算法是一种强大的全局优化算法，通过模拟物理退火过程来寻找最优解。它的核心思想是：在高温阶段广泛搜索，允许接受差解以避免陷入局部最优；在低温阶段精细搜索，收敛到最优解。

模拟退火算法具有全局搜索能力强、通用性好、易于实现等优点，广泛应用于各种优化问题。虽然存在参数敏感、收敛速度慢等局限性，但通过适当的改进和参数调优，SA可以在大多数优化问题中取得良好的效果。

对于初学者来说，模拟退火算法是一个很好的入门算法，因为它直观易懂，且容易编程实现。在实际应用中，建议根据具体问题调整参数，或使用改进版本的SA以获得更好的性能。

Copyright © 2026 GGBOND