Why comma selection can help with the escape from local optima

Abstract

We investigate (1,lambda) ESs using isotropic mutations for optimization in R^n by means of a theoretical runtime analysis. In particular, a constant offspring-population size lambda will be of interest. We start off by considering an adaptation-less (1,2) ES minimizing a linear function. Subsequently, a piecewise linear function with a jump/cliff is considered, where a (1+lambda) ES gets trapped, i. e., (at least) an exponential (in n) number of steps are necessary to escape the local-optimum region. The (1,2) ES, however, manages to overcome the cliff in an almost unnoticeable number of steps. Finally, we outline (because of the page limit) how the reasoning and the calculations can be extended to the scenario where a (1,lambda) ES using Gaussian mutations minimizes Cliff, a bimodal, spherically symmetric function already considered in the literature, which is merely Sphere with a jump in the function value at a certain distance from the minimum. For lambda a constant large enough, the (1,lambda) ES manages to conquer the global-optimum region { in contrast to (1+lambda) ESs which get trapped.