Faster Black-Box Algorithms Through Higher Arity Operators

Benjamin Doerr, Daniel Johannsen, Timo Kötzing, Per Kristian Lehre, Markus Wagner, Carola Winzen

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    Abstract

    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
    Publication statusPublished - 2011
    Event11th Foundations of Genetic Algorithms workshop Schwarzenberg - Schwarzenberg, Austria
    Duration: 5 Jan 20119 Jan 2011
    Conference number: 11
    http://www.sigevo.org/foga-2011/index.html

    Workshop

    Workshop11th Foundations of Genetic Algorithms workshop Schwarzenberg
    Number11
    CountryAustria
    CitySchwarzenberg
    Period05/01/201109/01/2011
    Internet address

    Keywords

    • Pseudo-Boolean optimization
    • Runtime analysis
    • Black-box complexity
    • Theory

    Fingerprint Dive into the research topics of 'Faster Black-Box Algorithms Through Higher Arity Operators'. Together they form a unique fingerprint.

    Cite this