Definition: A technique to find a good solution to an optimization problem by trying random variations of the current solution. A worse variation is accepted as the new solution with a probability that decreases as the computation proceeds. The slower the cooling schedule, or rate of decrease, the more likely the algorithm is to find an optimal or near-optimal solution.
See also metaheuristic.
Note: This technique stems from thermal annealing which aims to obtain perfect crystallizations by a slow enough temperature reduction to give atoms the time to attain the lowest energy state.
This search tries to avoid local minima by jumping out of them early in the computation. Toward the end of the computation, when the temperature, or probability of accepting a worse solution, is nearly zero, this simply seeks the bottom of the local minimum. The chance of getting a good solution can be traded off with computation time by slowing down the cooling schedule. The slower the cooling, the higher the chance of finding the optimum solution, but the longer the run time. Thus effective use of this technique depends on finding a cooling schedule that gets good enough solutions without taking too much time.
After Daniel Thiel <email@example.com>, 31 January 2000.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 30 March 2009.
HTML page formatted Fri Mar 25 16:20:35 2011.
Cite this as:
Paul E. Black, "simulated annealing", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 30 March 2009. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/simulatedAnnealing.html