A rigorous runtime analysis of the \((1 + (\lambda, \lambda))\) GA on jump functions

DOI10.1007/s00453-021-00907-7OpenAlexW3186197777MaRDI QIDQ2144272

Vitalii Karavaev, Benjamin Doerr, Denis Antipov

Publication date: 1 June 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2004.06702

zbMATH Keywords

evolutionary algorithmstheorycrossoverruntime analysisparameters tuning

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Evolutionary algorithms, genetic algorithms (computational aspects) (68W50)

Related Items (6)

Choosing the right algorithm with hints from complexity theory ⋮ Lower bounds from fitness levels made easy ⋮ Lazy parameter tuning and control: choosing all parameters randomly from a power-law distribution ⋮ Runtime analysis for permutation-based evolutionary algorithms ⋮ Using Automated Algorithm Configuration for Parameter Control ⋮ How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys

Cites Work

• Unnamed Item
• Crossover can provably be useful in evolutionary computation
• From black-box complexity to designing new genetic algorithms
• Real royal road functions for constant population size
• On the analysis of the \((1+1)\) evolutionary algorithm
• An elementary analysis of the probability that a binomial random variable exceeds its expectation
• Optimal static and self-adjusting parameter choices for the \((1+(\lambda ,\lambda ))\) genetic algorithm
• The analysis of evolutionary algorithms -- A proof that crossover really can help
• Black-box search by unbiased variation
• The univariate marginal distribution algorithm copes well with deception and epistasis
• Stagnation detection with randomized local search
• The runtime of the compact genetic algorithm on jump functions
• The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm
• Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas
• Upper and lower bounds for randomized search heuristics in black-box optimization
• A tight runtime analysis for the \((\mu + \lambda)\) EA
• On the Black-Box Complexity of Example Functions
• Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions
• On crossing fitness valleys with majority-vote crossover and estimation-of-distribution algorithms
• The benefits and limitations of voting mechanisms in evolutionary optimisation
• A tight runtime analysis for the (1 + (λ, λ)) GA on leadingones
• Theory of Evolutionary Computation

This page was built for publication: A rigorous runtime analysis of the \((1 + (\lambda, \lambda))\) GA on jump functions