Simulated Annealing: Escaping Local Optima in AI Search

Simulated Annealing is a powerful probabilistic optimization algorithm used in artificial intelligence to find the global optimum in vast, complex search spaces. Unlike standard hill-climbing algorithms that easily get trapped in sub-optimal peaks known as local optima, Simulated Annealing intentionally accepts worse solutions early in the search process to explore the environment broadly. This article explores how the algorithm utilizes a decaying temperature parameter and the Metropolis acceptance criterion to transition smoothly from erratic exploration to precise exploitation, ensuring a high probability of finding the best overall solution.

The Local Optima Trap

In artificial intelligence search problems, algorithms attempt to find a state that maximizes or minimizes an objective function. Simple algorithms like Hill Climbing only move to neighboring states that offer immediate improvements. While fast, this greedy approach causes the algorithm to stop as soon as it reaches a peak where no immediate neighbor is better. In complex landscapes, this peak is usually a local optimum rather than the highest possible peak, the global optimum. To find the global optimum, an AI must occasionally make downhill moves to escape these traps.

The Role of the Temperature Parameter

Simulated Annealing borrows its name and mechanism from metallurgy, where heating and slowly cooling a metal alters its atomic structure to reduce defects. In the algorithm, the "Temperature" (\(T\)) is a numerical parameter that controls the search behavior.

At the beginning of the search, \(T\) is set very high. A high temperature forces the algorithm to act almost randomly, moving freely across the search space and ignoring the boundaries of local optima. As the algorithm runs, \(T\) is systematically reduced according to a "cooling schedule." This decay is usually geometric, achieved by multiplying the current temperature by a decay rate (such as \(0.99\)) at each step. As \(T\) approaches zero, the algorithm becomes increasingly reluctant to accept worse moves, eventually behaving like a standard hill-climbing algorithm to narrow in on the final peak.

The Metropolis Acceptance Criterion

The exact mechanism that connects the temperature to the movement of the algorithm is the Metropolis acceptance probability, derived from statistical mechanics.

At each step, the algorithm compares the current state with a randomly selected neighboring state by calculating the change in energy or objective value, denoted as \(\Delta E\).

  1. If the neighbor is better (\(\Delta E > 0\) for maximization): The algorithm always accepts the move and transitions to the new state.
  2. If the neighbor is worse (\(\Delta E < 0\) for maximization): The algorithm does not immediately reject it. Instead, it accepts the worse state with a probability \(P\) defined by the Metropolis formula:

\[P = e^{\frac{\Delta E}{T}}\]

In this equation, \(e\) is Euler's number, \(\Delta E\) is the negative change in value, and \(T\) is the current temperature.

How Temperature and Probability Interact

The brilliance of Simulated Annealing lies in how the Metropolis formula reacts to changes in both \(\Delta E\) and \(T\).

Impact of the Error Size (\(\Delta E\))

If a neighboring state is only slightly worse than the current state, \(\Delta E\) is a small negative number. This keeps the probability \(P\) relatively high, meaning the algorithm is willing to take small steps backward. If the neighbor is drastically worse, \(\Delta E\) is a large negative number, driving the probability \(P\) down and preventing the algorithm from jumping off massive cliffs unless the temperature is exceptionally high.

Impact of the Decaying Temperature (\(T\))

The decaying temperature dynamically shifts the output of the Metropolis formula over time:

  • High Temperature (Early Search): When \(T\) is very large, dividing \(\Delta E\) by \(T\) results in a fraction very close to zero. Since \(e^0 = 1\), the probability of accepting a worse move is nearly 100%. This allows the AI to easily climb out of local optima.
  • Medium Temperature (Mid Search): As \(T\) decays, the fraction \(\frac{\Delta E}{T}\) becomes a larger negative number. The algorithm now rejects drastically worse moves but still accepts slightly worse moves, allowing it to navigate out of shallow traps while settling into the most promising region of the search space.
  • Low Temperature (Late Search): As \(T\) approaches zero, dividing \(\Delta E\) by \(T\) approaches negative infinity. Since \(e^{-\infty} = 0\), the probability of accepting a worse move drops to zero. The algorithm locks into its current region and climbs directly to the highest local peak—which, due to the earlier exploration phase, is very likely the global optimum.

By mathematically binding the severity of a bad move to a decaying temperature variable, Simulated Annealing successfully balances the need for broad exploration with the necessity of targeted optimization.