Simulated annealing on uncorrelated energy landscapes. (English) Zbl 0806.92014

Summary: A function \(f: \{0,1,2, L,a\}^ n\to R\) is said to be uncorrelated if \(\text{Prob} [f(x)\leq u]= G(u)\). This paper studies the effectiveness of simulated annealing as a strategy for optimizing uncorrelated functions. A recurrence relation expressing the effectiveness of the algorithm in terms of the function \(G\) is derived. Surprising numerical results are obtained, to the effect that for certain parametrized families of functions \(\{G_ c\), \(c\in R\}\), where \(c\) represents the “steepness” of the curve \(G'(u)\), the effectiveness of simulated annealing increases steadily with \(c\). These results suggest that on the average annealing is effective whenever most points have very small objective function values, but a few points have very large objective function values.


92D15 Problems related to evolution
65K10 Numerical optimization and variational techniques
49N70 Differential games and control
49N75 Pursuit and evasion games
Full Text: DOI EuDML