Ranking-based black-box complexity

DOI10.1007/s00453-012-9684-9zbMath1360.68505arXiv1102.1140OpenAlexW3100828115MaRDI QIDQ528852

Benjamin Doerr, Carola Winzen

Publication date: 17 May 2017

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

query complexitytheory of randomized search heuristicsblack-box complexitymastermind

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)

Related Items

Black-box complexity: advantages of memory usage, On the benefits and risks of using fitness sharing for multimodal optimisation, The unbiased black-box complexity of partition is polynomial, From black-box complexity to designing new genetic algorithms, Comprehensive characterization of the behaviors of estimation of distribution algorithms, The runtime of the compact genetic algorithm on jump functions, The \((1+1)\) elitist black-box complexity of LeadingOnes, Optimal parameter choices via precise black-box analysis, Working principles of binary differential evolution

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds for comparison based evolution strategies using VC-dimension and sign patterns
• Mastermind
• Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
• On the algorithmic complexity of the Mastermind game with black-peg results
• Minimization algorithms and random walk on the d-cube
• Local optimization on graphs
• On the analysis of the \((1+1)\) evolutionary algorithm
• Black-box search by unbiased variation
• Upper and lower bounds for randomized search heuristics in black-box optimization
• New upper and lower bounds for randomized and quantum local search
• Towards a Complexity Theory of Randomized Search Heuristics: Ranking-Based Black-Box Complexity
• A Remark on Stirling's Formula
• Lower bounds for local search by quantum arguments
• Black-box search by elimination of fitness functions
• Faster black-box algorithms through higher arity operators
• Concentration of Measure for the Analysis of Randomized Algorithms