学习笔记 - 模拟退火

早该写了，发现总是忘记，所以不得不写。

用处

最优化问题，并且规模很小。

你可以把不是模拟退火的用模拟退火做，并且获得不错的分数，只要你善于调整参数。

用法

假设我们已经有了一个策略，我们对它进行随机扰动，但是要扰动得比较有道理。

所以我们模拟退火，实时维护一个温度 $T$，初始是初温 $T_0$，每次乘上 $r(0<r<1)$ 以指数级减少，直到 $T$ 小于某个很小的数 $\epsilon$。每次随机扰动规模要和 $T$ 有关。每次扰动出新解：

• 如果新解比原解优，则接受；
• 否则以 $e^{-\frac{\Delta E}{T}}$ 的概率接受。$\Delta E > 0$，是新旧解优劣程度差的一种量化。

其他的处理方法：

• 可以卡时，就是在时间不超过某个限制时不断重复模拟退火。
• 维护全局最优解作为答案。

我比较喜欢这两个做法吧。

随便丢几个代码就知道这咋写了。所有的模拟退火题都是板子题。难点可能在于调整参数，包括 $T_0,r,\epsilon,\Delta E$。

例题

Luogu P2503 [HAOI2006] 均分数据。

#include <bits/stdc++.h>
using namespace std;

constexpr int MXN = 22;
constexpr int MXM = 7;
constexpr double INIT = 1000;
constexpr double RATE = 0.98;
constexpr double ENDS = 1e-4;
int N, M, val[MXN], sum[MXM], bel[MXN];
double av, tans;

double cal() {
  double ans(0);
  for (int i(0); i != M; ++i) ans += (av - sum[i]) * (av - sum[i]);
  return sqrt(ans / M);
}

double gene(mt19937& rnd) {
  double mans(0), nans(0);
  mans = nans = cal();
  for (double temp(INIT); temp > ENDS; temp *= RATE) {
    int id(rnd() % N), col(0);
    do {
      col = rnd() % M;
    } while (col == bel[id]);
    // cout << id << ' ' << col << ' ';
    sum[bel[id]] -= val[id];
    swap(bel[id], col);
    sum[bel[id]] += val[id];
    nans = cal();
    if (nans <= mans) {
      mans = nans;
    } else if (rnd() * 1.0 / UINT32_MAX > exp(-(nans - mans) / temp)) {
      sum[bel[id]] -= val[id];
      swap(bel[id], col);
      sum[bel[id]] += val[id];
    }
    // cout << mans << ' ' << nans << endl;
  }
  return mans;
}

int main() {
  random_device sd;
  mt19937 rnd(sd());
  cin >> N >> M;
  for (int i(0); i != N; ++i) {
    cin >> val[i];
    bel[i] = 0;
    sum[0] += val[i];
    av += val[i];
  }
  av /= M;
  tans = gene(rnd);
  while (clock() * 1.0 / CLOCKS_PER_SEC < 0.3) tans = min(tans, gene(rnd));
  cout << setprecision(2) << fixed << tans << endl;
  return 0;
}

P2538 [SCOI2008] 城堡。

#include <bits/stdc++.h>
using namespace std;

constexpr int MXN = 22;
constexpr int MXM = 7;
constexpr double INIT = 1000;
constexpr double RATE = 0.98;
constexpr double ENDS = 1e-4;
int N, M, val[MXN], sum[MXM], bel[MXN];
double av, tans;

double cal() {
  double ans(0);
  for (int i(0); i != M; ++i) ans += (av - sum[i]) * (av - sum[i]);
  return sqrt(ans / M);
}

double gene(mt19937& rnd) {
  double mans(0), nans(0);
  mans = nans = cal();
  for (double temp(INIT); temp > ENDS; temp *= RATE) {
    int id(rnd() % N), col(0);
    do {
      col = rnd() % M;
    } while (col == bel[id]);
    // cout << id << ' ' << col << ' ';
    sum[bel[id]] -= val[id];
    swap(bel[id], col);
    sum[bel[id]] += val[id];
    nans = cal();
    if (nans <= mans) {
      mans = nans;
    } else if (rnd() * 1.0 / UINT32_MAX > exp(-(nans - mans) / temp)) {
      sum[bel[id]] -= val[id];
      swap(bel[id], col);
      sum[bel[id]] += val[id];
    }
    // cout << mans << ' ' << nans << endl;
  }
  return mans;
}

int main() {
  random_device sd;
  mt19937 rnd(sd());
  cin >> N >> M;
  for (int i(0); i != N; ++i) {
    cin >> val[i];
    bel[i] = 0;
    sum[0] += val[i];
    av += val[i];
  }
  av /= M;
  tans = gene(rnd);
  while (clock() * 1.0 / CLOCKS_PER_SEC < 0.3) tans = min(tans, gene(rnd));
  cout << setprecision(2) << fixed << tans << endl;
  return 0;
}

QOJ 3195 Within Arm’s Reach。

#include <bits/stdc++.h>
using namespace std;

const int MXN = 25;
const double T = 100;
const double EPS = 1e-13;
const double RATE = 0.99;
const double PI = acos(-1);
int N, len[MXN], tx, ty;
double tlen, angle[MXN], ans[MXN], dans[MXN], dlen;

inline double cald(double x, double y) {
  return sqrt(x * x + y * y);
}
inline pair<double, double> conv(double l, double theta) {
  return make_pair(l * cos(theta), l * sin(theta));
}
inline double random(mt19937& rnd) {
  return rnd() * 2.0 / UINT32_MAX - 1;
}
pair<double, double> calc(bool output_mode = false) {
  double x(0), y(0), a(0);
  for (int i(0); i != N; ++i) {
    a = angle[i];
    pair<double, double> vec(conv(len[i], a));
    x += vec.first, y += vec.second;
    if (output_mode)
      cout << setprecision(6) << fixed << x
           << ' ' << setprecision(6) << fixed << y << endl;
  }
  return make_pair(x, y);
}

int main() {
  cin >> N;
  for (int i(0); i != N; ++i) cin >> len[i];
  cin >> tx >> ty;
  tlen = cald(tx, ty);
  mt19937 rnd((random_device())());
  double dlen(cald(calc().first, calc().second));
  while (clock() * 1.0 / CLOCKS_PER_SEC < 0.9) {
    pair<double, double> vec(calc());
    double nlen(cald(vec.first, vec.second));
    for (double temp(T); temp > EPS; temp *= RATE) {
      for (int i(1); i != N; ++i)
        angle[i] = ans[i] + random(rnd) * temp / 100 * 2 * PI;
      vec = calc();
      double clen(cald(vec.first, vec.second));
      if (abs(clen - tlen) < abs(nlen - tlen) ||
          rnd() < exp((abs(nlen - tlen) - abs(clen - tlen)) * 10000 / temp)) {
        for (int i(0); i != N; ++i) ans[i] = angle[i];
        nlen = clen;
      }
      if (abs(clen - tlen) < abs(dlen - tlen)) {
        for (int i(0); i != N; ++i) dans[i] = angle[i];
        dlen = clen;
      }
    }
  }
  for (int i(0); i != N; ++i) angle[i] = dans[i];
  pair<double, double> cur(calc());
  if (tlen) angle[0] = atan2(ty, tx) - atan2(cur.second, cur.first);
  else angle[0] = 0;
  for (int i(1); i != N; ++i) angle[i] += angle[0];
  calc(1);
  return 0;
}