Improved runtime bounds for the univariate marginal distribution algorithm via anti-concentration

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Standard

Improved runtime bounds for the univariate marginal distribution algorithm via anti-concentration. / Lehre, Per Kristian; Nguyen, Phan Trung Hai.

GECCO '17 Proceedings of the Genetic and Evolutionary Computation Conference. Association for Computing Machinery , 2017. p. 1383-1390.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Harvard

Lehre, PK & Nguyen, PTH 2017, Improved runtime bounds for the univariate marginal distribution algorithm via anti-concentration. in GECCO '17 Proceedings of the Genetic and Evolutionary Computation Conference. Association for Computing Machinery , pp. 1383-1390, GECCO 2017:, Berlin, Germany, 15/07/17. https://doi.org/10.1145/3071178.3071317

APA

Lehre, P. K., & Nguyen, P. T. H. (2017). Improved runtime bounds for the univariate marginal distribution algorithm via anti-concentration. In GECCO '17 Proceedings of the Genetic and Evolutionary Computation Conference (pp. 1383-1390). Association for Computing Machinery . https://doi.org/10.1145/3071178.3071317

Vancouver

Lehre PK, Nguyen PTH. Improved runtime bounds for the univariate marginal distribution algorithm via anti-concentration. In GECCO '17 Proceedings of the Genetic and Evolutionary Computation Conference. Association for Computing Machinery . 2017. p. 1383-1390 https://doi.org/10.1145/3071178.3071317

Author

Lehre, Per Kristian ; Nguyen, Phan Trung Hai. / Improved runtime bounds for the univariate marginal distribution algorithm via anti-concentration. GECCO '17 Proceedings of the Genetic and Evolutionary Computation Conference. Association for Computing Machinery , 2017. pp. 1383-1390

Bibtex

@inproceedings{3c724198565448049da49e133a0a37db,
title = "Improved runtime bounds for the univariate marginal distribution algorithm via anti-concentration",
abstract = "Unlike traditional evolutionary algorithms which produce offspring via genetic operators, Estimation of Distribution Algorithms (EDAs) sample solutions from probabilistic models which are learned from selected individuals. It is hoped that EDAs may improve optimisation performance on epistatic fitness landscapes by learning variable interactions. However, hardly any rigorous results are available to support claims about the performance of EDAs, even for fitness functions without epistasis. The expected runtime of the Univariate Marginal Distribution Algorithm (UMDA) on OneMax was recently shown to be in O (nX log X) [9]. Later, Krejca and Witt proved the lower bound Q (Xs/n + n log n) via an involved drift analysis [16]. We prove a O (nX) bound, given some restrictions on the population size. This implies the tight bound 8 (n log n) when X = O (log n), matching the runtime of classical EAs. Our analysis uses the level-based theorem and anti-concentration properties of the Poisson-binomial distribution. We expect that these generic methods will facilitate further analysis of EDAs.",
keywords = "Runtime Analysis, Level-based Analysis, Estimation of Distribution Algorithms",
author = "Lehre, {Per Kristian} and Nguyen, {Phan Trung Hai}",
year = "2017",
month = jul,
day = "1",
doi = "10.1145/3071178.3071317",
language = "English",
isbn = "978-1-4503-4920-8",
pages = "1383--1390",
booktitle = "GECCO '17 Proceedings of the Genetic and Evolutionary Computation Conference",
publisher = "Association for Computing Machinery ",
note = "GECCO 2017: : The Genetic and Evolutionary Computation Conference ; Conference date: 15-07-2017 Through 19-07-2017",
url = "http://gecco-2017.sigevo.org/index.html/HomePage",

}

RIS

TY - GEN

T1 - Improved runtime bounds for the univariate marginal distribution algorithm via anti-concentration

AU - Lehre, Per Kristian

AU - Nguyen, Phan Trung Hai

PY - 2017/7/1

Y1 - 2017/7/1

N2 - Unlike traditional evolutionary algorithms which produce offspring via genetic operators, Estimation of Distribution Algorithms (EDAs) sample solutions from probabilistic models which are learned from selected individuals. It is hoped that EDAs may improve optimisation performance on epistatic fitness landscapes by learning variable interactions. However, hardly any rigorous results are available to support claims about the performance of EDAs, even for fitness functions without epistasis. The expected runtime of the Univariate Marginal Distribution Algorithm (UMDA) on OneMax was recently shown to be in O (nX log X) [9]. Later, Krejca and Witt proved the lower bound Q (Xs/n + n log n) via an involved drift analysis [16]. We prove a O (nX) bound, given some restrictions on the population size. This implies the tight bound 8 (n log n) when X = O (log n), matching the runtime of classical EAs. Our analysis uses the level-based theorem and anti-concentration properties of the Poisson-binomial distribution. We expect that these generic methods will facilitate further analysis of EDAs.

AB - Unlike traditional evolutionary algorithms which produce offspring via genetic operators, Estimation of Distribution Algorithms (EDAs) sample solutions from probabilistic models which are learned from selected individuals. It is hoped that EDAs may improve optimisation performance on epistatic fitness landscapes by learning variable interactions. However, hardly any rigorous results are available to support claims about the performance of EDAs, even for fitness functions without epistasis. The expected runtime of the Univariate Marginal Distribution Algorithm (UMDA) on OneMax was recently shown to be in O (nX log X) [9]. Later, Krejca and Witt proved the lower bound Q (Xs/n + n log n) via an involved drift analysis [16]. We prove a O (nX) bound, given some restrictions on the population size. This implies the tight bound 8 (n log n) when X = O (log n), matching the runtime of classical EAs. Our analysis uses the level-based theorem and anti-concentration properties of the Poisson-binomial distribution. We expect that these generic methods will facilitate further analysis of EDAs.

KW - Runtime Analysis

KW - Level-based Analysis

KW - Estimation of Distribution Algorithms

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

U2 - 10.1145/3071178.3071317

DO - 10.1145/3071178.3071317

M3 - Conference contribution

AN - SCOPUS:85026369061

SN - 978-1-4503-4920-8

SP - 1383

EP - 1390

BT - GECCO '17 Proceedings of the Genetic and Evolutionary Computation Conference

PB - Association for Computing Machinery

T2 - GECCO 2017:

Y2 - 15 July 2017 through 19 July 2017

ER -