Convergence Analysis of Evolution Strategies with Random Numbers of Offspring

Abstract. Hitting times of the global optimum for evolutionary algo-rithms are usually available for simple unimodal problems or for simpli-fied algorithms. In discrete problems, the number of results that relate the convergence rate of evolution strategies to the geometry of the opti-misation landscape is restricted to a few theoretical studies. This article introduces a variant of the canonical (µ+ λ)-ES, called the Poisson-ES, for which the number of offspring is not deterministic, but is instead sampled from a Poisson distribution with mean λ. After a slight change on the rank-based selection for the µ parents, and assuming that the number of offspring is small, we show that the convergence rate of the new algorithm is dependent on a geometric quantity that measures the maximal width of adaptive valleys. The argument of the proof is based on the analogy of the Poisson-ES with a basic Mutation-or-Selection evolutionary strategy introduced in a previous work