Metropolis algorithm with cooling schedule — escaping local minima to find near-optimal tours
TSP TOUR (click canvas to add city)
COST vs TEMPERATURE
TEMPERATURE SCHEDULE
Temperature T: –
SA Tour: –
Greedy Tour: –
Improvement: –
Iteration: 0
Simulated Annealing (Kirkpatrick, Gelatt & Vecchi 1983) mimics thermodynamic cooling: at high temperature, random "bad" moves are accepted with probability e^(-ΔE/T), escaping local minima. As T → 0, only improvements are accepted. For TSP, we use 2-opt swaps — reversing a segment of the tour. The Boltzmann acceptance criterion is the key: at high T, the algorithm explores broadly; as T decreases via T ← αT, it converges. Theoretical guarantee: converges to global optimum if T decreases slow enough (logarithmic schedule). In practice, geometric cooling (α ≈ 0.995) works remarkably well.