(algorithm)
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 <mouttaqu@enitiaa-nantes.fr>, 31 January 2000.
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 30 March 2009.
HTML page formatted Mon Feb 2 13:10:40 2015.
Cite this as:
Paul E. Black, "simulated annealing", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 30 March 2009. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/simulatedAnnealing.html