On the complexity of overcoming gaps with isotropic mutations and elitist selection

We consider the (1+lambda) evolution strategy, an evolutionary algorithm for minimization in Ropfⁿ, using isotropic mutations. Thus, for instance, Gaussian mutations adapted by the 1/5-rule or by sigma-self-adaptation are covered. Lower bounds on the (expected) runtime (defined as the number of function evaluations) to overcome a gap in the search space are proved (where the search faces a gap of size Delta if the distance between the current search point and the set of all better points is at least Delta), showing when the runtime is potentially polynomial and when the runtime is necessarily super-polynomial or even necessarily exponential in n, the dimensionality of the search space