Simulated Annealing (SA)

A controlled randomness method: accept bad moves with probability e^−ΔC/T, and slowly cool down.

Intuition

The name comes from metallurgy: heat a metal up, then cool it slowly so atoms settle into a low-energy crystal lattice. The optimization analogy treats cost as energy and solutions as atomic configurations.

Compared with greedy local search

The algorithm

SIMULATED_ANNEALING(initial S0):
    S ← S0;  S_best ← S
    T ← T0                                  // 1: initial temperature
    while (stopping criterion not met):     // 2: outer loop
        for counter = 1..MaxIterations:     // 3: iterations per T
            S' ← perturb(S)                  // small random change
            ΔC ← C(S') − C(S)
            if ΔC ≤ 0:                       // better → always take
                S ← S'
                if C(S') < C(S_best): S_best ← S'
            else:                            // worse → take sometimes
                α ← random uniform(0,1)
                if α ≤ e−ΔC / T:
                    S ← S'
        T ← cool(T)                          // 4: temperature schedule
    return S_best

The 4 parameters you must set

1. Initial temperature T₀

Pick T₀ so that, at the start, bad moves are accepted with probability ≈ 0.9. Procedure:

Set Pr = 0.9, start with some T.
Try 1000 perturbations. Count the fraction of bad moves that get accepted.
If fraction < 0.9: T ← T * 2; retry.
Repeat until fraction ≥ 0.9.

This calibrates T to the scale of cost differences in your problem.

2. Number of iterations per temperature

Let N = number of variables. Try N, N², or N³; pick the smallest value where increasing it doesn't improve the answer noticeably. More iterations = more exploration at each temperature.

3. Cooling schedule

Most common: geometric cooling with α close to 1.

T_new = 0.9 * T_old    // slow cooling — good
T_new = 0.5 * T_old    // fast cooling — converges to local opt fast

4. Stopping criterion

Stop when T < 0.0001 — at that point, e^−ΔC/T ≈ 0 for any positive ΔC, so SA behaves like a pure greedy.

Interactive demo (TSP)

Watch SA progressively shrink the tour. Notice how the temperature plot drives bad-move acceptance.

Exam tips