Finding

Paper

Citations: 46

2010

Abstract

We give a simple and short alternative proof of the multiplicative drift theorem published recently (Doerr, Johannsen, Winzen (GECCO 2010)). It completely avoids the use of drift theorems previously used in the theory of evolutionary computation. By this, its proof is fully self-contained. The new theorem yields exactly the same bounds for expected runtimes as the previous theorem. In addition, it also gives good bounds on the deviations from the mean. This shows, for the first time, that the classical O(n log n) run-time bound for the (1+1) evolutionary algorithm for optimizing linear functions holds with high probability (and not just in expectation). Similar improvements are obtained for other classical problems in the evolutionary algorithms literature, for example computing minimum spanning trees, finding single-source shortest paths, and finding Eulerian cycles.

Authors

Benjamin Doerr, L. A. Goldberg

Journal

Journal name not available for this finding

copied to clipboard

copied to clipboard