[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Log in

Finite-Time Performance Analysis of Static Simulated Annealing Algorithms

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

Generalized hill climbing (GHC) algorithms provide a framework for modeling local search algorithms for addressing intractable discrete optimization problems. Current theoretical results are based on the assumption that the goal when addressing such problems is to find a globally optimal solution. However, from a practical point of view, solutions that are close enough to a globally optimal solution (where close enough is measured in terms of the objective function value) for a discrete optimization problem may be acceptable. This paper introduces β-acceptable solutions, where β is a value greater than or equal to the globally optimal objective function value. Moreover, measures for assessing the finite-time performance of GHC algorithms, in terms of identifying β-acceptable solutions, are defined. A variation of simulated annealing (SA), termed static simulated annealing (S2A), is analyzed using these measures. S2A uses a fixed cooling schedule during the algorithm's execution. Though S2A is provably nonconvergent, its finite-time performance can be assessed using the finite-time performance measures defined in terms of identifying β-acceptable solutions. Computational results with a randomly generated instance of the traveling salesman problem are reported to illustrate the results presented. These results show that upper and lower estimates for the number of iterations to reach a β-acceptable solution within a specified number of iterations can be obtained, and that these estimates are most accurate for moderate and high fixed temperature values for the S2A algorithm.

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

Access this article

Subscribe and save

Springer+ Basic
£29.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

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. S. Anily and A. Federgruen, “Simulated annealing methods with general acceptance probabilities,” Journal of Applied Probability, vol. 24, pp. 657–667, 1987.

    Google Scholar 

  2. C. Balaguer, A. Giménez, J.M. Pastor, V.M. Padrón, and M. Abderrahim, “A climbing autonomous robot for inspection applications in 3D complex environments,” Robotica, vol. 18, pp. 287–297, 2000.

    Google Scholar 

  3. O. Cantoni and R. Cerf, “The exit path of a Markov chain with rare transitions,” ESAIM: Probability and Statistics, vol. 1, pp. 95–144, 1987.

    Google Scholar 

  4. T.S. Chiang and Y.Y. Chow, “A limit-theorem for a class of inhomogeneous Markov-processes,” Annals of Probability, vol. 17, pp. 1483–1502, 1989.

    Google Scholar 

  5. H. Cohn, and M. Fielding, “Simulated annealing: Searching for an optimal temperature schedule,” SIAM Journal of Optimization, vol. 9, no. 3, 779–802, 1999.

    Google Scholar 

  6. G.A. Croes, “A method for solving traveling-salesman problems,” Operations Research, vol. 6, pp. 791–812, 1958.

    Google Scholar 

  7. M.P. Desai, “Some results characterizing the finite time behaviour of the simulated annealing algorithm,” Sadhana, vol. 24, pp. 317–337, 1999.

    Google Scholar 

  8. G. Dueck and T. Scheuer, “Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing,” European Journal of Operational Research, vol. 46, pp. 271–281, 1990.

    Google Scholar 

  9. A.G. Ferreira and J. Zerovnik, “Bounding the probability of success of stochastic methods for global optimization,” Computers and Mathematics Applications, vol. 25, no. 10/11, pp. 1–8, 1993.

    Google Scholar 

  10. M. Fielding, “Simulated annealing with an optimal fixed temperature,” SIAM Journal of Optimization, vol. 11, pp. 289–307, 2000.

    Google Scholar 

  11. M.A. Fleischer, “Simulated annealing: Past, present, and future,” in Proceedings of the 1995Winter Simulation Conference, 1995, pp. 155–161.

  12. M.A. Fleischer and S.H. Jacobson, “Information theory and the finite-time behavior of the simulated annealing algorithm: Experimental results,” INFORMS Journal on Computing, vol. 11, pp. 35–43, 1999.

    Google Scholar 

  13. H. Foerster and G. W¨ascher, “Simulated annealing for order spread minimization in sequencing cutting patterns,” European Journal of Operational Research, vol. 126, pp. 106–130, 1998.

    Google Scholar 

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

    Google Scholar 

  15. B. Hajek, “Cooling schedules for optimal annealing,” Mathematics of Operations Research, vol. 13, pp. 311–329, 1988.

    Google Scholar 

  16. K. Helsgaun, “An effective implementation of the Lin-Kernighan traveling salesman heuristic,” European Journal of Operational Research, vol. 126, pp. 106–130, 2000.

    Google Scholar 

  17. D. Henderson and S.H. Jacobson, “The finite-time performance of generalized hill climbing algorithms,” Technical Report, University of Illinois, Urbana, Illinois, 2001.

    Google Scholar 

  18. D. Henderson, S.H. Jacobson, and A.W. Johnson, “The theory and practice of simulated annealing,” in State of-the-Art Handbook in Metaheuristics. To appear.

  19. S.H. Jacobson, K.A. Sullivan, and A.W. Johnson, “Discrete manufacturing process design optimization using computer simulation and generalized hill climbing algorithms,” Engineering Optimization, vol. 31, pp. 247–260, 1998.

    Google Scholar 

  20. A.W. Johnson and S.H. Jacobson, “A class of convergent generalized hill climbing algorithms,” Applied Mathematics and Computation. To appear.

  21. A.W. Johnson and S.H. Jacobson, “On the convergence of generalized hill climbing algorithms,” Discrete Applied Mathematics. To appear.

  22. S. Kobayashi, M. Edahiro, and M. Kubo, “A VLSI scan-chain optimization algorithm for multiple scanpaths,” IEICE Transactions on Fundamentals of Electronics, Communications, and Computer Science, vol. 11, pp. 2499–2504, 1999.

    Google Scholar 

  23. E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys, The Traveling Salesman Problem, John Wiley and Sons: Chichester, United Kingdom, 1985.

    Google Scholar 

  24. S. Lin and B.W. Kernighan, “An effective heuristic for the traveling salesman problem,” Operations Research, vol. 21, pp. 498–516, 1973.

    Google Scholar 

  25. C. Mazza, “Parallel simulated annealing,” Random Structures and Algorithms, vol. 3, pp. 139–148, 1992.

    Google Scholar 

  26. D. Mitra, F. Romeo, and A.L. Sangiovanni-Vincentelli, “Convergence and finite-time behavior of simulated annealing,” Advances in Applied Probability, vol. 18, pp. 747–771, 1986.

    Google Scholar 

  27. R. Srichander, “Efficient schedules for simulated annealing,” Engineering Optimization, vol. 24, pp. 161–176, 1995.

    Google Scholar 

  28. X. Yao, “A new simulated annealing algorithm,” International Journal of Computer Mathematics, vol. 56, pp. 161–168, 1995.

    Google Scholar 

  29. X. Yao and G. Li, “General simulated annealing,” Journal of Computer Science and Technology, vol. 6, pp. 329–338, 1991.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Orosz, J.E., Jacobson, S.H. Finite-Time Performance Analysis of Static Simulated Annealing Algorithms. Computational Optimization and Applications 21, 21–53 (2002). https://doi.org/10.1023/A:1013544329096

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1013544329096

Navigation