On Logarithmic Simulated Annealing

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