On the convergence of stationary distributions in simulated annealing algorithms (Q1099589): Difference between revisions

Simulated annealing is an iterative probabilistic algorithm designed to find good solutions for discrete optimization problems. At each iterative step a deterioration of the objective function is accepted with a certain probability. This probability depends upon a parameter t called the temperature and approaches zero as t approaches zero. Thus optimal objective values are attained as the temperature is decreased to zero. Computational experiments have indicated that convergence to the optimum state need not occur if the temperature t is decreased too quickly. Research suggests that the most favourable procedure to use is to iterate at a fixed temperature for a sufficiently large number of iterations before lowering the parameter t to a new level. In this way relatively few different parameters are required to reach a solution. Intuitively this procedure suggests generating the equilibrium distribution for each temperature with the expectation that these distributions will converge to the optimum as t tends to zero. It is the purpose of this paper to lend theoretical support to this supposition. The results are obtained within the framework of Markov processes. By considering directly the limit of the stationary distributions, it has been possible for the authors to prove convergence to the optimum for a comprehensive class of simulated annealing algorithms based on connected undirected neighbourhood graphs. One consequence of the generality of the proof is the considerable flexibility it facilitates in the design of simulated annealing algorithms which can be exd its specific differences with the other approaches, mainly the K \& R standard. For higher sophisticated programming techniques can be consulted and other (already) classical texts, but this one is indispensable for the moment, let they be beginners or advanced programmers in C language.