simulated annealing

simulated annealing
Name	Simulated Annealing
Class	Metaheuristic
Year	1983
Authors	Scott Kirkpatrick, C. Daniel Gelatt, Mario P. Vecchi
Inspired by	Annealing (metallurgy)
Related to	Monte Carlo method, Local search (optimization)

simulated annealing. It is a probabilistic technique for approximating the global optimum of a given function, inspired by the physical process of annealing in metallurgy. The method is a metaheuristic used to address complex combinatorial optimization problems where finding an exact solution is computationally infeasible. By allowing occasional moves to worse states, it can escape local minima and converge toward a globally optimal solution.

Overview

The fundamental analogy draws from the physical process of annealing (metallurgy), where a material is heated and then slowly cooled to reduce defects and minimize its energy. In optimization, this corresponds to exploring a solution space, with the "temperature" parameter controlling the probability of accepting inferior solutions. The technique is particularly valuable for problems like the travelling salesman problem and integrated circuit design, where traditional gradient descent methods often fail. Its development was a significant milestone in the field of applied mathematics and operations research, bridging concepts from statistical mechanics and computer science.

Algorithm

The procedure begins by generating an initial solution and setting a high starting temperature. At each iteration, a neighboring solution is generated, often through a small perturbation defined by a Markov chain process. The change in the objective function, or "energy," is calculated. If the new solution is better, it is always accepted. If it is worse, it may be accepted with a probability determined by the Boltzmann distribution, a concept central to statistical thermodynamics. This acceptance probability depends on the current temperature, which is gradually reduced according to a predefined cooling schedule. The algorithm typically terminates when the temperature reaches a near-zero value or after a set number of iterations, as implemented in systems like IBM's CPLEX.

Convergence properties

Under certain conditions, simulated annealing can be proven to converge to a global optimum with probability one. This theoretical guarantee relies on a sufficiently slow cooling schedule, such as the logarithmic cooling schedule proposed in the seminal work by Stuart Geman and Donald Geman on Gibbs sampling. The convergence analysis often uses tools from the theory of Markov processes and ergodicity. However, in practical applications with finite time, the algorithm is a heuristic, and its performance is sensitive to parameter tuning, including the initial temperature and the neighborhood structure. Research from institutions like AT&T Bell Laboratories has extensively studied these time complexity trade-offs.

Variations and extensions

Many adaptations have been developed to improve performance or tailor the method to specific domains. Adaptive simulated annealing dynamically adjusts parameters during the search. Quantum annealing, utilized by companies like D-Wave Systems, draws inspiration from quantum mechanics rather than classical thermodynamics. Parallel tempering, also known as replica exchange, runs multiple copies at different temperatures to enhance sampling. Other hybrids combine it with techniques like genetic algorithms or tabu search, pioneered by researchers such as Fred Glover. These extensions are frequently applied in fields like computational chemistry and protein folding simulations.

Applications

The versatility of the technique has led to its adoption across numerous scientific and engineering disciplines. In VLSI design, it is used for floorplanning and placement, a problem tackled by early pioneers at IBM. It optimizes scheduling and routing in logistics, benefiting companies like FedEx and UPS. In machine learning, it aids in training neural networks and optimizing hyperparameters. Other notable uses include image processing for NASA missions, financial modeling for the New York Stock Exchange, and designing aerodynamic structures in collaboration with Boeing and Airbus. The International Mathematical Olympiad has even featured problems solvable with this approach.

History

The concept was formally introduced in 1983 by Scott Kirkpatrick, C. Daniel Gelatt, and Mario P. Vecchi in a seminal paper published in Science (journal), while they were working at IBM Thomas J. Watson Research Center. Its inspiration came from the Metropolis–Hastings algorithm, a Monte Carlo method developed earlier by Nicholas Metropolis and colleagues at Los Alamos National Laboratory. Independent work on similar ideas was conducted by Vladimir Černý in 1985. The method gained rapid popularity in the 1980s, becoming a cornerstone of computational optimization, and its principles continue to influence modern developments in artificial intelligence and quantum computing.

Category:Optimization algorithms and methods Category:Metaheuristics Category:Stochastic processes