【模拟退火】模板代码

模拟退火基础学习&模板

概述

简单说，模拟退火是一种随机化算法，用于求函数的极值。当一个问题的方案数量极大（甚至是无穷的）而且不是一个单峰函数时，我们常使用模拟退火求解。

它与爬山算法最大的不同是，在寻找到一个局部最优解时，赋予了它一个跳出去的概率，也就有更大的机会能找到全局最优解。

在 OI 领域，对应的，每次随机出一个新解，如果这个解更优，则接受它，否则以一个与温度和与最优解的差相关的概率接受它。

相关参数

初始温度：\(T\_0\)

结束温度：\(T\_s\)

降温系数：\(\Delta t\)

这样每次温度就是上次的温度乘上\(\Delta t\)

能量差：\(\Delta E=f(t_{new})−f(t_{now})\)，即新点的能量减去当前的能量（能量也就是函数值）

接受概率：\(P(\Delta E)=e^{\frac{−ΔE}{t}}\),t为当前温度，这样保证当能量差小于0时，概率P是大于1的，也就是必然接受，当能量差大于0时，能量差越大越不容易接受，t越大越容易接受（这里能量差需要具体问题具体分析，因为是退火，所以能量是越小越好）

模板

AcWing 3167. 星星还是树

二维平面有若干点,寻找一个点到所有点的距离之和最短，该点可以选择在平面中的任意位置，甚至与这 n 个点的位置重合。

#include <bits/stdc++.h>
using namespace std;
int const N = 100 + 5;
vector<pair<double, double>> a;
const double inf = 2e6;
double ans = inf;
// 获取两点之间的距离
double getd(pair<double, double> x, pair<double, double> y) {
    double dx = x.first - y.first;
    double dy = x.second - y.second;
    return sqrt(dx * dx + dy * dy);
}
// 计算一个点的能量
double getsum(pair<double, double> x) {  // f函数
    double re = 0;
    for (auto& p : a) {
        re += getd(x, p);
    }
    ans = min(ans, re);
    return re;
}
// 计算一个l到r的随机值
double rand(double l, double r) {  // 计算一个l到r的随机值
    return (double)rand() / RAND_MAX * (r - l) + l;
}
// Simulated Annealing
// 模拟退火：随机一个点，然后随机一个新的点，
//         如果新的点的能量更小，就移动到新的点，
//         否则以一定的概率移动到新的点
void sa() {
    pair<double, double> p(rand(0, 1e4), rand(0, 1e4));
    for (double t = 1e4; t > 1e-4; t *= 0.99) {
        pair<double, double> np(rand(p.first - t, p.first + t),
               rand(p.second - t, p.second + t));  // 随机一个新的点
        double dt = getsum(np) - getsum(p);        // 计算能量差
        if (exp(-dt / t) > rand(0, 1)) {
            p = np;
        }
    }
}
int main() {
    int n;
    cin >> n;
    srand((unsigned)time(NULL));
    for (int i = 0; i < n; ++i) {
        double x, y;
        cin >> x >> y;
        a.push_back({x, y});
    }
    for (int i = 0; i < 100; ++i)
        sa();
    cout << round(ans) << "\n";
}

技巧

1. 由于较为玄学，所以需要多跑几次模拟退火

2. 更改随机种子

3. 卡时间，例如小于0.8秒就一直跑模拟退火，充分利用测评时间

4. 超时说明降温系数太大了，降温过程太慢，方法：可以把0.999改为0.99