On the limitations of the univariate marginal distribution algorithm to deception and where bivariate EDAs might help

Per Kristian Lehre; Phan Trung Hai Nguyen

doi:10.1145/3299904.3340316

On the limitations of the univariate marginal distribution algorithm to deception and where bivariate EDAs might help

Per Kristian Lehre, Phan Trung Hai Nguyen

Computer Science

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

9 Citations (Scopus)

169 Downloads (Pure)

Abstract

We introduce a new benchmark problem called Deceptive Leading Blocks (DLB) to rigorously study the runtime of the Univariate Marginal Distribution Algorithm (UMDA) in the presence of epistasis and deception. We show that simple Evolutionary Algorithms (EAs) outperform the UMDA unless the selective pressure μ/λ is extremely high, where μ and λ are the parent and offspring population sizes, respectively. More precisely, we show that the UMDA with a parent population size of μ=Ω(logn) has an expected runtime of e^Ω(μ)on the DLB problem assuming any selective pressure μ/λ ≥14/1000, as opposed to the expected runtime of O(nλlogλ+n³) for the non-elitist (μ,λ) EA with μ/λ≤1/e. These results illustrate inherent limitations of univariate EDAs against deception and epistasis, which are common characteristics of real-world problems. In contrast, empirical evidence reveals the efficiency of the bi-variate MIMIC algorithm on the DLB problem. Our results suggest that one should consider EDAs with more complex probabilistic models when optimising problems with some degree of epistasis and deception.

Original language	English
Title of host publication	Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA '19)
Place of Publication	New York, NY, USA
Publisher	Association for Computing Machinery (ACM)
Pages	154-168
Number of pages	15
ISBN (Electronic)	978-1-4503-6254-2
DOIs	https://doi.org/10.1145/3299904.3340316
Publication status	Published - 27 Aug 2019
Event	15th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XV) - Hasso Plattner Institute, Potsdam, Germany Duration: 27 Aug 2019 → 29 Aug 2019

Conference

Conference	15th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XV)
Abbreviated title	FOGA 2019
Country/Territory	Germany
City	Potsdam
Period	27/08/19 → 29/08/19

Keywords

Running time analysis
deception
deceptive leading blocks
epistasis
theory
univariate marginal distribution algorithm

Access to Document

10.1145/3299904.3340316Licence: None: All rights reserved

Lehre_&_Nguyen_On_the_limitations_of_the_univariate_marginal_distribution_algorithm_FOGA_2019
Checked for eligibility: 13/09/2019 © Owner/Author 2019. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA '19), http://dx.doi.org/10.1145/3299904.3340316.
Accepted author manuscript, 491 KBLicence: Other (please specify with Rights Statement)

Cite this

@inproceedings{8f5310e999c54cd0b73be04b9190a5eb,

title = "On the limitations of the univariate marginal distribution algorithm to deception and where bivariate EDAs might help",

abstract = "We introduce a new benchmark problem called Deceptive Leading Blocks (DLB) to rigorously study the runtime of the Univariate Marginal Distribution Algorithm (UMDA) in the presence of epistasis and deception. We show that simple Evolutionary Algorithms (EAs) outperform the UMDA unless the selective pressure μ/λ is extremely high, where μ and λ are the parent and offspring population sizes, respectively. More precisely, we show that the UMDA with a parent population size of μ=Ω(logn) has an expected runtime of eΩ(μ) on the DLB problem assuming any selective pressure μ/λ ≥14/1000, as opposed to the expected runtime of O(nλlogλ+n3) for the non-elitist (μ,λ) EA with μ/λ≤1/e. These results illustrate inherent limitations of univariate EDAs against deception and epistasis, which are common characteristics of real-world problems. In contrast, empirical evidence reveals the efficiency of the bi-variate MIMIC algorithm on the DLB problem. Our results suggest that one should consider EDAs with more complex probabilistic models when optimising problems with some degree of epistasis and deception.",

keywords = "Running time analysis, deception, deceptive leading blocks, epistasis, theory, univariate marginal distribution algorithm",

author = "Lehre, {Per Kristian} and Nguyen, {Phan Trung Hai}",

year = "2019",

month = aug,

day = "27",

doi = "10.1145/3299904.3340316",

language = "English",

pages = "154--168",

booktitle = "Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA '19)",

publisher = "Association for Computing Machinery (ACM)",

address = "United States",

note = "15th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XV), FOGA 2019 ; Conference date: 27-08-2019 Through 29-08-2019",

}

Lehre, PK & Nguyen, PTH 2019, On the limitations of the univariate marginal distribution algorithm to deception and where bivariate EDAs might help. in Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA '19). Association for Computing Machinery (ACM), New York, NY, USA, pp. 154-168, 15th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XV), Potsdam, Germany, 27/08/19. https://doi.org/10.1145/3299904.3340316

On the limitations of the univariate marginal distribution algorithm to deception and where bivariate EDAs might help. / Lehre, Per Kristian; Nguyen, Phan Trung Hai.
Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA '19). New York, NY, USA: Association for Computing Machinery (ACM), 2019. p. 154-168.

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

TY - GEN

T1 - On the limitations of the univariate marginal distribution algorithm to deception and where bivariate EDAs might help

AU - Lehre, Per Kristian

AU - Nguyen, Phan Trung Hai

PY - 2019/8/27

Y1 - 2019/8/27

N2 - We introduce a new benchmark problem called Deceptive Leading Blocks (DLB) to rigorously study the runtime of the Univariate Marginal Distribution Algorithm (UMDA) in the presence of epistasis and deception. We show that simple Evolutionary Algorithms (EAs) outperform the UMDA unless the selective pressure μ/λ is extremely high, where μ and λ are the parent and offspring population sizes, respectively. More precisely, we show that the UMDA with a parent population size of μ=Ω(logn) has an expected runtime of eΩ(μ) on the DLB problem assuming any selective pressure μ/λ ≥14/1000, as opposed to the expected runtime of O(nλlogλ+n3) for the non-elitist (μ,λ) EA with μ/λ≤1/e. These results illustrate inherent limitations of univariate EDAs against deception and epistasis, which are common characteristics of real-world problems. In contrast, empirical evidence reveals the efficiency of the bi-variate MIMIC algorithm on the DLB problem. Our results suggest that one should consider EDAs with more complex probabilistic models when optimising problems with some degree of epistasis and deception.

AB - We introduce a new benchmark problem called Deceptive Leading Blocks (DLB) to rigorously study the runtime of the Univariate Marginal Distribution Algorithm (UMDA) in the presence of epistasis and deception. We show that simple Evolutionary Algorithms (EAs) outperform the UMDA unless the selective pressure μ/λ is extremely high, where μ and λ are the parent and offspring population sizes, respectively. More precisely, we show that the UMDA with a parent population size of μ=Ω(logn) has an expected runtime of eΩ(μ) on the DLB problem assuming any selective pressure μ/λ ≥14/1000, as opposed to the expected runtime of O(nλlogλ+n3) for the non-elitist (μ,λ) EA with μ/λ≤1/e. These results illustrate inherent limitations of univariate EDAs against deception and epistasis, which are common characteristics of real-world problems. In contrast, empirical evidence reveals the efficiency of the bi-variate MIMIC algorithm on the DLB problem. Our results suggest that one should consider EDAs with more complex probabilistic models when optimising problems with some degree of epistasis and deception.

KW - Running time analysis

KW - deception

KW - deceptive leading blocks

KW - epistasis

KW - theory

KW - univariate marginal distribution algorithm

UR - https://hpi.de/foga2019/

U2 - 10.1145/3299904.3340316

DO - 10.1145/3299904.3340316

M3 - Conference contribution

SP - 154

EP - 168

BT - Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA '19)

PB - Association for Computing Machinery (ACM)

CY - New York, NY, USA

T2 - 15th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XV)

Y2 - 27 August 2019 through 29 August 2019

ER -

On the limitations of the univariate marginal distribution algorithm to deception and where bivariate EDAs might help

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this