Skip to main content
SpringerLink
Log in

Simulated Annealing: A Pedestrian Review of the Theory and Some Applications

  • Conference paper
Pattern Recognition Theory and Applications

Part of the book series: NATO ASI Series ((NATO ASI F,volume 30))

Abstract

Simulated annealing is a combinatorial optimization method based on randomization techniques. The method originates from the analogy between the annealing of solids, as described by the theory of statistical physics, and the optimization of large combinatorial problems. Here we review the basic theory of simulated annealing and recite a number of applications of the method. The theoretical review includes concepts of the theory of homogeneous and inhomogeneous Markov chains, an analysis of the asymptotic convergence of the algorithm, and a discussion of the finite-time behaviour. The list of applications includes combinatorial optimization problems related to VLSI design, image processing, code design and artificial intelligence.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Aarts, E.H.L and P.J.M. van Laarhoven, Statistical Cooling: A General Approach to Combinatorial Optimization Problems, Philips Journal of Research, 40 (1985) 193–226.

    MathSciNet  Google Scholar 

  2. Aarts, E.H.L and P.J.M. van Laarhoven, A New Polynomial Time Cooling Schedule, Proc. Int. Conf. on Computer Aided Design, Santa Clara, November 1985, pp. 206–208.

    Google Scholar 

  3. Aarts, E.H.L, F.M.J, de Bont, J.H.A. Habers and P.J.M. van Laarhoven, A Parallel Statistical Cooling Algorithm, Proc. Symposium on Theoretical Aspects of Computer Science, 1986, Springer Lecture Notes in Computer Science 210 (1986) 87–97.

    Google Scholar 

  4. Ackley, D.H., G.E. Hinton and T.J. Sejnowski, A Learning Algorithm for Boltzmann Machines, Cognitive Science, 9 (1985) 147–169.

    Article  Google Scholar 

  5. Anily, S. and A. Federgruen, Probabilistic Analysis of Simulated Annealing Methods, preprint, 1985.

    Google Scholar 

  6. Aragon C.R., D.S. Johnson, L.A. McGeoch and C. Schevon, Optimization by Simulated Annealing: an Experimental Evaluation, working paper, 1984.

    Google Scholar 

  7. Beenker G.F.M., T.A.C.M. Claasen and P.W.C. Hermens, Binary Sequences with Maximally Flat Amplitude Spectrum, Philips J. of Research, 40 (1985) 289–304.

    MATH  Google Scholar 

  8. Bonomi, E. and J.-L. Lutton, The N-city Travelling Salesman Problem: Statistical Mechanics and the Metropolis Algorithm, SIAM Rev., 26 (1984) 551–568.

    Article  MathSciNet  MATH  Google Scholar 

  9. Carnevalli, P., L. Coletti and S. Paternello, Image Processing by Simulated Annealing, IBM J. Res. Develop., 29(1985) 569–579.

    Article  Google Scholar 

  10. Catthoor, F., H. DeMan and J. Vanderwalle, SAILPLANE: A Simulated Annealing based CAD-tool for the Analysis of Limit-Cycle Behaviour, Proc. IEEE Int. Conf. on Computer Design, Port Chester, October 1985, pp. 244–247.

    Google Scholar 

  11. Cerny, V., Thermodynamics! Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm, J. Opt Theory Appl, 45 (1985) 41–51.

    Article  MathSciNet  MATH  Google Scholar 

  12. Feller, W., An Introduction to Probability Theory and Applications, vol i, (Wiley, New York, 1950).

    Google Scholar 

  13. Fleisher, H., J. Giraldi, D.B. Martin, R.L. Phoenix and M.A. Tavel, Simulated Annealing as a Tool for Logic Optimization in a CAD Environment, Proc. ICCAD, Santa Clara, November 1985, pp. 203–205.

    Google Scholar 

  14. Garey, M.R. and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, (W.H. Freeman and Co., San Francisco, 1979).

    MATH  Google Scholar 

  15. Geman, S. and D. Geman, Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images, IEEE Proc. Pattern Analysis and Machine Intelligence, PAMI-6 (1984) 721–741.

    Article  Google Scholar 

  16. Gidas, B., Nonstationary Markov Chains and Convergence of the Annealing Algorithm, J. Statis. Phys 39 (1985) 73–131.

    Article  MathSciNet  MATH  Google Scholar 

  17. Hajek, B., Cooling Schedules for Optimal Annealing, preprint, 1985.

    Google Scholar 

  18. Hajek, B. A Tutorial Survey of Theory and Applications of Simulated Annealing, Proc. 24th Conf. on Decision and Control, Ft. Lauderdale, December 1985, pp. 755–760.

    Google Scholar 

  19. Hemachandra, L.A. and V.K. Wei, Simulated Annealing and Error Correcting Codes, preprint, 1984.

    Google Scholar 

  20. Holley, R, Rapid Convergence to Equilibrium in One Dimensional Stochastic Ising Models, Annals of Probability, 13 (1985) 72–89.

    Article  MathSciNet  MATH  Google Scholar 

  21. Isaacson, D. and R. Madsen, Markov Chains, (Wiley, New York, 1976).

    Google Scholar 

  22. Jepsen, D.W. and C.D. Gelatt Jr., Macro Placement by Monte Carlo Annealing, Proc. Int. Conf. Computer Design, Port Chester, November 1983, pp. 495–498.

    Google Scholar 

  23. Kirkpatrick, S., C.D. Gelatt Jr. and M.P. Vecchi, Optimization by Simulated Annealing, Science, 220 (1983) 671–680.

    Article  MathSciNet  MATH  Google Scholar 

  24. Kirkpatrick, S. and G. Toulouse, Configuration Space Analysis of Travelling Salesman Problems, J. Physique, 46 (1985) 1277–1292.

    Article  MathSciNet  Google Scholar 

  25. Laarhoven, P.J.M. van and E.H.L. Aarts, Theory and Applications of Simulated Annealing: An Overview, submitted for publication in Acta Applicandae Mathematicae, 1986.

    Google Scholar 

  26. Lawler, E.L., J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, The Traveling Salesman Problem, (Wiley, Chichester, 1985).

    MATH  Google Scholar 

  27. Leong, H.W., D.F. Wong and C.L. Liu, A Simulated-Annealing Channel Router, Proc. ICC AD, Santa Clara, November 1985, pp. 226–229.

    Google Scholar 

  28. Ligthart, M.M., E.H.L. Aarts and F.P.M. Beenker, A Design-fortestability of PLA’s using Statistical Cooling, to appear in Proc. 23rd Des. Automation Conf., Las Vegas, June 1986.

    Google Scholar 

  29. Lundy, M. and A. Mees, Convergence of an Annealing Algorithm, Math. Prog., 34 (1986) 111–124.

    Article  MathSciNet  MATH  Google Scholar 

  30. M. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller and E. Teller, Equation of State Calculations by Fast Computing Machines, J. Chem. Phys. 21 (1953) 1087–1092.

    Article  Google Scholar 

  31. Mezard, M. and G. Parisi, Replicas and Optimization, J. Physique Lett., 46 (1985) L-771-L-778.

    Google Scholar 

  32. Mitra, D., Romeo, F. and A.L. Sangiovanni-Vincentelli, Convergence and Finite-Time Behavior of Simulated Annealing, Proc. 24th Conf. on Decision and Control, Ft. Lauderdale, December 1985, pp. 761–767.

    Google Scholar 

  33. Moore, T.P. and A.J. de Geus, Simulated Annealing Controlled by a Rule-Based Expert System, Proc. Int. Conf. on Computer Aided Design, Santa Clara, November 1985, pp. 200–202.

    Google Scholar 

  34. Otten, R.H.J.M. and L.P.P.P. van Ginneken, Floorplan Design using Simulated Annealing, Proc. Int. Conf. on Computer Aided Design, Santa Clara, November 1984,pp. 96–98.

    Google Scholar 

  35. Papadimitriou, C.H. and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, (Prentice Hall, New York, 1982).

    Google Scholar 

  36. Ripley, B.D., Statistics, Images and Pattern Recognition, preprint 1985.

    Google Scholar 

  37. Romeo, F. and A.L. Sangiovanni-Vincentelli, Probabilistic Hill Climbing Algorithms: Properties and Applications, Proc. 1985 Chapel Hill Conf. on VLSI, May 1985 pp. 393–417.

    Google Scholar 

  38. Rowen, C. and J.L. Hennessy, Logic Minimization, Placement and Routing in SWAMI, Proc. 1985 Custom IC Conf., Portland, May 1985.

    Google Scholar 

  39. Sechen, C. and A.L. Sangiovanni-Vincentelli, Timber Wolf3.2: A New Standard Cell Placement and Global Routing Package, to appear in Proc. 23rd Des. Automation Conf., Las Vegas, June 1986.

    Google Scholar 

  40. Seneta, E., Non-negative Matrices and Markov Chains, (Springer Verlag, New York, 2nd ed., 1981).

    MATH  Google Scholar 

  41. Smith, W.E., H.H. Barrett and R.G. Paxman, Reconstruction of Objects from Coded Images by Simulated Annealing, Optics Letters, 8 (1983) 199–201.

    Article  Google Scholar 

  42. Smith, W.E., R.G. Paxman and H.H. Barrett, Application of Simulated Annealing to Coded-aperture Design and Tomographic Reconstruction, IEEE Trans. Nuclear Science, NS-32 (1985) 758–761.

    Article  Google Scholar 

  43. Sontag, E.D. and H.J. Sussmann, Image Restoration and Segmentation using the Annealing Algorithm, Proc. 24 th Conf. on Decision and Control, Ft. Lauderdale, December 1985, pp. 768–773.

    Google Scholar 

  44. Vecchi, M.P. and S. Kirkpatrick, Global Wiring by Simulated Annealing, IEEE Trans, on Computer-Aided Design, 2 (1983) 215–222.

    Article  Google Scholar 

  45. White, S.R., Concepts of Scale in Simulated Annealing, Proc. ICCD, Port Chester, November 1984, pp. 646–651.

    Google Scholar 

  46. Wolberg, G. and T. Pavlidis, Restoration of Binary Images using Stochastic Relaxation with Annealing, Pattern Recognition Letters, 3 (1985) 375–388.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Philips Research Laboratories, P.O. Box 80000, 5600 JA, Eindhoven, the Netherlands

    Emile H. L. Aarts & Peter J. M. van Laarhoven

Authors
  1. Emile H. L. Aarts
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Peter J. M. van Laarhoven
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Philips Research Laboratory, Avenue Em. Van Becelaere 2, Box 8, B-1170, Brussels, Belgium

    Pierre A. Devijver

  2. Department of Electronic and Electrical Engineering, University of Surrey, GU2 5XH, Guildford, UK

    Josef Kittler

Rights and permissions

Reprints and permissions

Copyright information

© 1987 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Aarts, E.H.L., van Laarhoven, P.J.M. (1987). Simulated Annealing: A Pedestrian Review of the Theory and Some Applications. In: Devijver, P.A., Kittler, J. (eds) Pattern Recognition Theory and Applications. NATO ASI Series, vol 30. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-83069-3_15

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-83069-3_15

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-83071-6

  • Online ISBN: 978-3-642-83069-3

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation