Please use this identifier to cite or link to this item:
https://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) (5 Jan 2011 - 9 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 |
DOI: | 10.1145/1967654.1967669 |
Published version: | http://doi.acm.org/10.1145/1967654.1967669 |
Appears in Collections: | Aurora harvest 8 Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
RA_hdl_108014.pdf Restricted Access | Restricted Access | 612.24 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.