Sharp bounds on the runtime of the (1+1) EA via drift analysis and analytic combinatorial tools

DOI10.1145/3299904.3340302zbMath1433.68645arXiv1906.09047OpenAlexW2969868371MaRDI QIDQ5215475

Carsten Witt, Hsien-Kuei Hwang

Publication date: 11 February 2020

Published in: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

asymptotic methodsdrift analysisrandomized search heuristics(1+1) EA

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Evolutionary algorithms, genetic algorithms (computational aspects) (68W50) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)

Related Items (3)

Runtime analysis for self-adaptive mutation rates ⋮ Lower bounds from fitness levels made easy ⋮ How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys

This page was built for publication: Sharp bounds on the runtime of the (1+1) EA via drift analysis and analytic combinatorial tools