Abstract
Simulated Annealing has proved to be a very sucessful heuristic for various combinatorial optimization problems. It is a randomized algorithm, that attempts to find the global optimum with high probability by local exchanges. In this paper we give a new proof of the convergence of Simulated Annealing with logarithmic cooling schedule by considering the conductance of the underlying transition graph. With this proof technique it is possible to obtain better bounds for the finite time behaviour of Simulated Annealing than previously known.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Anily, S. and Federgruen, A.:Ergodicity in Parametric Nonstationary Markov Chains: An Application to Simulated Annealing Methods, Oper. Res. 35, 1987.
Garey, M.R.; Johnson, S.J.:Computers and Intractability, W.H. Freeman and Company, 1979.
Gidas, B.:Nonstationary Markov Chains and Convergence of the Annealing Algorithm, J. Statis. Phys. 39, 1985.
Hajek, B.:Hitting Time and Occupation -Time Bounds Implied By Drift Analysis With Applications, Advanced Applied Probability 14, 1982.
Hajek, B.:Cooling Schedules for Optimal Annealing, Mathematics of Operations Research 13, 1988.
Jerrum, M.:Large Cliques elude the Metropolis Process, Random Structures and Algorithms 3, 1992.
Jerrum, J; Sinclair, A.:Approximating the permanent, Proceedings of the 20th ACM-Symposium on Theory of Computing, 1988.
Johnson, D.S. et al.:Optimization by Simulated Annealing: An Experimental Evaluation, perations Research 39, 1991.
Kirkpatrick, S.; Gelatt, C.D.; Vecchi, M.P.:Optimization by Simulated Annealing, Science 220, 1983.
Laarhoven, P.J.M.; Aarts, E.H.L.:Simulated Annealing: Theory and Applications, Kluwer Academic Publishers, 1989.
Metropolis, N. et al.:Equations of state calculations by fast computer machines, Journal of Chemical Physics 21, 1953.
Mihail, M.:Conductance and Convergence of Markov chains- A combinatorial treatment of expanders, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, 1989.
Mitra, D.; Romeo, F.; Sangiovanni-Vincentelli, A.L.:Convergence and Finite Time Behaviour of Simulated Annealing, Adv. Appl. Prob. 18, 1986.
Nolte, A.; Schrader, R.: Simulated Annealing for Graph Coloring, Technical report, University of Cologne, in preparation.
Nolte, A.; Schrader, R.:Simulated Annealing and its Problems to Color Graphs, Proceedings of the ESA 96, Springer Lecture Notes in Computer Science, to appear.
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nolte, A., Schrader, R. (1997). A Note on the Finite Time Behaviour of Simulated Annealing. In: Operations Research Proceedings 1996. Operations Research Proceedings, vol 1996. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-60744-8_32
Download citation
DOI: https://doi.org/10.1007/978-3-642-60744-8_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-62630-5
Online ISBN: 978-3-642-60744-8
eBook Packages: Springer Book Archive