Faster Black-Box Algorithms Through Higher Arity Operators

Benjamin Doerr; Daniel Johannsen; Timo Kötzing; Per Kristian Lehre; Markus Wagner; Carola Winzen

doi:10.1145/1967654.1967669

Faster Black-Box Algorithms Through Higher Arity Operators

Benjamin Doerr
, Daniel Johannsen
, Timo Kötzing
, Per Kristian Lehre
, Markus Wagner
, Carola Winzen

Max Planck Institute

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

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).

Original language	English
Title of host publication	FOGA '11 Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms
Publication date	2011
Pages	163-171
ISBN (Print)	978-1-4503-0633-1
DOIs	https://doi.org/10.1145/1967654.1967669
Publication status	Published - 2011
Event	11th Foundations of Genetic Algorithms workshop Schwarzenberg - Schwarzenberg, Austria Duration: 5 Jan 2011 → 9 Jan 2011 Conference number: 11 http://www.sigevo.org/foga-2011/index.html

Workshop

Workshop	11th Foundations of Genetic Algorithms workshop Schwarzenberg
Number	11
Country/Territory	Austria
City	Schwarzenberg
Period	05/01/2011 → 09/01/2011
Internet address	http://www.sigevo.org/foga-2011/index.html

Keywords

Pseudo-Boolean optimization
Runtime analysis
Black-box complexity
Theory

Access to Document

10.1145/1967654.1967669

http://www.sigevo.org/foga-2011/index.html

OpenUrl availability

Check availability in DTU Findit

Cite this

@inproceedings{fd76e1aaef774ee0aa1938186af388ea,

title = "Faster Black-Box Algorithms Through Higher Arity Operators",

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 = "Pseudo-Boolean optimization, Runtime analysis, Black-box complexity, Theory",

author = "Benjamin Doerr and Daniel Johannsen and Timo K{\"o}tzing and Lehre, \{Per Kristian\} and Markus Wagner and Carola Winzen",

year = "2011",

doi = "10.1145/1967654.1967669",

language = "English",

isbn = "978-1-4503-0633-1",

pages = "163--171",

booktitle = "FOGA '11 Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms",

note = "11th Foundations of Genetic Algorithms workshop Schwarzenberg, FOGA 2011 ; Conference date: 05-01-2011 Through 09-01-2011",

url = "http://www.sigevo.org/foga-2011/index.html",

}

Doerr, B, Johannsen, D, Kötzing, T, Lehre, PK, Wagner, M & Winzen, C 2011, Faster Black-Box Algorithms Through Higher Arity Operators. in FOGA '11 Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms. pp. 163-171, 11th Foundations of Genetic Algorithms workshop Schwarzenberg, Schwarzenberg, Austria, 05/01/2011. https://doi.org/10.1145/1967654.1967669

TY - GEN

T1 - Faster Black-Box Algorithms Through Higher Arity Operators

AU - Doerr, Benjamin

AU - Johannsen, Daniel

AU - Kötzing, Timo

AU - Lehre, Per Kristian

AU - Wagner, Markus

AU - Winzen, Carola

N1 - Conference code: 11

PY - 2011

Y1 - 2011

N2 - 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).

AB - 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).

KW - Pseudo-Boolean optimization

KW - Runtime analysis

KW - Black-box complexity

KW - Theory

U2 - 10.1145/1967654.1967669

DO - 10.1145/1967654.1967669

M3 - Article in proceedings

SN - 978-1-4503-0633-1

SP - 163

EP - 171

BT - FOGA '11 Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms

T2 - 11th Foundations of Genetic Algorithms workshop Schwarzenberg

Y2 - 5 January 2011 through 9 January 2011

ER -

Faster Black-Box Algorithms Through Higher Arity Operators

Abstract

Workshop

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this