Memory-restricted black-box complexity of OneMax

DOI10.1016/j.ipl.2011.10.004zbMath1233.68235OpenAlexW1991060790MaRDI QIDQ763484

Carola Winzen, Benjamin Doerr

Publication date: 9 March 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2011.10.004

zbMATH Keywords

query complexitybounded memoryblack-box algorithmsblack-box complexity

Mathematics Subject Classification ID

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

Related Items

Playing Several Variants of Mastermind with Constant-Size Memory is not Harder than with Unbounded Memory ⋮ The unbiased black-box complexity of partition is polynomial ⋮ Reducing the arity in unbiased black-box complexity ⋮ Playing mastermind with constant-size memory ⋮ Optimal parameter choices via precise black-box analysis

Cites Work

• Unnamed Item
• Unnamed Item
• On the analysis of the \((1+1)\) evolutionary algorithm
• Complexity measures and decision tree complexity: a survey.
• Upper and lower bounds for randomized search heuristics in black-box optimization
• Towards a Complexity Theory of Randomized Search Heuristics: Ranking-Based Black-Box Complexity