Memory-restricted black-box complexity of OneMax

DOI10.1016/J.IPL.2011.10.004MaRDI QIDQ763484zbMATH OpenOpenAlexFDO

Authors Benjamin Doerr, Carola Winzen

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

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

Recommendations

• \textsc{OneMax} in black-box models with several restrictions
• Black-box complexity: advantages of memory usage
• Reducing the arity in unbiased black-box complexity
• The (1+1) elitist black-box complexity of LeadingOnes
• Playing Mastermind with constant-size memory

Cites work

• scientific article; zbMATH DE number 5686753 (Why is no real title available?)
• scientific article; zbMATH DE number 3194843 (Why is no real title available?)
• Complexity measures and decision tree complexity: a survey.
• On the analysis of the \((1+1)\) evolutionary algorithm
• Towards a complexity theory of randomized search heuristics: ranking-based black-box complexity
• Upper and lower bounds for randomized search heuristics in black-box optimization

Cited in

(8)

• Black-box complexity: advantages of memory usage
• Optimal parameter choices via precise black-box analysis
• The (1+1) elitist black-box complexity of LeadingOnes
• Playing several variants of Mastermind with constant-size memory is not harder than with unbounded memory
• \textsc{OneMax} in black-box models with several restrictions
• The unbiased black-box complexity of partition is polynomial
• Playing mastermind with constant-size memory
• Reducing the arity in unbiased black-box complexity

This page was built for publication: Memory-restricted black-box complexity of OneMax

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