Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-23T18:21:39.577Z Has data issue: false hasContentIssue false
  • English
  • Français

Convergence of Simulated Annealing with Feedback Temperature Schedules

Published online by Cambridge University Press:  27 July 2009

M. Kolonko  and
M. T. Tran
M. Kolonko
Affiliation:
Institut für Mathematik, Universität Hildesheim, Marienburger Platz 22, D-31141 Hildesheim, Germany
M. T. Tran
Affiliation:
Institut für Mathematik, Universität Hildesheim, Marienburger Platz 22, D-31141 Hildesheim, Germany
Get access Rights & Permissions [Opens in a new window]

Abstract

It is well known that the standard simulated annealing optimization method converges in distribution to the minimum of the cost function if the probability a for accepting an increase in costs goes to 0. α is controlled by the “temperature” parameter, which in the standard setup is a fixed sequence of values converging slowly to 0. We study a more general model in which the temperature may depend on the state of the search process. This allows us to adapt the temperature to the landscape of the cost function. The temperature may temporarily rise such that the process can leave a local optimum more easily. We give weak conditions on the temperature schedules such that the process of solutions finally concentrates near the optimal solutions. We also briefly sketch computational results for the job shop scheduling problem.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 11 , Issue 3 , July 1997 , pp. 279 - 304
Copyright
Copyright © Cambridge University Press 1997

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Aarts, E.H.L., van Laarhoven, P.J.M., Lenstra, J.K., & Ulder, N.L.J. (1994). A computational study of local search algorithms for job shop scheduling. ORSA Journal on Computing 6: 118–125.CrossRefGoogle Scholar
2.Anily, S. & Federgruen, A. (1987). Simulated annealing methods with general acceptance probabilities. Journal of Applied Probability 24: 657–667.CrossRefGoogle Scholar
3.Bouleau, N. & Lépingle, D. (1984). Numerical methods for stochastic processes. New York: J. Wiley.Google Scholar
4.Brucker, P. (1995). Scheduling algorithms. Berlin: Springer-Verlag.Google Scholar
5.Faigle, U. & Kern, W. (1989). Note on the convergence of simulated annealing algorithms. SIAM Journal of Control and Optimization 29: 153–159.CrossRefGoogle Scholar
6.Greene, J.W. & Supowit, K.J. (1986). Simulated annealing without rejecting moves. IEEE Transactions on Computer Aided Design 5(1): 221–228.CrossRefGoogle Scholar
7.Hajek, B. (1988). Cooling schedules for optimal annealing. Mathematics of Operations Research 13: 311–329.CrossRefGoogle Scholar
8.Kolonko, M. (1994). A piecewise Markovian model for simulated annealing with stochastic cooling schedules. Journal of Applied Probability 32: 649–658.CrossRefGoogle Scholar
9.van Laarhoven, P.J.M. & Aarts, E.H.L. (1987). Simulated annealing: Theory and applications. Dordrecht: Reidel.CrossRefGoogle Scholar
10.van Laarhoven, P.J.M., Aarts, E.H.L. & Lenstra, J.K. (1992). Job shop scheduling by simulated annealing. Operations Research 40: 113–125.CrossRefGoogle Scholar
11.Loève, M. (1978). Probability theory II, 4th ed.Berlin: Springer-Verlag.Google Scholar
12.Lundy, M. & Mees, A. (1986). Convergence of an annealing algorithm. Mathematical Programming 34: 111–124.Google Scholar
13.Mitra, D., Romeo, F. & Sangiovanni-Vincentelli, A. (1986). Convergence and finite-time behaviour of simulated annealing. Advances in Applied Probability 18: 747–771.Google Scholar
14.Pólya, G. & Szegö, G. (1970). Aufgaben und Lehrsätze aus der Analysis I, 4th ed.Berlin: Springer-Verlag.CrossRefGoogle Scholar
15.Schäl, M. (1975). Conditions for optimally in dynamic programming and for the limit of n stage optimal policies to be optimal. Z. Wahrscheinlichkeitstheorie verwandte Gebiete 32: 179–196.Google Scholar
16.Schweitzer, P.J. (1968). Perturbation theory and finite Markov chains. Journal of Applied Probability 5: 401–413.CrossRefGoogle Scholar
17.Shahookar, K. & Mazumder, P. (1991). VLSI cell placement techniques. ACM Computing Surveys 23: 143–220.CrossRefGoogle Scholar
18.Tran, M.T. (1995). Simulated annealing: Konstruktion und Analyse einer Auswahl stochastischer Optimierungsverfahren mit Hilfe inhomogener Markoff-Ketten. Dissertation, Universität Hildesheim. Hildesheim, Germany.Google Scholar
19.Vaessens, R.J.M., Aarts, E.H.L. & Lenstra, J.K. (1994). Job shop scheduling by local search. Memorandum COSOR 94-05, Eindhoven University of Technology.Google Scholar