The \((1+1)\) elitist black-box complexity of LeadingOnes

DOI10.1007/s00453-017-0304-6zbMath1391.68050arXiv1604.02355MaRDI QIDQ1750359

Johannes Lengler, Carola Doerr

Publication date: 18 May 2018

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

evolutionary algorithms; query complexity; truncation selection; black-box complexity; elitist algorithm; LeadingOnes; memory restriction

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Related Items

The query complexity of a permutation-based variant of mastermind, The \((1+1)\) elitist black-box complexity of LeadingOnes, Analyzing randomized search heuristics via stochastic domination

Cites Work

• Unnamed Item
• Unnamed Item
• Ranking-based black-box complexity
• On the analysis of the \((1+1)\) evolutionary algorithm
• The \((1+1)\) elitist black-box complexity of LeadingOnes
• Black-box search by unbiased variation
• Playing mastermind with constant-size memory
• \textsc{OneMax} in black-box models with several restrictions
• Upper and lower bounds for randomized search heuristics in black-box optimization
• The Query Complexity of Finding a Hidden Permutation
• Faster black-box algorithms through higher arity operators
• Asymptotic Hitting Time for a Simple Evolutionary Model of Protein Folding