2011 · 73 citations · 7 references
ComputingComputer ScienceMathematicsAlgorithmsMachine LearningTheory Of ComputationAlgorithm AnalysisAlgorithmic ComplexityBoolean AlgebraComputational ComplexityRandomized ComplexityRandomized ComputationOperators
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).
7
Introduction to algorithms [2nd ed.]
Thomas H. Cormen · 2001 · 1.9K citations
Morgan Kaufmann Publishers, Inc.
IEEE Software · 1986 · 311 citations
Fred H. Menko, Hans F. A. Vasen, Henry T. Lynch · Annals of Oncology · 2001 · 90 citations