Simplified runtime analysis of estimation of distribution algorithms

Duc Cuong Dang; Per Kristian Lehre

doi:10.1145/2739480.2754814

Simplified runtime analysis of estimation of distribution algorithms

Duc Cuong Dang, Per Kristian Lehre

Computer Science

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

30 Citations (Scopus)

Abstract

Estimation of distribution algorithms (EDA) are stochastic search methods that look for optimal solutions by learning and sampling from probabilistic models. Despite their popularity, there are only few rigorous theoretical analyses of their performance. Even for the simplest EDAs, such as the Univariate Marginal Distribution Algorithm (UMDA) which assumes independence between decision variables, there are only a handful of results about its runtime, and results for simple functions such as OneMax are still missing. In this paper, we show that the recently developed levelbased theorem for non-elitist populations is directly applicable to runtime analysis of EDAs. To demonstrate this approach, we derive easily upper bounds on the expected runtime of the UMDA.

Original language	English
Title of host publication	GECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference
Publisher	Association for Computing Machinery
Pages	513-518
Number of pages	6
ISBN (Electronic)	9781450334723
DOIs	https://doi.org/10.1145/2739480.2754814
Publication status	Published - 11 Jul 2015
Event	16th Genetic and Evolutionary Computation Conference, GECCO 2015 - Madrid, Spain Duration: 11 Jul 2015 → 15 Jul 2015

Conference

Conference	16th Genetic and Evolutionary Computation Conference, GECCO 2015
Country/Territory	Spain
City	Madrid
Period	11/07/15 → 15/07/15

Keywords

Estimation of distribution algorithm
Level-based analysis
Runtime analysis

ASJC Scopus subject areas

Computational Theory and Mathematics
Computer Science Applications
Software

Access to Document

10.1145/2739480.2754814Licence: None: All rights reserved

Cite this

@inproceedings{bd533685b25d43ce82bec2d373ca862d,

title = "Simplified runtime analysis of estimation of distribution algorithms",

abstract = "Estimation of distribution algorithms (EDA) are stochastic search methods that look for optimal solutions by learning and sampling from probabilistic models. Despite their popularity, there are only few rigorous theoretical analyses of their performance. Even for the simplest EDAs, such as the Univariate Marginal Distribution Algorithm (UMDA) which assumes independence between decision variables, there are only a handful of results about its runtime, and results for simple functions such as OneMax are still missing. In this paper, we show that the recently developed levelbased theorem for non-elitist populations is directly applicable to runtime analysis of EDAs. To demonstrate this approach, we derive easily upper bounds on the expected runtime of the UMDA.",

keywords = "Estimation of distribution algorithm, Level-based analysis, Runtime analysis",

author = "Dang, {Duc Cuong} and Lehre, {Per Kristian}",

year = "2015",

month = jul,

day = "11",

doi = "10.1145/2739480.2754814",

language = "English",

pages = "513--518",

booktitle = "GECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference",

publisher = "Association for Computing Machinery ",

note = "16th Genetic and Evolutionary Computation Conference, GECCO 2015 ; Conference date: 11-07-2015 Through 15-07-2015",

}

TY - GEN

T1 - Simplified runtime analysis of estimation of distribution algorithms

AU - Dang, Duc Cuong

AU - Lehre, Per Kristian

PY - 2015/7/11

Y1 - 2015/7/11

N2 - Estimation of distribution algorithms (EDA) are stochastic search methods that look for optimal solutions by learning and sampling from probabilistic models. Despite their popularity, there are only few rigorous theoretical analyses of their performance. Even for the simplest EDAs, such as the Univariate Marginal Distribution Algorithm (UMDA) which assumes independence between decision variables, there are only a handful of results about its runtime, and results for simple functions such as OneMax are still missing. In this paper, we show that the recently developed levelbased theorem for non-elitist populations is directly applicable to runtime analysis of EDAs. To demonstrate this approach, we derive easily upper bounds on the expected runtime of the UMDA.

AB - Estimation of distribution algorithms (EDA) are stochastic search methods that look for optimal solutions by learning and sampling from probabilistic models. Despite their popularity, there are only few rigorous theoretical analyses of their performance. Even for the simplest EDAs, such as the Univariate Marginal Distribution Algorithm (UMDA) which assumes independence between decision variables, there are only a handful of results about its runtime, and results for simple functions such as OneMax are still missing. In this paper, we show that the recently developed levelbased theorem for non-elitist populations is directly applicable to runtime analysis of EDAs. To demonstrate this approach, we derive easily upper bounds on the expected runtime of the UMDA.

KW - Estimation of distribution algorithm

KW - Level-based analysis

KW - Runtime analysis

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

U2 - 10.1145/2739480.2754814

DO - 10.1145/2739480.2754814

M3 - Conference contribution

AN - SCOPUS:84963642070

SP - 513

EP - 518

BT - GECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference

PB - Association for Computing Machinery

T2 - 16th Genetic and Evolutionary Computation Conference, GECCO 2015

Y2 - 11 July 2015 through 15 July 2015

ER -

Simplified runtime analysis of estimation of distribution algorithms

Abstract

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this