Skip to content

Simulated Annealing

Introduction

Simulated annealing is a randomized algorithm. It is often used to solve problems where the number of possible solutions is extremely large (or even infinite) and the objective function is not unimodal.

Explanation

Based on the process of Hill Climbing, we observe that hill climbing directly discards a non-optimal solution near the current optimal solution. In many cases, we need to accept such non-optimal solutions to escape local optima, which is the idea behind simulated annealing.

What is annealing? (Excerpt from Baidu Baike)

Annealing is a metal heat treatment process that involves slowly heating the metal to a certain temperature, holding it for a sufficient time, and then cooling it at an appropriate rate. The purpose is to reduce hardness, improve machinability; eliminate residual stress, stabilize dimensions, reduce deformation and cracking tendency; refine grains, adjust microstructure, and eliminate structural defects. Precisely, annealing is a heat treatment process for materials, including metallic and non-metallic materials. Moreover, the annealing purposes for new materials differ from those of traditional metal annealing.

Since the annealing process introduces more randomness, the probability of obtaining the optimal solution increases significantly. Therefore, we can simulate this process by treating the objective function as an energy function.

Process

In one sentence: If the new state yields a better solution, update the answer; otherwise, accept the new state with a certain probability.

Let the current temperature be \(T\), and the energy (value) difference between the new state \(S'\) and the known state \(S\) (obtained randomly from the known state) be \(\Delta E\) (\(\Delta E \geqslant 0\)). Then the probability of state transition (updating the optimal solution) is:

\[ P(\Delta E)= \begin{cases} 1, & S' \text{ is better than } S,\\ \mathrm{e}^\frac{-\Delta E}{T}, & \text{otherwise}. \end{cases} \]

Note: Sometimes, to improve the quality of the solution, after simulated annealing ends, we perform multiple random state explorations near the obtained solution at the current temperature, attempting to find a better solution (the process is similar to simulated annealing).

How to Anneal (Cool Down)

Simulated annealing involves three parameters: initial temperature \(T_0\), cooling coefficient \(d\), and termination temperature \(T_k\). Here, \(T_0\) is a relatively large number, \(d\) is a number very close to but less than \(1\), and \(T_k\) is a positive number close to \(0\).

First, set the temperature \(T = T_0\), then perform a transition attempt according to the steps above, and then update \(T = d \cdot T\). When \(T < T_k\), the simulated annealing process ends, and the current optimal solution is the final optimal solution.

Note: To obtain a more precise solution, we usually do not directly take the current solution as the answer. Instead, we maintain the best value among all solutions encountered during the annealing process.

Refer to an image from Simulated annealing - Wikipedia (as the temperature decreases, the jumps become less random, and the optimal solution becomes more stable).

Implementation

The following code uses 「BZOJ 3680」吊打 XXX (finding the weighted Fermat point of \(n\) points) as an example.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>

constexpr int N = 10005;
int n, x[N], y[N], w[N];
double ansx, ansy, dis;

double Rand() { return (double)rand() / RAND_MAX; }

double calc(double xx, double yy) {
  double res = 0;
  for (int i = 1; i <= n; ++i) {
    double dx = x[i] - xx, dy = y[i] - yy;
    res += sqrt(dx * dx + dy * dy) * w[i];
  }
  if (res < dis) dis = res, ansx = xx, ansy = yy;
  return res;
}

void simulateAnneal() {
  double t = 100000;
  double nowx = ansx, nowy = ansy;
  while (t > 0.001) {
    double nxtx = nowx + t * (Rand() * 2 - 1);
    double nxty = nowy + t * (Rand() * 2 - 1);
    double delta = calc(nxtx, nxty) - calc(nowx, nowy);
    if (exp(-delta / t) > Rand()) nowx = nxtx, nowy = nxty;
    t *= 0.97;
  }
  for (int i = 1; i <= 1000; ++i) {
    double nxtx = ansx + t * (Rand() * 2 - 1);
    double nxty = ansy + t * (Rand() * 2 - 1);
    calc(nxtx, nxty);
  }
}

int main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);
  srand(0);  // Note: In practical use, a fixed random seed should not be used.
  std::cin >> n;
  for (int i = 1; i <= n; ++i) {
    std::cin >> x[i] >> y[i] >> w[i];
    ansx += x[i], ansy += y[i];
  }
  ansx /= n, ansy /= n, dis = calc(ansx, ansy);
  simulateAnneal();
  std::cout << std::fixed << std::setprecision(3) << ansx << ' ' << ansy
            << '\n';
  return 0;
}

Some Techniques

Block Simulated Annealing

Sometimes the objective function has many peaks, making it difficult for simulated annealing to find the optimal solution.

In such cases, the entire value domain can be divided into several segments. Run simulated annealing on each segment, and then take the best solution among them.

Time Limiting

There is a clock() function that returns the program's running time.

You can replace simulateAnneal(); in the main program with while ((double)clock()/CLOCKS_PER_SEC < MAX_TIME) simulateAnneal();. This will keep running simulated annealing until the time is about to exceed the limit.

Here, MAX_TIME is a user-defined number slightly smaller than the time limit (in seconds).

Exercises

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用