The (1+(λ, λ)) GA Is Even Faster on Multimodal Problems

For the (1 + (lambda, lambda)) genetic algorithm rigorous runtime analyses on unimodal fitness functions have shown that it can be faster than classical evolutionary algorithms, though on these simple problems the gains are only moderate. In this work, we conduct the first runtime analysis of this algorithm on a multimodal problem class, the jump functions benchmark. We show that with the right parameters, the (1 + (lambda, lambda)) GA optimizes any jump function with jump size 2 <= k <= n/16 in expected time O(n((k+1)/2)e(O(k))k(-k/2)), which significantly and already for constant k outperforms standard mutation-based algorithms with their Theta(n(k)) runtime and standard crossover-based algorithms with their O(n(k-1)) runtime. Our work also suggests some general advice on how to set the parameters of the (1 + (lambda, lambda)) GA, which might ease the further use of this algorithm.