A Rigorous Runtime Analysis of the $(1+(\lambda ,\lambda ))$ GA on Jump Functions

Abstract

The $(1+(\lambda ,\lambda ))$ genetic algorithm is a younger evolutionary algorithm trying to profit also from inferior solutions. Rigorous runtime analyses on unimodal fitness functions showed that it can indeed be faster than classical evolutionary algorithms, though on these simple problems the gains were 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 \ollga optimizes any jump function with jump size $2\le k\le n/4$ 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 $\tilde{O}(n^{k-1})$ runtime guarantee. For the isolated problem of leaving the local optimum of jump functions, we determine provably optimal parameters that lead to a runtime of $(n/k{)}^{k/2}{e}^{\Theta (k)}$. This suggests some general advice on how to set the parameters of the \ollga, which might ease the further use of this algorithm.

The full version of the paper "The $(1+(\lambda ,\lambda ))$ GA Is Even Faster on Multimodal Problems" presented at GECCO 2020 containing all the proofs omitted in the conference paper

References in corpus (5)

• Self-Adjusting Evolutionary Algorithms for Multimodal Optimization
• Does Comma Selection Help To Cope With Local Optima
• The Runtime of the Compact Genetic Algorithm on Jump Functions
• Stagnation Detection with Randomized Local Search
• Runtime Analysis of a Heavy-Tailed $(1+(\lambda ,\lambda ))$ Genetic Algorithm on Jump Functions

Cited by in corpus (7)

• Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives
• Runtime Analysis for Permutation-based Evolutionary Algorithms
• Choosing the Right Algorithm With Hints From Complexity Theory
• How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs
• Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distribution
• First Steps Towards a Runtime Analysis When Starting With a Good Solution
• Multi-parameter Control for the $(1+(\lambda ,\lambda ))$-GA on OneMax via Deep Reinforcement Learning