Heuristic — local search (stochastic)

▶ Open interactive explainer →

Simulated Annealing
Alias sa, simulated_annealing
Type Heuristic — local search (stochastic)
Complexity O(epochs · n)
Auto-seeds from shuffle (random tour)
Benchmarks published results ↓

Description

Probabilistic local search inspired by the annealing process in metallurgy. Each iteration proposes a random tour modification. Improvements are always accepted; worsenings are accepted with probability exp(−Δ/T), where T is the current “temperature”. Temperature decreases each step according to the cooling rate, so the algorithm transitions from broad exploration at high temperature to fine-tuned exploitation at low temperature.

Auto-expands to pipeline(shuffle, sa). The temperature schedule is calibrated for cold starts — seeding SA from a greedy NN tour constrains early exploration and typically worsens the final result. For a warm-started SA run use the classic preset (nn → 2opt → sa): the 2-opt stage removes edge crossings before SA fine-tunes the result.

procedure SimulatedAnnealing(cities, T_start, T_end, cooling):
    tour ← random_tour(cities)
    best ← tour
    T ← T_start
    while T > T_end:
        neighbour ← random_2opt_swap(tour)
        Δ ← length(neighbour) − length(tour)
        if Δ < 0 or random() < exp(−Δ / T):
            tour ← neighbour
        if length(tour) < length(best):
            best ← tour
        T ← T × cooling
    return best

Options

Both stopping rules are strict caps: the run ends at whichever is reached first. The temperature schedule normally finishes first, and --epochs is a safety bound.

Flag Description Default
--max_temperature Starting temperature 1000.0
--min_temperature Stopping temperature 0.001
--cooling_rate Fractional temperature drop per step 0.0001
--epochs Maximum iterations (safety cap) derived — see below

--epochs 0 means no epoch cap: the temperature schedule alone decides.

The default budget is sized above the cooling schedule, which is derived from the parameters as ceil(ln(max/min) / -ln(1 - cooling_rate)) — matching the loop’s T ← T × (1 − cooling_rate). At the defaults that schedule needs ~138,149 iterations; a slower rate needs far more (0.00001 requires ~1.38M). Setting --epochs below the schedule length is allowed but logged as a warning: the run then stops while the temperature is still high, which accepts nearly every move and looks like a poor solver rather than a truncated run.

Because the schedule is the primary stopping rule, a --min_temperature of 0 is rejected — the loop stops on temperature <= min_temperature and the f32 cooling step never actually reaches zero.

Usage

# auto-expands to pipeline(shuffle, sa)
teeline solve sa -i ./data/tsplib/berlin52.tsp
teeline solve sa -i ./data/tsplib/berlin52.tsp --verbose

# run SA from input city order (no shuffle)
teeline solve sa --no-seed -i ./data/tsplib/berlin52.tsp

# warm-start from a 2-opt-refined tour
teeline solve classic -i ./data/tsplib/berlin52.tsp

# custom temperature schedule
teeline solve sa -i ./data/tsplib/berlin52.tsp --cooling_rate=0.003 --max_temperature=500.0

References

  • AIMA, Section 4.1.2 — Simulated Annealing
  • Simulated annealing (Wikipedia)
  • Kirkpatrick, S., Gelatt, C. D. & Vecchi, M. P. (1983) — “Optimization by Simulated Annealing”, Science, 220(4598), 671–680. DOI: 10.1126/science.220.4598.671

Benchmarks

Loading published results…