文中图的来源

模拟退火

如图,退火是分子排列由无序变为有序的一个过程,在这个过程中物质会逐渐到达一个最稳定的状态(即能量最低)。

而模拟退火就是人为的去模拟这个过程,从而有概率的找到函数的全局最优解。

其大致过程可分为:

  1. 设定初始温度$T_0$;随机函数的初始输入,并计算其输出。
  2. 对当前输入进行随机偏移,并重新计算新的输出。
  3. 比较两种输出的优劣。若新输入的解更优,则将新输入作为当前输入继续迭代,否则有概率的采取新输入作为当前输入。
  4. 按照某种速率降低温度,当温度达到指定值(通常为0)时,停止迭代。

可以看到模拟退火算法的表现和效率取决于四个值:初始温度$T_0$,随机偏移量,采取较劣解的概率,温度降低的速率。这也是我们可以调参的地方。

其中面对较劣解也有概率采纳的操作,可以使得迭代不会一直陷入局部最优解,而是有概率可以到达全局最优解。

随机偏移量随着温度的降低而逐渐缩小,可以保证最后结果可以趋于稳定。温度高的时候随即偏移量大可以使得有几率跳脱出局部最优解。

例题

luogo1337

本题的能量函数是桌面距离乘以物体重量。桌面上绳子长度越短,桌面下绳子长度就越长,物体的重力势能就越小。
当所有物体重力势能总和达到最小时也就达到了稳态。

至于起始点我们可以采用这n个点的平均值(虽然我没这么写),这样应该会更快到达全局最优点。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;
int x[maxn], y[maxn], w[maxn];
int n;
double ansx, ansy, answ;

double cal(double xx, double yy) {
  double ret = 0;
  for (int i = 0; i < n; i++) {
    double dx = xx - x[i], dy = yy - y[i];
    ret += sqrt((dx * dx + dy * dy)) * w[i];
  }
  return ret;
}
void sa() {
  double t = 3000;  // 可调
  double X = ansx, Y = ansy;
  while (t > 1e-14) {                             // 可调
    double nx = X + (rand() * 2 - RAND_MAX) * t;  // 根据温度调整偏移值
    double ny = Y + (rand() * 2 - RAND_MAX) * t;
    double energy = cal(nx, ny);
    double delt = energy - answ;
    if (delt < 0) {
      X = nx, Y = ny;
      ansx = X, ansy = Y, answ = energy;
    } else if (exp(-delt / t) * RAND_MAX > rand())
      X = nx, Y = ny;
    t *= 0.996;  // 可调
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d%d%d", x + i, y + i, w + i);
  answ = cal(ansx, ansy);
  for (int i = 0; i < 5; i++) sa();  // 可调
  printf("%.3f %.3f\n", ansx, ansy);
}
最后修改:2020 年 08 月 04 日 01 : 22 PM