Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-30T22:21:16.243Z Has data issue: false hasContentIssue false
  • English
  • Français

Simulated Annealing and Adaptive Search in Global Optimization

Published online by Cambridge University Press:  27 July 2009

H. Edwin Romeijn  and
Robert L. Smith
H. Edwin Romeijn
Affiliation:
Rotterdam School of Management, Erasmus University Rotterdam, P.O. Box 1738, NL-3000 DR Rotterdam, The Netherlands
Robert L. Smith
Affiliation:
Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, Michigan 48109–2117
Get access Rights & Permissions [Opens in a new window]

Abstract

Simulated annealing is a class of sequential search techniques for solving continuous global optimization problems. In this paper we attempt to help explain the success of simulated annealing for this class of problems by studying an idealized version of this algorithm, which we call adaptive search. The prototypical adaptive search algorithm generates a sequence of improving points drawn conditionally from samples from a corresponding sequence of probability distributions. Under the condition that the sequence of distributions stochastically dominate in objective function value the uniform distribution, we show that the expected number of improving points required to achieve the global optimum within a prespecified error grows at most linearly in the dimension of the problem for a large class of global optimization problems. Moreover, we derive a cooling schedule for simulated annealing, which follows in a natural way from the definition of the adaptive search algorithm.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 8 , Issue 4 , October 1994 , pp. 571 - 590
Copyright
Copyright © Cambridge University Press 1994

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. & Korst, J.H.M. (1988). Simulated annealing and Boltzmann machines. Chichester: Wiley.Google Scholar
2.Aarts, E.H.L. & van Laarhoven, P.J.M. (1989). Simulated annealing: An introduction. Statistica Neerlandica 43: 31–52.CrossRefGoogle Scholar
3.Bélisle, C.J.P. (1992). Convergence theorems for a class of simulated annealing algorithms on . Journal of Applied Probability 29(4): 885–895.CrossRefGoogle Scholar
4.Bohachevsky, I.O., Johnson, M.E., & Stein, M.L. (1986). Generalized simulated annealing for function optimization. Technometrics 28: 209–217.CrossRefGoogle Scholar
5.Corana, A., Marchesi, M., Martini, C., & Ridella, S. (1987). Minimizing multimodal functions for continuous variables with the “simulated annealing” algorithm. ACM Transactions on Mathematical Software 13: 262–280.CrossRefGoogle Scholar
6.Dekkers, A. & Aarts, E. (1991). Global optimization and simulated annealing. Mathematical Programming 50: 367–393.CrossRefGoogle Scholar
7.Gelfand, S.B. & Mitter, S.K. (1993). Metropolis-type annealing algorithms for global optimization in . SIAM Journal on Control and Optimization 31(1): 111–131.CrossRefGoogle Scholar
8.Geluk, J.L. (1984). Abelian and Tauberian theorems for 0-varying functions. Technical Report 8409/S, Econometric Institute, Erasmus University Rotterdam, Rotterdam, The Netherlands.Google Scholar
9.Hajek, B. (1988). Cooling schedules for optimal annealing. Mathematics of Operations Research 13: 311–329.CrossRefGoogle Scholar
10.Halmos, P.R. (1950). Measure theory. New York: Van Nostrand.CrossRefGoogle Scholar
11.Kirkpatrick, S., Gelatt, C.D. Jr., & Vecchi, M.P. (1983). Optimization by simulated annealing. Science 20: 671–680.CrossRefGoogle Scholar
12.Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.M., & Teller, E. (1953). Equations of state calculations by fast computing machines. The Journal of Chemical Physics 21: 1087–1092.CrossRefGoogle Scholar
13.Patel, N.R. & Smith, R.L. (1983). The asymptotic extreme value distribution of the sample minimum of a concave function under linear constraints. Operations Research 31: 789–794.CrossRefGoogle Scholar
14.Patel, N.R., Smith, R.L., & Zabinsky, Z.B. (1988). Pure adaptive search in Monte Carlo optimization. Mathematical Programming 43: 317–328.CrossRefGoogle Scholar
15.Pincus, M. (1968). A closed form solution for certain programming problems. Operations Research 16: 690–694.CrossRefGoogle Scholar
16.Pincus, M. (1970). A Monte Carlo method for the approximate solution of certain types of constrained optimization problems. Operations Research 18: 1225–1228.CrossRefGoogle Scholar
17.Romeijn, H.E. & Smith, R.L. (1994). Simulated annealing for constrained global optimization. Journal of Global Optimization 5: 101–126.CrossRefGoogle Scholar
18.Ross, S.M. (1983). Stochastic processes. New York: Wiley.Google Scholar
19.Rubinstein, R.Y. (1981). Simulation and the Monte Carlo method. New York: Wiley.CrossRefGoogle Scholar
20.Zabinsky, Z.B. & Smith, R.L. (1992). Pure adaptive search in global optimization. Mathematical Programming 53(3): 323–338.CrossRefGoogle Scholar