# The Simulated Annealing Algorithm

• Carl Sechen
Chapter
Part of the The Kluwer International Series in Engineering and Computer Science book series (SECS, volume 54)

## Abstract

Most placement and global routing problems belong to the class of NP-complete problems.1 For problems in this class, there is no known exact algorithm whose worst-case time complexity is bounded by a polynomial in the size of the input. Consequently, heuristic algorithms are used to find solutions to these problems. These algorithms explore a discrete space of admissible configurations S in a deterministic fashion. Starting from an initial configuration i 0S, a sequence of configurations are explored until a satisfactory one is found. The algorithm is specified by the rules according to which configurations are generated and accepted. Often the search terminates in a local minimum, at a state ĵS such that c(j) ≥ c(ĵ) for all jŜ(ĵ) where c( ) is the cost function defined on the configuration space and where Ŝ(ĵ) represents the states of S reachable from ĵ. The state ĵ is a local minimum if there exists a state $$\bar{j} \in S$$ such that$$c\left( {\bar{j}} \right) < c\left( {\hat{j}} \right)$$. In many cases, the quality of the local minimum states, or configurations, are quite inferior in comparison to the global minimum state. Heuristic algorithms often end at these local minimum states because their behavior is essentially greedy, that is, they only accept new states which maximally reduce the cost.

## Keywords

Cost Function Simulated Annealing Combinatorial Optimization Problem Simulated Annealing Algorithm Acceptance Function
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

## References

1. 1.
M. Garey and D. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” (1979).
2. 1.
J. T. Schwartz, “Fast Probabilistic Algorithms for Verification of Polynomial Identities,” (1980).Google Scholar
3. 2.
S. Kirkpatrick, C. Gelatt, and M. Vecchi, “Optimization by Simulated Annealing,” (1983).Google Scholar
4. 3.
S. Kirkpatrick, C. Gelatt, and M. Vecchi, “Optimization by Simulated Annealing,” (1983).Google Scholar
5. 1.
N. Metropolis, A. Rosenbluth, M. Rosenbluth, and A. Teller, (1953).Google Scholar
6. 2.
K. Binder, “Monte Carlo Methods in Statistical Physics,” (1978).Google Scholar
7. 3.
S. Kirkpatrick, C. Gelatt, and M. Vecchi, “Optimization by Simulated Annealing,” (1983).Google Scholar
8. 1.
F. Romeo and A. Sangiovanni-Vincentelli, “Probabilistic Hill Climbing Algorithms: Properties and Applications,”(1985).Google Scholar
9. 1.
S. Kirkpatrick, C. Gelatt, and M. Vecchi, “Optimization by Simulated Annealing,” (1983).Google Scholar
10. 1.
S. Kirkpatrick, C. Gelatt, and M Vecchi, “Optimization by Simulated Annealing,” (1983).Google Scholar
11. 2.
S. Karlin, “A First Course in Stochastic Processes,” (1973).Google Scholar
12. 3.
W. Feller, “An Introduction to Probability Theory and Applications,” (1970).Google Scholar
13. 4.
D. Freedman, “Markov Chains,” (1971).
14. 5.
D. Mitra, R. Romeo, and A. Sangiovaimi-Vincentelli, “Convergence and Finite-Time Behavior of Simulated Annealing,” (1985).Google Scholar
15. 1.
F. Romeo and A. Sangiovanni-Vincentelli, “Probabilistic Hill Climbing Algorithms: Properties and Applications,” (1985).Google Scholar
16. 2.
M. Lundy and A. Mees, “Convergence of the Annealing Algorithm,” (1984).Google Scholar
17. 1.
D. Geman and S. Geman, “Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images,”(1984).Google Scholar
18. 2.
B. Gidas, “Non-Stationary Markov Chains and Convergence of the Annealing Algorithm,” (1985).Google Scholar
19. 3.
B. Hajek, “Cooling Schedules for Optimal Annealing,” (1985).Google Scholar
20. 4.
D. Isaacson and R. Madsen, “Uarkov Chains: Theory and Applications,” (1976).Google Scholar
21. 5.
M. Iosifescu, “Finite Markov Processes and their Applications,” (1980).
22. 6.
E. Senata, “Non-Negative Matrices and Markov Chains,” (1980).Google Scholar
23. 7.
D. Mitra, F. Romeo, and A. Sangiovanni-Vincentelli, “Convergence and Finite-Time Behavior of Simulated Annealing,” (1985). gGoogle Scholar
24. 8.
D. Mitra, F. Romeo, and A. Sangiovanni-Vincentelli, “Convergence and Finite-Time Behavior of Simulated Annealing,” (1985).Google Scholar
25. 1.
M. Huang, F. Romeo, and A. Sangiovanni-Vincentelli, “An Efficient General Cooling Schedule for Simulated Annealing,” (1986).Google Scholar
26. 2.
D. Oeman and S. Geman, “Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images,” (1984).Google Scholar
27. 3.
J. Lam and J. M. Delosme, “Logic Minimization Using Simulated Annealing,” (1986).Google Scholar
28. 4.
E. Aarts and P. Laarhoven, “Statistical Cooling: A General Approach to Combinatorial Optimization Problems,” (1985).Google Scholar
29. 5.
R. Otten and L. Ginneken, “Floorplan Desing Using Simulated Annealing,” (1984).Google Scholar
30. 6.
R. Otten and L. Ginneken, “Floorplan Desing Using Simulated Annealing,” (1984).Google Scholar
31. 7.
E. Aarts and P. Laarhoven, “Statistical Cooling: A General Approach to Combinatorial Optimization Problems,” (1985).Google Scholar
32. 8.
M. Huang, F. Romeo, and A. Sangiovanni-Vincentelli, “An Efficient General Cooling Schedule for Simulated Annealing,” (1986).Google Scholar
33. 9.
J. Lam and J. M Delosme, “Logic Minimization Using Simulated Annealing,” (1986).Google Scholar
34. 1.
OM. Huang, F. Romeo, and A. Sangiovanni-Vincentelli, “An Efficient General Cooling Schedule for Simulated Annealing,” (1986).Google Scholar
35. 1.
S. White, “Concepts of Scale in Simulated Annealing” (1984).Google Scholar
36. 2.
E. Aarts and P. Laarhoven, “Statistical Cooling: A General Approach to Combinatorial Optimization Problems,” (1985).Google Scholar
37. 3.
R. Otten and L. Ginneken, “Floorplan Desing Using Simulated Annealing,” (1984).Google Scholar
38. 4.
M. Huang, F. Romeo, and A. Sangiovanni-Vincentelli, “An Efficient General Cooling Schedule for Simulated Annealing,” (1986).Google Scholar
39. 5.
F. Reif, “Statistical and Thermal Physics,” (1965).Google Scholar
40. 1.
W. Feller, “An Introduction to Probability Theory and Applications,” (1970).Google Scholar
41. 1.
S. Kirkpatrick, C. Gelatt, and M. Vecchi, “Optimization by Simulated Annealing,” (1983).Google Scholar
42. 1.
S. Kirkpatrick, C. Oelatt, and M. Vecchi, “Optimization by Simulated Annealing,” (1983).Google Scholar
43. 1.
D. Mitra, F. Romeo, and A. Sangiovanni-Vincentelli, “Convergence and Finite-Time Behavior of Simulated Annealing,” (1985).Google Scholar
44. 1.
J. Deutsch, Private Communication, (1984).Google Scholar