## 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.

### MSC:

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