next up previous

4.1.3 Annealing Schedule     continued...

Length of Markov Chains

An obvious choice for , the length of the k-th Markov chain, is a value that depends on the size of the problem, so is independent of k. Alternatively it can be argued that a minimum number of transitions should be accepted at each temperature. However, as approaches 0, transitions are accepted with decreasing probability so the number of trials required to achieve acceptances approaches . Thus, in practice, an algorithm in which each Markov chain is terminated after

whichever comes first, is a suitable compromise.