Advertisement

The Simulated Annealing Algorithm

  • Carl Sechen
Chapter
  • 81 Downloads
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.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    M. Garey and D. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” (1979).zbMATHGoogle Scholar
  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).zbMATHGoogle Scholar
  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).zbMATHGoogle Scholar
  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

Copyright information

© Kluwer Academic Publishers, Boston 1988

Authors and Affiliations

  • Carl Sechen
    • 1
  1. 1.Yale UniversityUSA

Personalised recommendations