Simulated annealing

Simulated annealing (SA) is a probabilistic technique for approximating the global optimum of a given function. Specifically, it is a metaheuristic to approximate global optimization in a large search space. It is often used when the search space is discrete (e.g., all tours that visit a given set of cities). For problems where finding an approximate global optimum is more important than finding a precise local optimum in a fixed amount of time, simulated annealing may be preferable to alternatives such as gradient descent.

The name and inspiration come from annealing in metallurgy, a technique involving heating and controlled cooling of a material to increase the size of its crystals and reduce their defects. Both are attributes of the material that depend on its thermodynamic free energy. Heating and cooling the material affects both the temperature and the thermodynamic free energy. The simulation of annealing as an approach that reduces a minimization of a function of large number of variables to the statistical mechanics of equilibration (annealing) of the mathematically equivalent artificial multiatomic system was first formulated by Armen G. Khachaturyan, Svetlana V. Semenovskaya, Boris K. Vainshtein in 1979 and by Armen G. Khachaturyan, Svetlana V. Semenovskaya, Boris K. Vainshtein in 1981. These authors used computer simulation mimicking annealing and cooling of such a system to find its global minimum.

This notion of slow cooling implemented in the Simulated Annealing algorithm is interpreted as a slow decrease in the probability of accepting worse solutions as the solution space is explored (accepting worse solutions is a fundamental property of metaheuristics because it allows for a more extensive search for the optimal solution). The simulation can be performed either by a solution of kinetic equations for density functions (A. G. Khachaturyan, S.V. Semenovskaya, B.K.Vainstein in 1979 and A. Khachaturyan, S. Semenovsakaya, B. Vainshtein in 1981) or by using the stochastic sampling method which was independently described by Scott Kirkpatrick, C. Daniel Gelatt and Mario P. Vecchi in 1983, by Vlado Černý in 1985 and by Svetlana V. Semenovskaya, Karen A. Khachaturyan and Armen G. Khachaturyan in 1985. The method is an adaptation of the Metropolis–Hastings algorithm, a Monte Carlo method to generate sample states of a thermodynamic system, invented by M.N. Rosenbluth and published by N. Metropolis et al. in 1953.

...
Wikipedia