Efficient simulated annealing on fractal energy landscapes (Q805499)

A new theoretical framework for analyzing simulated annealing is presented. 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. For a class of deterministic fractal landscapes, and for ``linearly separable'' functions, annealing is proved to be efficient, running in time polynomial or quasi-polynomial in the solution quality. The cooling schedule employed is the familiar geometric schedule of annealing practice, rather than the logarithmic schedule of previous theory. While random sampling and descent algorithms may be more efficient than annealing in some cases, their run times increase exponentially with the number of dimensions, while annealing's increases only linearly. A number of circuit placement problems are found to have energy landscapes with weaker, random fractal properties, giving for the first time a reasonable explanation of the successful application of simulated annealing to problems in the VLSI domain. The analysis models annealing as a random walk on a graph, and uses recent theorems relating the ``conductance'' of a graph to the mixing rate of its associated Markov chain. This enables both a new conceptual approach and new quantitative methods. Another foundation of the analysis is a proof that the expected energy cannot increase during annealing with decreasing temperatures; a surprising ``probability pump'' counterexample exists if the hypotheses are weakened slightly. This article is extracted from the author's doctoral thesis. Additional material there includes the construction of a more efficient ``hypergeometric'' cooling schedule for annealing on the deterministic fractals, and numerical experiments on a ``real-world'' circuit partitioning problem instance. The experiments confirm the predicted dependence of solution quality on the initial temperature and run time. Contradicting the theoretical predictions, however, the effect of the temperature reduction factor is found to be almost nonexistent.