Simulated Annealing — Absorption & Recurrent Behaviour in Time-Inhomogeneous Markov Chains
Manh Tien Tran · 1992
Simulated Annealing is a randomized algorithm which has been proposed for finding global optima in large NP-complete problems with cost functions which may have several local minima. A theoretical analysis of simulated annealing is based on the theory of time-inhomogeneous Markov chains. We analyze the asymptotic behaviour of time-inhomogeneous Markov chains with general state space. We consider an arbitrary partition {A, A C } of the state space Ω where A could be the set of optimal solutions. We give a necessary and sufficient condition for the “reachability” of A and a simple sufficient condition for the asymptotic absorption in A.