ON THE CONVERGENCE OF STATIONARY DISTRIBUTIONS IN SIMULATED ANNEALING ALGORITHMS

Simulated annealing is a randomized optimization algorithm which accepts deterioration of the objective function with a probability depending on a control parameter t in each iteration. Under general assumptions we show that the equilibrium distributions with respect to the parameter levels converge to the distribution which selects a global optimum with probability one. This result may be taken as an explanation for the observed good performance of simulated annealing implementations which prefer many iterations on relatively few parameter levels to relatively few iterations at many parameter levels.