Simulated Annealing

Simulated Annealing (SA) is a randomized metaheuristic that approximates a global optimum of an energy function E(s). Randomness means the same input can yield different outputs.

It shines when the state space is discrete and E has many local minima — classic example: the Travelling Salesman Problem (TSP).

This lesson follows CP-Algorithms — Simulated Annealing.

Related: Knapsack (exact DP vs heuristics), Minimum Enclosing Circle (randomized incremental).

Motivation (metallurgy → search)

Annealing heats a material then cools it so atoms settle into a low-energy arrangement. Early on, thermal noise lets the system cross energy barriers; later it freezes into a deep basin.

SA copies that:

Start at a random state with high temperature T.
Propose a neighbor; always take improvements; sometimes take worse moves (probability grows with T).
Cool T each step so escapes become rare and the search settles.

Track s_best across the whole run (the current s may wander).

Building blocks

Concept	TSP meaning
State `s`	A tour (permutation of cities)
Energy `E(s)`	Tour length (minimize)
Neighbor	Swap two cities (or 2-opt, …)
Temperature `T`	Willingness to accept worse tours
Decay `u < 1`	Cooling rate (`T ← T·u`)

For maximization, minimize −f and flip the sign when reporting.

Probability acceptance (Gibbs)

P(E, E_next, T) = True  if  U[0,1] ≤ exp(−(E_next − E) / T)
                  False otherwise

If E_next < E, then exp(…) ≥ 1 → always accept. If worse, accept with probability exp(−ΔE / T).

bool P(double E, double E_next, double T, mt19937& rng) {
    double prob = exp(-(E_next - E) / T);
    if (prob >= 1) return true;
    bernoulli_distribution d(prob);
    return d(rng);
}

Algorithm template

pair<double, state> simAnneal() {
    state s = state();       // random start
    state best = s;
    double T = 10000;        // initial temperature
    double u = 0.995;        // decay
    double E = s.E(), E_best = E;
    mt19937 rng(...);
    while (T > 1) {
        state nxt = s.next();
        double E_next = nxt.E();
        if (P(E, E_next, T, rng)) {
            s = nxt;
            E = E_next;
            if (E < E_best) { best = s; E_best = E; }
        }
        T *= u;
    }
    return {E_best, best};
}

Fill in state::next() (neighbor) and state::E() (energy).

Choosing `T` and `u`

Wide space / many basins → slow cool, e.g. u = 0.999 (or ≥ 0.998 if unsure).
Narrower space → u ≈ 0.99 may suffice.
Iteration count with exponential cooling: N ≈ ⌈ −log_u T ⌉ (from T_final ≈ 1), or pick N from TLE budget then T = u^{−N}.

Also common: time-based exit; other cooling schedules; change the base of the exponential (pow(e, −ΔE/T)) to sharpen/soften the preference for small ΔE.

🧪 Tiny TSP with SA (fixed seed)

Check: simulated annealing

Quiz