Analysis of a Simple Evolutionary Algorithm for the Minimization in Euclidian Spaces

Abstract

Although evolutionary algorithms (EAs) are widely used in practical optimization, their theoretical analysis is still in its infancy. Up to now results on expected runtimes and success probabilities are limited to discrete search spaces. In practice, however, EAs are mostly used for continuous optimization problems. First results on the expected runtime of a simple, but fundamental EA minimizing a symmetric polynomial of degree two in Rn are presented. Namely, the so-called (1+1) evolution strategy ((1+1) ES) minimizing the SPHERE function is investigated. A lower bound on the expected runtime is shown that is valid for any m