How Simulated Annealing Mimics Physical Annealing to Find Global Optima

1 Simulated Annealing Algorithm

Simulated Annealing (SA) was first proposed by N. Metropolis et al. in 1953, and in 1983 S. Kirkpatrick et al. introduced the annealing concept to combinatorial optimization. It is a stochastic search algorithm based on a Monte‑Carlo iterative strategy, inspired by the similarity 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 characteristic, randomly explores the solution space to seek the global optimum of the objective function, allowing escape from local optima.

Unlike gradient‑based methods (e.g., hill climbing) and other deterministic search techniques that can become trapped in local minima, SA’s main advantage is its ability to avoid such traps. In fact, it has been proven that with sufficient randomness and a sufficiently slow cooling schedule, simulated annealing converges to a globally optimal solution.

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

2 Physical Annealing

Heating process: Increases particle motion, eliminating any prior non‑uniform states in the system.

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

Cooling process: Reduces particle thermal motion, leading to increased order; the system’s energy gradually 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). Here, represents the energy state, and is the product of the Boltzmann constant and the thermodynamic temperature.

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

From the expression we can infer:

The probability of a molecule staying in a lower‑energy state is higher than in a higher‑energy state at the same temperature.

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.” Mimicking solid 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 ensures that any improvement is always accepted, while worse solutions are accepted with a probability that lies in [0,1] and decreases as temperature drops.