Please use this identifier to cite or link to this item: http://hdl.handle.net/2440/108014
Citations
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) (05 Jan 2011 - 09 Jan 2011 : Schwarzenberg, Austria)
Statement of
Responsibility: 
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
RMID: 0030059120
DOI: 10.1145/1967654.1967669
Published version: http://doi.acm.org/10.1145/1967654.1967669
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_108014.pdfRestricted Access612.24 kBAdobe PDFView/Open


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