Peter Norvig on Simulated Annealing - Dictionary of Arguments
Norvig I 125
Simulated Annealing/Norvig/Russell: Problem: local search algorithms operate using a single current node (rather than multiple paths) and generally move only to neighbors of that node. Within a landscape they will not find the global maximum but will stay on a local maximum (or minimum). >Local minima; >Search algorithms.
Simulated annealing: In metallurgy, annealing is the process used to temper or harden metals and glass by heating them to a high temperature and then gradually cooling them, thus allowing the material to reach a low energy crystalline state.
Explanation of simulated annealing: imagine the task of getting a ping-pong ball into the deepest crevice in a bumpy surface. If we just let the ball roll, it will come to rest at a local minimum. If we shake the surface, we can bounce the ball out of the local minimum. The trick is to shake just hard enough to bounce the ball out of local minima but not hard enough to dislodge it from the global minimum. >Search algorithms.
Norvig I 155
Simulated annealing was first described by Kirkpatrick et al. (1983)(1), who borrowed directly from the Metropolis algorithm (which is used to simulate complex systems in physics (Metropolis et al., 1953)(2) and was supposedly invented at a Los Alamos dinner party). Simulated annealing is now a field in itself, with hundreds of papers published every year. See also >Optimization.
1. Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983). Optimization by simulated annealing. Science,
2. Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., and Teller, E. (1953). Equations of state calculations by fast computing machines. J. Chemical Physics, 21, 1087–1091._____________Explanation of symbols: Roman numerals indicate the source, arabic numerals indicate the page number. The corresponding books are indicated on the right hand side. ((s)…): Comment by the sender of the contribution. Translations: Dictionary of Arguments The note [Author1]Vs[Author2] or [Author]Vs[term] is an addition from the Dictionary of Arguments. If a German edition is specified, the page numbers refer to this edition.
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010