We perform a convergence analysis of simulated annealing for the special case of logarithmic cooling schedules. For this class of simulated annealing algorithms, B. HAJEK [7] proved that the convergence to optimum solutions requires the lower bound T/ln(k+2) on the cooling schedule, where k is the number of transitions and denotes the maximum value of the escape depth from local minima. Let n be a uniform upper bound for the number of neighbours in the underlying configuration space. Under some natural assumptions, we prove the following convergence rate: After k≥n sup(o(t))+log sup(O(1))(1/ε) transitions the probability to be in an optimum solution is larger than （1-ε）The result can be applied, for example, to the average case analysis of stochastic algorithms when estimations of the corresponding values T are known.
展开▼
