Metaphor

模拟退火与爬山算法

5分钟阅读

概述

模拟退火（Simulated Annealing, SA） 和 爬山算法（Hill Climbing, HC） 是两类基于随机化的局部搜索算法，用于在解空间中找到近似最优解。1

爬山算法是最简单的局部搜索，容易陷入局部最优。模拟退火通过引入”温度”概念和概率接受劣解来跳出局部最优，是竞赛中解决NP-hard问题的重要近似算法。

爬山算法（Hill Climbing）

算法思想

从某个初始解出发，在当前解的邻域内寻找更好的解，若找到则移动到该解，重复直到邻域内无更优解。

代码框架

struct Solution {
    // 解的表示
    double evaluate() const;  // 目标函数值
};
 
Solution hillClimbing(Solution init, int maxIter) {
    Solution cur = init, best = cur;
    for (int iter = 0; iter < maxIter; iter++) {
        Solution nxt = cur.neighbor();  // 产生邻域解
        if (nxt.evaluate() > cur.evaluate()) {
            cur = nxt;  // 接受更优解
            if (cur.evaluate() > best.evaluate()) best = cur;
        }
    }
    return best;
}

问题

爬山算法容易陷入局部最优解，无法跳出。

模拟退火算法

算法思想

模拟退火源于金属退火的物理过程。算法维护一个”温度”参数 ，初期温度高时允许接受较差的解，随着温度降低逐渐只接受更优解。

核心是 Metropolis准则：

其中 。

代码框架

struct Solution {
    double x, y;  // 解的表示（可能是坐标等）
    double evaluate() const;  // 目标函数值
};
 
Solution cur = init, best = cur;
double T = INIT_TEMP;  // 初始温度
double cool = COOL_RATE;  // 降温率，通常 0.995~0.999
 
while (T > MIN_TEMP) {
    for (int i = 0; i < ITER_PER_TEMP; i++) {
        Solution nxt = cur.neighbor(T);  // 基于温度产生邻域解
        double delta = nxt.evaluate() - cur.evaluate();
        
        if (delta > 0 || rnd() < exp(delta / T)) {
            cur = nxt;  // 接受新解
        }
        if (cur.evaluate() > best.evaluate()) {
            best = cur;
        }
    }
    T *= cool;  // 降温
}

关键参数

参数建议值说明
初始温度 足够高以跳出局部最优
降温率 越接近1降温越慢
每温度迭代次数温度内充分搜索
终止温度 足够小以收敛

典型应用

1. 平面最近邻问题（旅行商近似）

double dist(Point a, Point b) {
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
 
Solution neighbor(const Solution& cur, double T) {
    Solution nxt = cur;
    // 随机交换两个城市
    int i = rnd() % n, j = rnd() % n;
    swap(nxt.path[i], nxt.path[j]);
    // 基于温度调整扰动幅度
    if (rnd() < 0.5) {
        nxt.path[i] += (rnd() - 0.5) * T * 0.01;
    }
    return nxt;
}

2. 函数最优化

// 例：求解 f(x,y) = sin(x) + cos(y) 的最大值
struct Solution {
    double x, y;
    double evaluate() const {
        return sin(x) + cos(y);
    }
    Solution neighbor(double T) {
        Solution nxt;
        nxt.x = x + (rnd() - 0.5) * T;
        nxt.y = y + (rnd() - 0.5) * T;
        return nxt;
    }
};

3. 调度问题

模拟退火常用于 Job Shop Scheduling 等组合优化问题。

爬山+模拟退火对比

特性爬山算法模拟退火
时间复杂度
解的质量容易局部最优更好的全局近似
参数调优几乎不需要需要精心调整
适用场景解空间平滑NP-hard问题

进阶技巧

多次运行取最优

由于随机性，单次SA可能效果不佳。通常：

Solution bestOverall;
double bestVal = -INF;
for (int run = 0; run < 5; run++) {
    Solution cur = randomInit();
    Solution curBest = simulatedAnnealing(cur);
    if (curBest.evaluate() > bestVal) {
        bestVal = curBest.evaluate();
        bestOverall = curBest;
    }
}

自适应参数

  • 初期使用较大扰动，后期逐渐减小
  • 当解质量停滞时增大扰动

参考资料

Last updated: 2026-04-06

Footnotes

  1. 本内容参考 OI-Wiki 模拟退火，内容经过验证和扩展。 ↩

关系图谱