Simulated annealing: past, present, and future

ABSTRACT

This paper provides an overview of the simulated annealing algorithm and describes its historical foundation in thermodynamics as well as the genesis and evolution for solving difficult optimization problems. An example illustrating its application to graph problems is provided as well as a look at ongoing, state-of-the-art research using SA.

REFERENCES

• 1: Emile Aarts , Jan Korst, Simulated annealing and Boltzmann machines: a stochastic approach to combinatorial optimization and neural computing, John Wiley & Sons, Inc., New York, NY, 1989
• 2: Azencott, R. ed. 1992. Simulated annealing: parallelizalion techniques, New York, N.Y., John Wiley & Sons, Inc.
• 3: Ihor O Bohachevsky , Mark E Johnson , Myron L Stein, Generalized simulated annealing for function optimization, Technometrics, v.28 n.3, p.209-217, August 1986 [doi>10.2307/1269076]
• 4: Bondy, J.A. and U.S.R. Murty. 1976. Graph theory wzth applications, New York, N.Y. North-Holland, Elsevier Science Publishing Co., Inc.
• 5: Bonomi, E. and J. Lutton, 1984. The n-city travelling salesman problem: statistical mechanics and the Metropolis algorithm, SIAM Review, VoI. 26, No.4. pp. 551-568.
• 6: Kah Mun Cheh , Jeffrey B. Goldberg , Ronald G. Askin, A note on the effect of neighborhood structure in simulated annealing, Computers and Operations Research, v.18 n.6, p.537-548, Sept. 1991 [doi>10.1016/0305-0548(91)90059-Z]
• 7: C~rny, V. 1985. A thermodynamical approach to the travelling salesman problem: an efficient simulation algorithm. Journal of Optimzzatzon Theory and Application, Vol. 45, pp. 41-55.
• 8: Kathryn A. Dowsland, Simulated annealing, Modern heuristic techniques for combinatorial problems, John Wiley & Sons, Inc., New York, NY, 1993
• 9: Eglese, R.W. 1990. Simulated annealing: a tool for operational research, European Journal of Operational Research, Vol. 46, No. 3. June 15, 1990. pp. 271-281.
• 10: Mark Alan Fleischer, Assessing the performance of the simulated annealing algorithm using information theory, Case Western Reserve University, Cleveland, OH, 1994
• 11: Fleischer, M. and S. H. Jacobson. 1994. Information theory and the simulated annealing algorithm: experimental results. Technical Report, Department of Engineering Management, Old Dominion University, Norfolk, VA.
• 12: Fleischer, M. 1995. Cybernetic optimization by simulated annealing: accelerating convergence by parallel processing and probabilistic feedback control, Technical Report. Department of Engineering Management, Old Dominion University, Norfolk, VA.
• 13: Fleischer, M. and S. H. Jacobson. 1995. Cybernetic optimization by simulated annealing: an implementation of parallel processing using probabilistic feedback control. In Metaheuristics: The State of the Art 1995 (Proceeding of the Metaheuristics International Conference 1995), ed. J. Kelly, I. Osman, Kluwer Academic Publishers, New York, N.Y. To appear.
• 14: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 15: Glover, F. 1989. Tabu search-part I. ORSA Journal on Computzng, Vol. 1, No. 3. pp. 190-206.
• 16: Glover, F. 1995. Tabu thresholding: improved search by nonmonotonic trajectories. To appear in IN- FORMS Journal on Computing.
• 17: L. Goldstein , M. Waterman, Neighborhood size in the Simulated Annealing Algorithm, American Journal of Mathematical and Management Sciences, v.8 n.3-4, p.409-423, Jan. 1988
• 18: Ingber, L. 1995. Adaptive simulated annealing: lessons learned. Journal of Control and Cybernetics. To appear.
• 19: David S. Johnson , Cecilia R. Aragon , Lyle A. McGeoch , Catherine Schevon, Optimization by simulated annealing: an experimental evaluation. Part I, graph partitioning, Operations Research, v.37 n.6, p.865-892, Nov–Dec. 1989 [doi>10.1287/opre.37.6.865]
• 20: Kirkpatrick, S., C. D. Gelatt, Jr., and M. P. Vecchi. 1983. Optimization by simulated annealing. Sczence, Vol. 220, No. 4598, May 13, 1983. pp. 671-680.
• 21: Udi Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 22: Metropolis, N., A. Rosenbluth, M. Rosenbluth, A. Teller and E. Teller. 1953. Equation of state calculations by fast computing machines. Journal of Chemical Physics, Vol. 21, pp. 1087- 1092.
• 23: Mitra, D., F. Romeo and A. Sangiovanni-Vincentelli. 1986. Convergence and finite- time behavior of simulated annealing. Advances zn Applied Probability, Vol. 18, pp. 747-771.
• 24: Ibrahim Hassan Osman, Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, Annals of Operations Research, v.41 n.1-4, p.421-451, 1993
• 25: C. A. Tovey, Simulated, simulated annealing, American Journal of Mathematical and Management Sciences, v.8 n.3-4, p.389-407, Jan. 1988
• 26: Norbert Wiener, Cybernetics: Or Control and Communication in Animal and the Machine, MIT Press, Cambridge, MA, 2000
• 27: Yao, X. 1991. Simulated annealing with extended neighborhood. Internat,onal Journal of Computer Mathematics, Vol. 40, pp. 169-89.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  K. Computing Milieux
  K.2 HISTORY OF COMPUTING
      Subjects: Theory

General Terms:
Algorithms, Theory