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.
Similar content being viewed by others
References
S. Anily and A. Federgruen, “Simulated annealing methods with general acceptance probabilities,” Journal of Applied Probability, vol. 24, pp. 657–667, 1987.
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.
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.
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.
H. Cohn, and M. Fielding, “Simulated annealing: Searching for an optimal temperature schedule,” SIAM Journal of Optimization, vol. 9, no. 3, 779–802, 1999.
G.A. Croes, “A method for solving traveling-salesman problems,” Operations Research, vol. 6, pp. 791–812, 1958.
M.P. Desai, “Some results characterizing the finite time behaviour of the simulated annealing algorithm,” Sadhana, vol. 24, pp. 317–337, 1999.
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.
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.
M. Fielding, “Simulated annealing with an optimal fixed temperature,” SIAM Journal of Optimization, vol. 11, pp. 289–307, 2000.
M.A. Fleischer, “Simulated annealing: Past, present, and future,” in Proceedings of the 1995Winter Simulation Conference, 1995, pp. 155–161.
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.
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.
M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman: San Francisco, California, 1979.
B. Hajek, “Cooling schedules for optimal annealing,” Mathematics of Operations Research, vol. 13, pp. 311–329, 1988.
K. Helsgaun, “An effective implementation of the Lin-Kernighan traveling salesman heuristic,” European Journal of Operational Research, vol. 126, pp. 106–130, 2000.
D. Henderson and S.H. Jacobson, “The finite-time performance of generalized hill climbing algorithms,” Technical Report, University of Illinois, Urbana, Illinois, 2001.
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.
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.
A.W. Johnson and S.H. Jacobson, “A class of convergent generalized hill climbing algorithms,” Applied Mathematics and Computation. To appear.
A.W. Johnson and S.H. Jacobson, “On the convergence of generalized hill climbing algorithms,” Discrete Applied Mathematics. To appear.
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.
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.
S. Lin and B.W. Kernighan, “An effective heuristic for the traveling salesman problem,” Operations Research, vol. 21, pp. 498–516, 1973.
C. Mazza, “Parallel simulated annealing,” Random Structures and Algorithms, vol. 3, pp. 139–148, 1992.
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.
R. Srichander, “Efficient schedules for simulated annealing,” Engineering Optimization, vol. 24, pp. 161–176, 1995.
X. Yao, “A new simulated annealing algorithm,” International Journal of Computer Mathematics, vol. 56, pp. 161–168, 1995.
X. Yao and G. Li, “General simulated annealing,” Journal of Computer Science and Technology, vol. 6, pp. 329–338, 1991.
Author information
Authors and Affiliations
Rights 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
Issue Date:
DOI: https://doi.org/10.1023/A:1013544329096