 |
    |
On the Complexity to Approach Optimum Solutions by Inhomogeneous Markov Chains
Andreas A. Albrecht
University of Hertfordshire, Dept. of Computer Science, Hatfield, Herts AL10 9AB, UKAbstract. We analyse the probability 1–
to be in an optimum solution after k steps of an inhomogeneous Markov chain which is specified by a logarithmic cooling schedule c(k) =
/ ln (k+2). We prove that after k >(n/)O() steps the probability to be in an optimum solution is larger than 1–, where n is an upper bound for the size of local neighbourhoods and is a parameter of the entire configuration space. By counting the occurrences of configurations, we demonstrate for an application with known optimum solutions that the lower bound indeed ensures the stated probability for a relatively small constant in O().
Keywords: Markov Chains, Simulated Annealing, Cooling Schedules, Local Search, Convergence Analysis.
LNCS 3102, p. 642 ff.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004