Faster Black-Box Algorithms Through Higher Arity Operators

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2011

View graph of relations

We extend the work of Lehre and Witt (GECCO 2010) on the unbiased black-box model by considering higher arity variation operators. In particular, we show that already for binary operators the black-box complexity of LeadingOnes drops from (n2) for unary operators to O(n log n). For OneMax, the (n log n) unary black-box complexity drops to O(n) in the binary case. For k-ary operators, k n, the OneMax-complexity further decreases to O(n= log k).
Original languageEnglish
Title of host publicationFOGA '11 Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms
Publication date2011
Pages163-171
ISBN (print)978-1-4503-0633-1
DOIs
StatePublished

Workshop

Workshop11th Foundations of Genetic Algorithms workshop Schwarzenberg
Number11
CountryAustria
CitySchwarzenberg
Period05/01/1109/01/11
Internet addresshttp://www.sigevo.org/foga-2011/index.html
CitationsWeb of Science® Times Cited: No match on DOI

Keywords

  • Pseudo-Boolean optimization, Runtime analysis, Black-box complexity, Theory
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 5627172