Faster Black-Box Algorithms Through Higher Arity Operators

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

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 Theta(n^2) for unary operators to O(n log n). For
OneMax, the Omega(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).