Probabilistic runtime analysis of (1 +over, λ),ES using isotropic mutations

摘要

We consider the (1+λ)ES and the (1+λ)ES, which are simple evolutionary algorithms for minimization in Rⁿ, using isotropic mutations. General lower bounds on the number of mutations that are necessary to reduce the approximation error in the search space, ie the distance from the optimum (or from any other fixed point in the search space), are proved. Therefore, we generalize a lower-bound method recently introduced by Witt in a runtime analysis of the (μ+1)EA for the search space {0,1}ⁿ, which was also already successfully applied in an analysis of a (μ+1)ES. Namely, we prove that both, the (1+λ)ES as well as the (1+λ)ES need Ω(n•λ/√lnλ) function evaluations with an overwhelming probability to halve the approximation error in the search space - independently of how the isotropic mutations are adapted and of the function to be optimized.On the other hand, for an upper bound we consider the following concrete scenario: the minimization of the well-known SPHERE-function using Gaussian mutation vectors adapted by the 1/5-rule. We prove that the (1+λ)ES needs Ω(n•λ/√lnλ). SPHERE-evaluations with an overwhelming probability to halve the approximation error. Moreover, by some kind of reduction, we show that this upper bound also holds for the (1,λ)ES.Finally, the gap of size O(√lnλ) between the lower bound and the upper bound is discussed.