Analysis of finite length annealing schedules

Abstract

By constructing a master equation for the distribution of outcomes from simulated annealing, we are able to characterize this process exactly for arbitrary annealing schedules on extremely small problems. Two sorts of numerical experiments are reported, using this formalism. First, annealing schedules are found which minimize the cut cost of partitioning a highly symmetric weighted graph, using a fixed number of Monte Carlo search steps. The experiments yield some surprising results, which sharpen our understanding of the problems inherent in trying to optimize a stochastic search. For example, optimal annealing schedules are not monotone decreasing in temperature. Second, we construct configuration spaces of random energies and varying connectivity. These are used to compare different annealing schedules which are common in the literature. The experiments also provide an occasion to contrast annealing schedules derived from asymptotic, worst-case bounds on convergence to the global optimum with adaptive schedules which attempt to maintain the system close to equilibrium throughout the annealing process. © 1991 Springer-Verlag New York Inc.