Probability in the Engineering and Informational Sciences

Research Article

Simulated Annealing and Adaptive Search in Global Optimization

H. Edwin Romeijna1* and Robert L. Smitha2

a1 Rotterdam School of Management, Erasmus University Rotterdam, P.O. Box 1738, NL-3000 DR Rotterdam, The Netherlands

a2 Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, Michigan 48109–2117

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.

Footnotes

* The work of this author was supported in part by a NATO Science Fellowship of the Netherlands Organization for Scientific Research (NWO).