Some real-world problems may prove too complex for exact solutions to be obtained. Methods based on successive approximations, whether deterministic or random, often yield usable and relatively reliable results. Among these methods, the curiously named "simulated annealing" offers several advantages, particularly for finding global optima.
Escaping local traps
-------------------------
Complex functions of several variables may have many local optima. When using an approximate computational method, how can we avoid becoming trapped in one of these local minima and "missing" the true optimum we seek? The method developed by three IBM engineers—Scott Kirkpatrick (born 1941), Charles Daniel Gelatt Jr. (born 1947), and Mario Pietro Vecchi (born 1948)—during their research on integrated circuits was published in Science in 1983. It draws directly on methods used in metallurgy while implementing an existing algorithmic procedure published by Nicholas Metropolis in 1949. Metropolis improved this algorithm in 1953, before Canadian statistician Wilfred Keith Hastings (1930–2016) generalized it in 1970.
In metallurgy, annealing a metal object is a heat-treatment process in which the object is first held at a high temperature and then cooled under controlled conditions, thereby modifying the metal's properties. The process alternates cycles of reheating (or annealing—annealing in English, from to anneal, meaning “to heat-treat by annealing”) and slow cooling. When the metal is heated, the energy supplied to it allows its constituent molecules to break some of their bonds, giving the resulting atoms a degree of mobility. As the metal cools, this mobility decreases and new bonds form.
Empirical evidence shows that slow cooling generally produces more stable structures corresponding to a global energy minimum. The resulting metal is more pliable and flexible, with few irregularities.
