Simulated Annealing (SA) is a stochastic optimization method inspired by thermal annealing in materials science. In optimization terms, high temperature corresponds to exploratory search, while gradual cooling shifts the process toward exploitation of promising regions.
SA is especially useful when the objective landscape is rugged and full of local minima, as in combinatorial optimization tasks such as the Traveling Salesman Problem (TSP), scheduling, graph partitioning, and layout problems.
Core Setup
Let:
- \(D\): search space of feasible states.
- \(f: D \to \mathbb{R}\): objective function to minimize.
- \(x_t \in D\): current state at iteration \(t\).
- \(x' \in U(x_t)\): candidate state sampled from neighborhood \(U\).
- \(T_t > 0\): temperature at iteration \(t\).
The optimization goal is
\[ x^* = \arg\min_{x \in D} f(x). \]
Metropolis Acceptance Rule
For a candidate \(x'\), define
\[ \Delta E = f(x') - f(x_t). \]
- If \(\Delta E \le 0\), accept the move.
- If \(\Delta E > 0\), accept with probability
\[ P(\text{accept}) = \exp\left(-\frac{\Delta E}{T_t}\right). \]
This probabilistic acceptance of uphill moves allows SA to escape local minima early in the search. As \(T_t\) decreases, uphill moves become less likely and the process stabilizes.
Relation to Hill Climbing
Taking the limit \(T_t\to 0^+\) in the Metropolis rule recovers ordinary hill climbing: since \(\exp(-\Delta E/T_t)\to 0\) for every \(\Delta E>0\) as \(T_t\to 0^+\), any strictly worsening move is rejected with certainty, and only \(\Delta E\le 0\) moves are ever accepted. Hill climbing is therefore exactly the \(T=0\) special case of simulated annealing: a fully greedy walk that stops as soon as no neighbor improves on the current state, regardless of how far the global optimum might still be.
Running at a fixed nonzero temperature instead keeps a strictly positive acceptance probability for every worsening move, so the search can climb back out of the basin around a local minimum before it ever gets trapped there. Cooling \(T_t\) toward \(0\) over the course of a run interpolates between the two regimes: broad exploration that a pure hill climber could never perform early on, and a greedy, hill-climbing-like refinement once the temperature has collapsed.
Cooling Schedules
Typical schedules include:
- Exponential: \(T_t = T_0\alpha^t\), with \(\alpha \in (0,1)\).
- Linear: \(T_t = T_0 - \beta t\), with \(\beta > 0\).
- Logarithmic: \(T_t = \frac{T_0}{\log(1+t)}\).
In practice, exponential cooling is common because it is simple and easy to tune. Faster cooling converges quicker but increases risk of premature freezing.
Choosing the Initial Temperature
A cooling schedule only describes how \(T_t\) decreases once a starting value \(T_0\) is fixed; \(T_0\) itself still has to be chosen large enough that early moves are accepted almost regardless of \(\Delta E\), or the search behaves like hill climbing from the very first step. A practical way to calibrate it is to sample a handful of candidate moves from the initial state, measure their typical energy increase \(\overline{\Delta E}\), and pick \(T_0\) so that a move of this typical size is accepted with some target probability \(p_0\), commonly between \(0.7\) and \(0.9\):
\[ p_0 = \exp\left(-\frac{\overline{\Delta E}}{T_0}\right) \quad\Longrightarrow\quad T_0 = -\frac{\overline{\Delta E}}{\ln p_0}. \]
The interactive demonstration below sidesteps this calibration by fixing both a start and an end temperature directly and solving for the cooling factor \(\alpha\) that connects them over a chosen number of iterations \(N\). Setting \(T_N=T_0\alpha^N\) in the exponential schedule and solving for \(\alpha\) gives
\[ \alpha = \left(\frac{T_N}{T_0}\right)^{1/N}, \]
which is exactly the cooling factor computed from the demo's "Start Temp", "End Temp", and "Iterations" fields.
Neighborhood Design
Neighborhood quality is critical: if steps are too small, exploration is slow; if too large, the process behaves like random restart.
- Continuous domains: Gaussian or uniform perturbation.
- Combinatorial domains: swap, insertion, reversal, bit-flip.
- Graph domains: edge/vertex rewiring under feasibility constraints.
Algorithm
- Initialize \(x_0\), \(x_{best}=x_0\), \(T_0\), and iteration budget.
- Sample \(x' \in U(x_t)\), compute \(\Delta E\), apply Metropolis rule.
- Update best state if improved.
- Update temperature \(T_{t+1} = g(T_t, t)\).
- Stop at max iterations or minimum temperature.
TSP Demonstration
The interactive demo below applies SA to TSP. It starts from a random tour and repeatedly proposes local tour modifications, accepting them under the Metropolis criterion.
References
- Kirkpatrick83 Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by Simulated Annealing.
- Cerny85 Černý, V. (1985). Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm.