Nested annealing: a provable improvement to simulated annealing

Simulated annealing is a family of randomized algorithms for solving multivariate global optimization problems. Empirical results from the application of simulated annealing algorithms to certain hard problems including certain types of NP-complete problems demonstrate that these algorithms yield better results than known heuristic algorithms. But for the worst case input, the time bound can be exponential. In this paper, for the first time, we show how to improve the performance of simulated annealing algorithms by exploiting some special properties of the cost function to be optimized. In particular, the cost functions we consider are small-separable, with parameter s(n). We develop an algorithm we call "Nested Annealing" which is a simple modification of simulated annealing where we assign different temperatures to different regions. Simulated annealing can be shown to have expected run time 2Ω(n) whereas our improved algorithm has expected performance 2Os(n). Thus for example, in many vision and VLSI layout problem, for whichs(n=O( n), our time bound is 2O( n) rather than 2Ω(n). © 1992.

Duke Scholars

Author John H. Reif Computer Science