@inproceedings{bca2f6586f3d42ef90bbf27c597e9f0b,
title = "Faster black-box algorithms through higher arity operators",
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).",
keywords = "Black-box complexity, Pseudo-Boolean optimization, Runtime analysis, Theory",
author = "Benjamin Doerr and Daniel Johannsen and Timo K{\"o}tzing and Lehre, \{Per Kristian\} and Markus Wagner and Carola Winzen",
year = "2011",
month = may,
day = "20",
doi = "10.1145/1967654.1967669",
language = "English",
isbn = "9781450306331",
series = "FOGA'11 - Proceedings of the 2011 ACM/SIGEVO Foundations of Genetic Algorithms XI",
pages = "163--171",
booktitle = "FOGA'11 - Proceedings of the 2011 ACM/SIGEVO Foundations of Genetic Algorithms XI",
note = "11th Foundations of Genetic Algorithms Workshop, FOGA XI ; Conference date: 05-01-2011 Through 09-01-2011",
}