Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Faster black-box algorithms through higher arity operators
Author: Doerr, B.
Johannsen, D.
Kötzing, T.
Lehre, P.
Wagner, M.
Winzen, C.
Citation: Proceedings of the 11th Workshop Proceedings on Foundations of Genetic Algorithms, 2011, pp.163-172
Publisher: ACM Press
Issue Date: 2011
Series/Report no.: FOGA ’11
ISBN: 9781450306331
Conference Name: 11th workshop proceedings on Foundations of genetic algorithms (FOGA) (5 Jan 2011 - 9 Jan 2011 : Schwarzenberg, Austria)
Statement of
Benjamin Doerr Daniel Johannsen Timo Kötzing Per Kristian Lehre Markus Wagner Timo Kötzing Carola Winzen
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; runtime analysis; pseudo-Boolean optimization; theory
Rights: Copyright 2011 ACM
DOI: 10.1145/1967654.1967669
Published version:
Appears in Collections:Aurora harvest 8
Computer Science publications

Files in This Item:
File Description SizeFormat 
  Restricted Access
Restricted Access612.24 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.