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

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

Colleges, School and Institutes

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.


Details

Original languageEnglish
Title of host publicationProceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA '19)
Publication statusPublished - 27 Aug 2019
Event15th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XV) - Hasso Plattner Institute, Potsdam, Germany
Duration: 27 Aug 201929 Aug 2019

Conference

Conference15th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XV)
Abbreviated titleFOGA 2019
CountryGermany
CityPotsdam
Period27/08/1929/08/19

Keywords

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