Hostname: page-component-76fb5796d-25wd4 Total loading time: 0 Render date: 2024-04-26T19:06:49.562Z Has data issue: false hasContentIssue false
  • English
  • Français

Convergence properties of simulated annealing for continuous global optimization

Part of: Combinatorial probability

Published online by Cambridge University Press:  14 July 2016

M. Locatelli
M. Locatelli*
Affiliation:
Universitá degli studi di Milano
*
∗Postal address: Dipartimento di Scienze dell'Informazione, Via Comelico, 39/41–20135 Milano, Italy.
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper conditions for the convergence of a class of simulated annealing algorithms for continuous global optimization are given. The previous literature about the subject gives results for the convergence of algorithms in which the next candidate point is generated according to a probability distribution whose support is the whole feasible set. A class of possible cooling schedules has been introduced in order to remove this restriction.

Keywords

SIMULATED ANNEALINGCONTINUOUS GLOBAL OPTIMIZATIONCOOLING SCHEDULE

MSC classification

Primary: 60C05: Combinatorial probability
Type
Research Papers
Information
Journal of Applied Probability , Volume 33 , Issue 4 , December 1996 , pp. 1127 - 1140
Copyright
Copyright © Applied Probability Trust 1996 

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] Anily, S. and Federgruen, A. (1985) Probabilistic analysis of simulated annealing methods. Technical Report. Graduate School of Business, Columbia University, New York.Google Scholar
[2] Belisle, C. J. P. (1992) Convergence theorems for a class of simulated annealing algorithms on. J. Appl. Prob. 29, 885–892.CrossRefGoogle Scholar
[3] Bohachevsky, I. O., Johnson, M. E. and Stein, M. L. (1986) Generalized simulated annealing for function optimization. Technometrics 28, 209–217.Google Scholar
[4] Černy, V. (1985) Thermodynamical approach to the travelling salesman problem: an efficient simulation algorithm. J. Optim. Theory Appl. 45, 41–51.Google Scholar
[5] Doob, J. L. (1953) Stochastic Processes. Wiley, New York.Google Scholar
[6] Gelfand, S. and Mitter, S. (1985) Analysis of simulated annealing for optimization. Proc. 24th Conf. on Decision and Control. pp. 779–786.Google Scholar
[7] Hajek, B. (1988) Cooling schedules for optimal annealing. Math. Operat. Res. 13, 311–329.Google Scholar
[8] Huang, M. D., Romeo, F. and Sangiovanni-Vincentelli, A. (1986) An efficient general cooling schedule for simulated annealing. Proc. ICCAD. pp. 381–284.Google Scholar
[9] Kemeny, J. G. and Snell, J. L. (1976) Finite Markov Chains. Springer, New York.Google Scholar
[10] Kirkpatrick, S., Gelatt, C. D. and Vecchi, M. P. (1983) Optimization by simulated annealing. Science 220, 671–680.Google Scholar
[11] Lam, J. and Delosme, J.-M. (1986) Logic minimization using simulated annealing. Proc. ICCAD. pp. 348–352.Google Scholar
[12] Lam, J. and Delosme, J.-M. (1987) An adaptive annealing schedule. Technical Report 8608. University of Yale, New Haven.Google Scholar
[13] Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N. and Teller, A. H. (1953) Equation of state calculations by fast computer machines. J. Chem. Pys. 21, 1087.Google Scholar
[14] Mood, A. M., Graybill, F. A. and Boes, D. C. (1974) Introduction to the Theory of Statistics. McGraw-Hill, New York.Google Scholar
[15] Romeo, F. (1989) Simulated annealing: theory and applications to layout problems. PhD thesis. University of California, Berkeley, CA.Google Scholar
[16] Sorkin, G. B. (1991) Efficient simulated annealing on fractal energy landscapes. Algorithmica 6, 367–418.CrossRefGoogle Scholar
[17] Törn, A. and Zilinskas, A. (1987) Global Optimization. Springer, Berlin.Google Scholar
[18] Wong, E. (1991) Stochastic neural networks. Algorithmica. 6, 466–478.Google Scholar
[19] Zhigljavsky, A. A. (1991) Theory of Global Random Search. Kluwer, Dordrecht.Google Scholar