Back to Study Material Artificial Intelligence

Simulated annealing

Simulated annealing is a probabilistic local search algorithm inspired by the physical annealing process in metallurgy. When metal is heated and then slowl...

Simulated annealing

Escaping Local Optima Through Controlled Randomness

Simulated annealing is a probabilistic local search algorithm inspired by the physical annealing process in metallurgy. When metal is heated and then slowly cooled, atoms settle into low-energy, highly ordered configurations. The algorithm mimics this by starting with high randomness and gradually reducing it, allowing occasional uphill moves early on to escape local optima.

The algorithm maintains a current state and a temperature parameter T, which starts high and decreases over time according to a cooling schedule. At each iteration, a random neighboring state is generated. If the neighbor is better than the current state, it is always accepted. If the neighbor is worse, it is accepted with probability exp(delta E / T), where delta E is the negative change in objective value. At high temperatures this probability is close to one, allowing wide exploration. As temperature drops, the probability of accepting worse solutions decreases, and the search gradually converges.

The cooling schedule is crucial. If temperature drops too quickly, the algorithm behaves like standard hill climbing and may still get stuck. If it drops too slowly, the algorithm wastes computational time exploring at random. Geometric cooling — multiplying T by a constant slightly less than one at each step — is the most common schedule.

A concrete example: the traveling salesman problem asks for the shortest route visiting a set of cities. A simulated annealing solution starts with a random tour and generates neighbors by swapping two cities' positions in the route. Early in the search, even longer tours are occasionally accepted, allowing the algorithm to explore broadly. As the temperature cools, only improvements are accepted, refining the tour toward a near-optimal solution.

Simulated annealing is widely used in chip design, scheduling, and protein structure prediction.

Exam tip: Know the acceptance probability formula and the effect of temperature. Be ready to explain why accepting worse solutions is beneficial — it prevents getting trapped in local optima.