Conference paper
Faster Black-Box Algorithms Through Higher Arity Operators
In
Foga '11 Proceedings of the 11th Workshop Proceedings on Foundations of Genetic Algorithms
—
2011, pp. 163-171
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).
| Language: | English |
|---|---|
| Publisher: | ACM |
| Year: | 2011 |
| Pages: | 163-171 |
| Proceedings: | 11th Foundations of Genetic Algorithms workshop Schwarzenberg |
| Journal subtitle: | Proceedings of the 2011 Acm/sigevo Foundations of Genetic Algorithms Xi |
| ISBN: | 1450306330 and 9781450306331 |
| Types: | Conference paper |
| DOI: | 10.1145/1967654.1967669 |
