Faster black-box algorithms through higher arity operators

Benjamin Doerr; Daniel Johannsen; Timo Kö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 Kötzing, Per Kristian Lehre, Markus Wagner, Carola Winzen

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

48 Citations (Scopus)

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 θ(n²) 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 2011 ACM/SIGEVO Foundations of Genetic Algorithms XI
Pages	163-171
Number of pages	9
DOIs	https://doi.org/10.1145/1967654.1967669
Publication status	Published - 2011
Event	11th Foundations of Genetic Algorithms Workshop, FOGA XI - Schwarzenberg, Austria Duration: 5 Jan 2011 → 9 Jan 2011

Conference

Conference	11th Foundations of Genetic Algorithms Workshop, FOGA XI
Country/Territory	Austria
City	Schwarzenberg
Period	5/01/11 → 9/01/11

Keywords

Black-box complexity
Pseudo-Boolean optimization
Runtime analysis
Theory

ASJC Scopus subject areas

Computational Theory and Mathematics
Theoretical Computer Science

Access to Document

10.1145/1967654.1967669

Cite this

@inproceedings{e57f740635904a9bbdeec477d50cbd1f,

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

pages = "163--171",

booktitle = "FOGA'11 - Proceedings of the 2011 ACM/SIGEVO Foundations of Genetic Algorithms XI",

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

}

TY - GEN

T1 - Faster black-box algorithms through higher arity operators

AU - Doerr, Benjamin

AU - Johannsen, Daniel

AU - Kötzing, Timo

AU - Lehre, Per Kristian

AU - Wagner, Markus

AU - Winzen, Carola

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 - Black-box complexity

KW - Pseudo-Boolean optimization

KW - Runtime analysis

KW - Theory

UR - http://www.scopus.com/inward/record.url?scp=79955999294&partnerID=8YFLogxK

U2 - 10.1145/1967654.1967669

DO - 10.1145/1967654.1967669

M3 - Conference contribution

AN - SCOPUS:79955999294

SN - 9781450306331

SP - 163

EP - 171

BT - FOGA'11 - Proceedings of the 2011 ACM/SIGEVO Foundations of Genetic Algorithms XI

T2 - 11th Foundations of Genetic Algorithms Workshop, FOGA XI

Y2 - 5 January 2011 through 9 January 2011

ER -

Faster black-box algorithms through higher arity operators

Abstract

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this