EFFICIENT SIMULATED ANNEALING ON FRACTAL ENERGY LANDSCAPES

We present a new theoretical framework for analyzing simulated annealing. The behavior of simulated annealing depends crucially on the "energy landscape" associated with the optimization problem: the landscape must have special properties if annealing is to be efficient. We prove that certain fractal properties are sufficient for simulated annealing to be efficient in the following sense: If a problem is scaled to have best solutions of energy 0 and worst solutions of energy 1, a solution of expected energy no more than epsilon can be found in time polynomial in 1/epsilon, where the exponent of the polynomial depends on certain parameters of the fractal. Higher-dimensional versions of the problem can be solved with almost identical efficiency. The cooling schedule used to achieve this result is the familiar geometric schedule of annealing practice, rather than the logarithmic schedule of previous theory. Our analysis is more realistic than those of previous studies of annealing in the constraints we place on the problem space and the conclusions we draw about annealing's performance. The mode of analysis is also new: Annealing is modeled as a random walk on a graph, and recent theorems relating the "conductance" of a graph to the mixing rate of its associated Markov chain generate both a new conceptual approach to annealing and new analytical, quantitative methods. The efficiency of annealing is compared with that of random sampling and descent algorithms. While these algorithms are more efficient for some fractals, their run times increase exponentially with the number of dimensions, making annealing better for problems of high dimensionality. We find that a number of circuit placement problems have energy landscapes with fractal properties, thus giving for the first time a reasonable explanation of the successful application of simulated annealing to problems in the VLSI domain.