Towards a Complexity Theory of Randomized Search Heuristics: Ranking-Based Black-Box Complexity

DOI10.1007/978-3-642-20712-9_2zbMath1330.68110MaRDI QIDQ3007613

Benjamin Doerr, Carola Winzen

Publication date: 17 June 2011

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-20712-9_2

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C59: Approximation methods and heuristics in mathematical programming

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

68W20: Randomized algorithms

Related Items

Memory-restricted black-box complexity of OneMax, Towards a Complexity Theory of Randomized Search Heuristics: Ranking-Based Black-Box Complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Minimization algorithms and random walk on the d-cube
• Local optimization on graphs
• Lower bounds on the worst-case complexity of some oracle algorithms
• Black-box search by unbiased variation
• 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
• Black-box search by elimination of fitness functions
• Faster black-box algorithms through higher arity operators