Faster Black-Box Algorithms Through Higher Arity Operators

2010/12/04 by Benjamin Doerr, Daniel Johannsen, Doerr, Benjamin +9 · 1 citation
Computer Science · #FOS: Computer and information sciences #Neural and Evolutionary Computing (cs.NE) #cs.NE

paper · pdf · doi:10.48550/arxiv.1012.0952

To appear at FOGA 2011

arxiv created 2010/12/04 · arxiv updated 2010/12/07

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 Θ(n²) 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).

Cited by

• Diversity-Preserving Exploitation of Crossover

Related

• Black-Box Complexity: Breaking the O(n log n) Barrier of LeadingOnes
• Reducing the Arity in Unbiased Black-Box Complexity
• The (1+1) Elitist Black-Box Complexity of LeadingOnes
• OneMax in Black-Box Models with Several Restrictions
• Unbiased Black-Box Complexities of Jump Functions