## Simulated Annealingedited by Christian Blum, IRIDIA, and Andrea Roli, Università di Bologna ## Contents## About Simulated AnnealingSimulated Annealing (SA) is commonly said to be the oldest among the metaheuristics and surely one of the first algorithms that had an explicit strategy to avoid local minima. The origins of the algorithm are in statistical mechanics (Metropolis algorithm) and it was first presented as a search algorithm for CO problems in [Kirkpatrick et al. 1983] and [Cerny et al. 1985]. The fundamental idea is to allow moves resulting in solutions of worse quality than the current solution (uphill moves) in order to escape from local minima. The probability of doing such a move is decreased during the search.The algorithm starts by generating an initial solution (either randomly or heuristically constructed) and by initializing the so-called temperature parameter The temperature
Simulated annealing (given some assumptions on the cooling of the temperature, etc.) is proven to converge to the optimum solution of a problem. An easy implementation of the algorithm makes it very easy to adapt a local search method (e.g. best improvement local search) to a simulated annealing algorithm, usually rendering the local search with much better results. Disadvantages
Although it is proven to converge to the optimum, it converges in infinite time. Not only for this reason, but also since you have to cool down slowly, the algorithm is usually not faster than its comtemporaries ## Readings-
P.J.M. van Laarhoven and E.H.L. Aarts, 1987, Simulated Annealing: Theory and Applications, D.Reidel Publishing Company, Kluwer -
E.H.L Aarts and J.K. Lenstra, 1997, Local Search in Combinatorial Optimization, Wiley -
Cerny, V., "Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm", J. Opt. Theory Appl., 45, 1, 41-51, 1985 -
Kirkpatrick, S., C. D. Gelatt Jr., M. P. Vecchi, "Optimization by Simulated Annealing", Science, 220, 4598, 671-680, 1983. -
Metropolis,N., A. Rosenbluth, M. Rosenbluth, A. Teller, E. Teller, "Equation of State Calculations by Fast Computing Machines", J. Chem. Phys.,21, 6, 1087-1092, 1953.
## Links- Simulated Annealing Information
- More references to publications
| ||

Network Coordinator: Marco Dorigo e-mail: mdorigo@ulb.ac.be Web site responsibles: Christian Blum and Max Manfrin |