English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Ranking-based Black-box Complexity

MPS-Authors
/persons/resource/persons44338

Doerr,  Benjamin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45750

Doerr,  Carola
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Doerr, B., & Doerr, C. (2014). Ranking-based Black-box Complexity. Algorithmica, 68(3), 571-609. doi:10.1007/s00453-012-9684-9.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0019-8407-2
Abstract
Randomized search heuristics such as evolutionary algorithms, simulated annealing, and ant colony optimization are a broadly used class of general-purpose algorithms. Analyzing them via classical methods of theoretical computer science is a growing field. While several strong runtime analysis results have appeared in the last 20 years, a powerful complexity theory for such algorithms is yet to be developed. We enrich the existing notions of black-box complexity by the additional restriction that not the actual objective values, but only the relative quality of the previously evaluated solutions may be taken into account by the black-box algorithm. Many randomized search heuristics belong to this class of algorithms. We show that the new ranking-based model can give more realistic complexity estimates. The class of all binary-value functions has a black-box complexity of O(\log n) in the previous black-box models, but has a ranking-based complexity of \Theta(n). On the other hand, for the class of all \onemax functions, we present a ranking-based black-box algorithm that has a runtime of \Theta(n / \log n), which shows that the \onemax problem does not become harder with the additional ranking-basedness restriction.