模拟退火算法原理及应用

2025/07/02

10 mins read See this issue

# Javascript

Back

To Top

模拟退火算法（Simulated Annealing, SA）是一种受物理中固体退火过程启发的随机优化算法，用于在大型搜索空间中寻找近似全局最优解，尤其适用于解决组合优化问题（如旅行商问题、调度问题等）。

# 核心思想

物理退火类比：
- 在冶金学中，退火是将材料加热至高温后缓慢冷却，使其原子从高能状态逐渐达到低能、稳定的晶态。
- 模拟退火算法模仿这一过程：通过控制“温度”参数，逐步降低系统的随机性，使解从随机探索转向局部精细调整。
接受劣解的概率：
- 与传统贪心算法（只接受更优解）不同，SA以一定概率接受暂时劣解，从而跳出局部最优，增加找到全局最优的可能性。

# 算法步骤

初始化：
- 随机生成初始解 ( $x_0$ )。
- 设置初始温度 ( $T$ )（高温）、降温系数 ( $\alpha$ )（如0.95）、终止温度 ( $T_{\text{min}}$ )。
迭代过程（对每个温度 ( $T$ )）：
- 生成新解：在当前解附近随机扰动（如交换、移动等操作）得到候选解 ( $x_{\text{new}}$ )。
- 计算能量差：( $\Delta E = E(x_{\text{new}}) - E(x_{\text{current}})$ )（目标函数值的差）。
- 接受准则：
  - 若 ( $\Delta E \leq 0$ )（更优解），直接接受 ( $x_{\text{new}}$ )。
  - 若 ( $\Delta E > 0$ )（劣解），以概率 ( $P = e^{-\Delta E / T}$ ) 接受 ( $x_{\text{new}}$ )（Metropolis准则）。
- 降温：( $T \leftarrow \alpha \cdot T$ )（缓慢降低温度）。
终止条件：
- 温度降至 ( $T_{\text{min}}$ ) 或解不再显著改进。

# 关键参数

初始温度 ( $T$ )：需足够高以允许广泛探索。
降温速率 ( $\alpha$ )：过快易陷入局部最优，过慢则收敛慢。
马尔可夫链长度：每个温度下的迭代次数，影响搜索充分性。

# 特点

优点：
- 能跳出局部最优，适合非凸、多峰问题。
- 实现简单，对目标函数要求低（无需连续、可导）。
缺点：
- 参数调优敏感（如降温计划）。
- 收敛速度较慢，可能需大量计算。

# 应用场景

组合优化（如路径规划、排班问题）。
机器学习中的参数优化。
电路设计、图像处理等。

通过模拟退火算法，可以在复杂问题中以较高概率找到接近全局最优的解，尽管无法保证绝对最优。

# 模拟退火算法实现

class SimulatedAnnealing {
  /**
   * 模拟退火算法构造函数
   * @param {Object} params 参数对象
   * @param {Function} params.getInitialSolution 获取初始解的函数
   * @param {Function} params.getNeighbor 获取相邻解的函数
   * @param {Function} params.getCost 计算解的成本函数
   * @param {Number} [params.initialTemp=100] 初始温度
   * @param {Number} [params.coolingRate=0.95] 冷却速率
   * @param {Number} [params.minTemp=0.001] 最小温度
   * @param {Number} [params.iterationsPerTemp=100] 每个温度的迭代次数
   */
  constructor(params) {
    this.getInitialSolution = params.getInitialSolution;
    this.getNeighbor = params.getNeighbor;
    this.getCost = params.getCost;
    this.initialTemp = params.initialTemp || 100;
    this.coolingRate = params.coolingRate || 0.95;
    this.minTemp = params.minTemp || 0.001;
    this.iterationsPerTemp = params.iterationsPerTemp || 100;
    
    this.currentSolution = null;
    this.bestSolution = null;
    this.currentCost = Infinity;
    this.bestCost = Infinity;
    this.temperature = this.initialTemp;
  }

  /**
   * 运行模拟退火算法
   * @returns {Object} 包含最佳解和最佳成本的对象
   */
  run() {
    this.currentSolution = this.getInitialSolution();
    this.bestSolution = [...this.currentSolution];
    this.currentCost = this.getCost(this.currentSolution);
    this.bestCost = this.currentCost;
    
    while (this.temperature > this.minTemp) {
      for (let i = 0; i < this.iterationsPerTemp; i++) {
        this.step();
      }
      this.temperature *= this.coolingRate;
    }
    
    return {
      solution: this.bestSolution,
      cost: this.bestCost
    };
  }

  /**
   * 执行一步退火过程
   */
  step() {
    const neighbor = this.getNeighbor(this.currentSolution);
    const neighborCost = this.getCost(neighbor);
    const costDifference = neighborCost - this.currentCost;
    
    // 如果新解更好，或者满足接受概率，则接受新解
    if (costDifference < 0 || Math.random() < Math.exp(-costDifference / this.temperature)) {
      this.currentSolution = [...neighbor];
      this.currentCost = neighborCost;
      
      // 更新最佳解
      if (this.currentCost < this.bestCost) {
        this.bestSolution = [...this.currentSolution];
        this.bestCost = this.currentCost;
      }
    }
  }
}

# 退火算法示例：解决旅行商问题(TSP)

// 城市坐标数据
const cities = [
  { name: "New York", x: 40.7128, y: -74.0060 },
  { name: "Los Angeles", x: 34.0522, y: -118.2437 },
  { name: "Chicago", x: 41.8781, y: -87.6298 },
  { name: "Houston", x: 29.7604, y: -95.3698 },
  { name: "Phoenix", x: 33.4484, y: -112.0740 },
  { name: "Philadelphia", x: 39.9526, y: -75.1652 },
  { name: "San Antonio", x: 29.4241, y: -98.4936 },
  { name: "San Diego", x: 32.7157, y: -117.1611 }
];

// 计算两个城市之间的距离
function calculateDistance(city1, city2) {
  const dx = city1.x - city2.x;
  const dy = city1.y - city2.y;
  return Math.sqrt(dx * dx + dy * dy);
}

// 计算路径总长度
function calculateTotalDistance(path) {
  let totalDistance = 0;
  for (let i = 0; i < path.length - 1; i++) {
    totalDistance += calculateDistance(path[i], path[i + 1]);
  }
  // 返回起点
  totalDistance += calculateDistance(path[path.length - 1], path[0]);
  return totalDistance;
}

// 获取初始解（随机路径）
function getInitialSolution() {
  const path = [...cities];
  for (let i = path.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [path[i], path[j]] = [path[j], path[i]];
  }
  return path;
}

// 获取相邻解（交换两个随机城市）
function getNeighbor(path) {
  const newPath = [...path];
  const i = Math.floor(Math.random() * newPath.length);
  let j = Math.floor(Math.random() * newPath.length);
  while (j === i) {
    j = Math.floor(Math.random() * newPath.length);
  }
  [newPath[i], newPath[j]] = [newPath[j], newPath[i]];
  return newPath;
}

// 创建模拟退火实例
const sa = new SimulatedAnnealing({
  getInitialSolution,
  getNeighbor,
  getCost: calculateTotalDistance,
  initialTemp: 10000,
  coolingRate: 0.99,
  minTemp: 0.0001,
  iterationsPerTemp: 1000
});

// 运行算法
console.time("Simulated Annealing");
const result = sa.run();
console.timeEnd("Simulated Annealing");

// 输出结果
console.log("最佳路径成本:", result.cost);
console.log("最佳路径:");
result.solution.forEach(city => console.log(city.name));
console.log("返回起点:", result.solution[0].name);

# 运行结果示例

运行上述代码可能会得到类似以下输出（具体结果因随机性而不同）：

Simulated Annealing: 125.456ms
最佳路径成本: 4235.67893456789
最佳路径:
San Diego
Los Angeles
Phoenix
Houston
San Antonio
Chicago
New York
Philadelphia
返回起点: San Diego

# 代码说明

SimulatedAnnealing类：封装了模拟退火算法的核心逻辑
- run()方法执行完整的退火过程
- step()方法执行单步退火操作
TSP问题实现：
- calculateDistance计算两个城市间的距离
- calculateTotalDistance计算路径总长度
- getInitialSolution生成随机初始路径
- getNeighbor通过交换两个城市生成相邻解
参数设置：
- initialTemp: 初始温度设为10000
- coolingRate: 冷却速率设为0.99（较慢冷却）
- minTemp: 最小温度设为0.0001
- iterationsPerTemp: 每个温度迭代1000次