Tight bounds on the expected runtime of a standard steady state genetic algorithm

DOI10.1007/S00453-021-00893-WMaRDI QIDQ2144273zbMATH OpenOpenAlexFDO

Authors Pietro S. Oliveto, Dirk Sudholt, Carsten Witt

Publication date 1 June 2022

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-021-00893-w

zbMATH Keywords

crossoverlower boundsevolutionary algorithmsruntime analysis

Mathematics Subject Classification ID

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

Recommendations

• On the benefits of populations for the exploitation speed of standard steady-state genetic algorithms
• On the runtime analysis of the simple genetic algorithm
• Optimal mutation rates for the (1+) EA on OneMax through asymptotically tight drift analysis
• A tight runtime analysis for the \((\mu + \lambda)\) EA
• A tight runtime analysis for the \((1+(\lambda,\lambda))\) GA on LeadingOnes

Cites work

• scientific article; zbMATH DE number 194544 (Why is no real title available?)
• scientific article; zbMATH DE number 5686753 (Why is no real title available?)
• scientific article; zbMATH DE number 3273551 (Why is no real title available?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A note on the mean deviation of the binomial distribution
• Analyzing evolutionary algorithms. The computer science perspective.
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Black-box search by unbiased variation
• Crossover can be constructive when computing unique input-output sequences
• Crossover can provably be useful in evolutionary computation
• Fixed-parameter tractability of crossover: steady-state GAs on the closest string problem
• Improved time complexity analysis of the simple genetic algorithm
• On the benefits of populations for the exploitation speed of standard steady-state genetic algorithms
• On the runtime analysis of the simple genetic algorithm
• The analysis of evolutionary algorithms -- A proof that crossover really can help
• Theory of evolutionary computation. Recent developments in discrete optimization
• Tight bounds on the optimization time of a randomized search heuristic on linear functions

Cited in

(5)

• An exponential lower bound for the runtime of the compact genetic algorithm on jump functions
• Crossover can guarantee exponential speed-ups in evolutionary multi-objective optimisation
• The cost of randomness in evolutionary algorithms: crossover can save random bits
• Analysing equilibrium states for population diversity
• The runtime of the compact genetic algorithm on jump functions

This page was built for publication: Tight bounds on the expected runtime of a standard steady state genetic algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2144273)