Lower bounds on the run time of the univariate marginal distribution algorithm on OneMax

Martin S. Krejca; Carsten Witt

doi:10.1145/3040718.3040724

Lower bounds on the run time of the univariate marginal distribution algorithm on OneMax

Martin S. Krejca
, Carsten Witt

Department of Applied Mathematics and Computer Science

Hasso Plattner Institute for Software Systems Engineering

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

543 Downloads (Orbit)

Abstract

The Univariate Marginal Distribution Algorithm (UMDA), a popular estimation of distribution algorithm, is studied from a run time perspective. On the classical OneMax benchmark function, a lower bound of Ω(μ√n + n log n), where μ is the population size, on its expected run time is proved. This is the first direct lower bound on the run time of the UMDA. It is stronger than the bounds that follow from general black-box complexity theory and is matched by the run time of many evolutionary algorithms. The results are obtained through advanced analyses of the stochastic change of the frequencies of bit values maintained by the algorithm, including carefully designed potential functions. These techniques may prove useful in advancing the field of run time analysis for estimation of distribution algorithms in general.

Original language	English
Title of host publication	14th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms
Publisher	Association for Computing Machinery
Publication date	2017
Pages	65-79
ISBN (Print)	9781450346511
DOIs	https://doi.org/10.1145/3040718.3040724
Publication status	Published - 2017
Event	14th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms - Frederiksberg Campus, Copenhagen, Denmark Duration: 12 Jan 2017 → 15 Jan 2017

Conference

Conference	14th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms
Location	Frederiksberg Campus
Country/Territory	Denmark
City	Copenhagen
Period	12/01/2017 → 15/01/2017

Keywords

Computer Programming
Systems Science
Estimation of distribution algorithm
Lower bound
Run time analysis
Genetic algorithms
Heuristic algorithms
Population statistics
Stochastic systems
Advanced analysis
Benchmark functions
Black-box complexity
Estimation of distribution algorithms
Lower bounds
Potential function
Run-time analysis
Univariate marginal distribution algorithms
Evolutionary algorithms

Access to Document

10.1145/3040718.3040724

P65 krejcaFinal published version, 688 KB

OpenUrl availability

Full text

Cite this

@inproceedings{560d7e752a264e79b833c7bfea919222,

title = "Lower bounds on the run time of the univariate marginal distribution algorithm on OneMax",

abstract = "The Univariate Marginal Distribution Algorithm (UMDA), a popular estimation of distribution algorithm, is studied from a run time perspective. On the classical OneMax benchmark function, a lower bound of Ω(μ√n + n log n), where μ is the population size, on its expected run time is proved. This is the first direct lower bound on the run time of the UMDA. It is stronger than the bounds that follow from general black-box complexity theory and is matched by the run time of many evolutionary algorithms. The results are obtained through advanced analyses of the stochastic change of the frequencies of bit values maintained by the algorithm, including carefully designed potential functions. These techniques may prove useful in advancing the field of run time analysis for estimation of distribution algorithms in general.",

keywords = "Computer Programming, Systems Science, Estimation of distribution algorithm, Lower bound, Run time analysis, Genetic algorithms, Heuristic algorithms, Population statistics, Stochastic systems, Advanced analysis, Benchmark functions, Black-box complexity, Estimation of distribution algorithms, Lower bounds, Potential function, Run-time analysis, Univariate marginal distribution algorithms, Evolutionary algorithms",

author = "Krejca, \{Martin S.\} and Carsten Witt",

year = "2017",

doi = "10.1145/3040718.3040724",

language = "English",

isbn = "9781450346511",

pages = "65--79",

booktitle = "14th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms",

publisher = "Association for Computing Machinery",

address = "United States",

note = "14th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms, FOGA XIV ; Conference date: 12-01-2017 Through 15-01-2017",

}

TY - GEN

T1 - Lower bounds on the run time of the univariate marginal distribution algorithm on OneMax

AU - Krejca, Martin S.

AU - Witt, Carsten

PY - 2017

Y1 - 2017

N2 - The Univariate Marginal Distribution Algorithm (UMDA), a popular estimation of distribution algorithm, is studied from a run time perspective. On the classical OneMax benchmark function, a lower bound of Ω(μ√n + n log n), where μ is the population size, on its expected run time is proved. This is the first direct lower bound on the run time of the UMDA. It is stronger than the bounds that follow from general black-box complexity theory and is matched by the run time of many evolutionary algorithms. The results are obtained through advanced analyses of the stochastic change of the frequencies of bit values maintained by the algorithm, including carefully designed potential functions. These techniques may prove useful in advancing the field of run time analysis for estimation of distribution algorithms in general.

AB - The Univariate Marginal Distribution Algorithm (UMDA), a popular estimation of distribution algorithm, is studied from a run time perspective. On the classical OneMax benchmark function, a lower bound of Ω(μ√n + n log n), where μ is the population size, on its expected run time is proved. This is the first direct lower bound on the run time of the UMDA. It is stronger than the bounds that follow from general black-box complexity theory and is matched by the run time of many evolutionary algorithms. The results are obtained through advanced analyses of the stochastic change of the frequencies of bit values maintained by the algorithm, including carefully designed potential functions. These techniques may prove useful in advancing the field of run time analysis for estimation of distribution algorithms in general.

KW - Computer Programming

KW - Systems Science

KW - Estimation of distribution algorithm

KW - Lower bound

KW - Run time analysis

KW - Genetic algorithms

KW - Heuristic algorithms

KW - Population statistics

KW - Stochastic systems

KW - Advanced analysis

KW - Benchmark functions

KW - Black-box complexity

KW - Estimation of distribution algorithms

KW - Lower bounds

KW - Potential function

KW - Run-time analysis

KW - Univariate marginal distribution algorithms

KW - Evolutionary algorithms

U2 - 10.1145/3040718.3040724

DO - 10.1145/3040718.3040724

M3 - Article in proceedings

SN - 9781450346511

SP - 65

EP - 79

BT - 14th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms

PB - Association for Computing Machinery

T2 - 14th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms

Y2 - 12 January 2017 through 15 January 2017

ER -

Lower bounds on the run time of the univariate marginal distribution algorithm on OneMax

Abstract

Conference

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this