How Simulated Annealing Finds Global Optima: From Physics to Optimization

1 Simulated Annealing Algorithm

Simulated Annealing (SA) was first proposed by N. Metropolis et al. in 1953, and in 1983 S. Kirkpatrick and colleagues introduced the annealing concept to combinatorial optimization. It is a Monte‑Carlo iterative stochastic search algorithm that draws on the analogy between physical annealing of solids and combinatorial optimization problems.

Starting from a high initial temperature, SA gradually lowers the temperature parameter and, using a probabilistic jump mechanism, searches the solution space for the global optimum, allowing occasional moves to worse solutions to escape local minima.

Unlike gradient‑based methods (e.g., hill climbing) or other deterministic searches that can become trapped in local minima, SA’s main advantage is its ability to avoid such traps; with sufficient randomness and a sufficiently slow cooling schedule, SA is proven to converge to a globally optimal solution.

In modeling competitions, SA is primarily used for solving optimization problems such as the Traveling Salesman Problem (TSP), Max‑Cut, 0‑1 Knapsack, Graph Colouring, Scheduling, and other combinatorial challenges.

2 Physical Annealing

Heating process: Increases particle motion, eliminating any pre‑existing non‑uniform states.

Isothermal process: For a closed system exchanging heat with the environment at constant temperature, spontaneous changes always move toward lower free energy, reaching equilibrium when free energy is minimized.

Cooling process: Reduces particle thermal motion, leading to increased order; the system’s energy decreases, resulting in a low‑energy crystal structure.

3 Boltzmann Probability Distribution

In statistics, the Boltzmann distribution is expressed as ... (the formula is omitted in the source).

The ratio of probabilities for two states is called the Boltzmann factor.

At a given temperature, molecules are more likely to occupy lower‑energy states than higher‑energy ones.

Higher temperatures make the probability differences between energy states smaller; at sufficiently high temperature, all states have nearly equal probability.

As temperature decreases, the probability of the lowest‑energy state increases, approaching 1 as temperature approaches zero.

4 Acceptance Probability of Worse Solutions (Metropolis Criterion)

Also known as the state acceptance function, this is the origin of the name “simulated annealing.” As temperature (or iteration count) decreases, the system stabilizes and the probability of accepting worse solutions declines. The acceptance probability is given by the Metropolis formula, which guarantees that any improvement is always accepted, while worse moves are accepted with a probability that lies in [0,1] and decreases with lower temperature.