research-article

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

Authors:

Per Kristian Lehre,

Phan Trung Hai NguyenAuthors Info & Claims

FOGA '19: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

Pages 154 - 168

https://doi.org/10.1145/3299904.3340316

Published: 27 August 2019 Publication History

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 µ = Ω (log n) has an expected runtime of e^Ω(µ) on the DLB problem assuming any selective pressure [EQUATION], 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.

References

[1]

David H. Ackley. 1987. An empirical study of bit vector function optimisation. Genetic Algorithms and Simulated Annealing (1987), 170--204.

[2]

Rubén Armañanzas, Iñaki Inza, Roberto Santana, Yvan Saeys, Jose Luis Flores, Jose Antonio Lozano, Yves Van De Peer, Rosa Blanco, Víctor Robles, Concha Bielza, and Pedro Larrañaga. 2008. A review of estimation of distribution algorithms in bioinformatics. BioData Mining 1, 1 (2008), 6.

[3]

Shummet Baluja. 1994. Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning. Technical report, Carnegie Mellon University (1994).

Digital Library

[4]

Christopher M. Bishop. 2006. Pattern Recognition and Machine Learning (Information Science and Statistics). Springer-Verlag.

Digital Library

[5]

Tianshi Chen, Per Kristian Lehre, Ke Tang, and Xin Yao. 2009. When is an Estimation of Distribution Algorithm Better than an Evolutionary Algorithm?. In Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2009. 1470--1477.

Digital Library

[6]

Dogan Corus, Duc-Cuong Dang, Anton V. Eremeev, and Per Kristian Lehre. 2018. Level-Based Analysis of Genetic Algorithms and Other Search Processes. IEEE Transactions on Evolutionary Computation 22, 5 (Oct 2018), 707--719.

Digital Library

[7]

Duc Cuong Dang and Per Kristian Lehre. 2015. Simplified Runtime Analysis of Estimation of Distribution Algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '15). 513--518.

Digital Library

[8]

Duc Cuong Dang, Per Kristian Lehre, and Phan Trung Hai Nguyen. 2018. Level-Based Analysis of the Univariate Marginal Distribution Algorithm. Algorithmica (2018).

[9]

Yuval Davidor. 1991. Epistasis Variance: A Viewpoint on GA-Hardness. Foundations of Genetic Algorithms, Vol. 1. Elsevier, 23 -- 35.

[10]

Jeremy S. De Bonet, Charles L. Isbell Jr, and Paul Viola. 1996. MIMIC: Finding Optima by Estimating Probability Densities. In Proceedings of the 9th International Conference on Neural Information Processing Systems (NIPS '96). 424--430.

Digital Library

[11]

Benjamin Doerr. 2019. An Exponential Lower Bound for the Runtime of the cGA on Jump Functions. CoRR abs/1904.08415 (2019).

Digital Library

[12]

Benjamin Doerr. 2019. A Tight Runtime Analysis for the cGA on Jump Functions - EDAs Can Cross Fitness Valleys at No Extra Cost. CoRR abs/1903.10983 (2019). arXiv:1903.10983

Digital Library

[13]

Benjamin Doerr and Carola Doerr. 2016. The Impact of Random Initialization on the Runtime of Randomized Search Heuristics. Algorithmica 75, 3 (2016), 529--553.

Digital Library

[14]

Benjamin Doerr, Daniel Johannsen, and Carola Winzen. 2010. Multiplicative Drift Analysis. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '10). 1449--1456.

Digital Library

[15]

Benjamin Doerr and Timo Kötzing. 2019. Multiplicative Up-Drift. CoRR abs/1904.05682 (2019).

Digital Library

[16]

Benjamin Doerr and Martin S. Krejca. 2018. Significance-Based Estimation-of-Distribution Algorithms. In Proceedings of Genetic and Evolutionary Computation Conference (GECCO '18). 1483--1490.

Digital Library

[17]

Stefan Droste, Thomas Jansen, and Ingo Wegener. 2002. On the Analysis of the (1+ 1) Evolutionary Algorithm. Theoretical Computer Science 276, 1--2 (2002), 51--81.

Digital Library

[18]

Devdatt Dubhashi and Alessandro Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms (1st ed.). Cambridge University Press.

Digital Library

[19]

Agoston E. Eiben and J. E. Smith. 2003. Introduction to Evolutionary Computing. SpringerVerlag.

Digital Library

[20]

Bennett Eisenberg. 2008. On the expectation of the maximum of IID geometric random variables. Statistics & Probability Letters 78, 2 (2008), 135 -- 143.

[21]

William Feller. 1968. An introduction to probability theory and its applications (3 ed.). Vol. 1. Wiley.

[22]

Tobias Friedrich, Timo Kötzing, and Martin S. Krejca. 2016. EDAs cannot be balanced and stable. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '16). 1139--1146.

Digital Library

[23]

Tobias Friedrich, Timo Kötzing, Martin S. Krejca, and Andrew M. Sutton. 2017. The Compact Genetic Algorithm is Efficient Under Extreme Gaussian Noise. IEEE Transactions on Evolutionary Computation 21, 3 (2017), 477--490.

Digital Library

[24]

Robin Gras. 2008. How efficient are genetic algorithms to solve high epistasis deceptive problems?. In 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence). 242--249.

[25]

Georges R. Harik, Fernando G. Lobo, and David E. Goldberg. 1999. The compact genetic algorithm. IEEE Trans. Evolutionary Computation 3, 4 (1999), 287--297.

Digital Library

[26]

Václav Hasenöhrl and Andrew M. Sutton. 2018. On the Runtime Dynamics of the Compact Genetic Algorithm on Jump Functions. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '18). 967--974.

Digital Library

[27]

Mark Hauschild and Martin Pelikan. 2011. An introduction and survey of estimation of distribution algorithms. Swarm and Evolutionary Computation 1, 3 (2011), 111--128.

[28]

Jun He and Xin Yao. 2003. Towards an analytic framework for analysing the computation time of evolutionary algorithms. Artificial Intelligence 145, 1 (2003), 59 -- 97.

Digital Library

[29]

Thomas Jansen, Kenneth A. De Jong, and Ingo Wegener. 2005. On the Choice of the Offspring Population Size in Evolutionary Algorithms. Evolutionary Computation 13, 4 (2005), 413--440.

Digital Library

[30]

Thomas Jansen and R. Paul Wiegand. 2004. The Cooperative Coevolutionary (1+1) EA. Evolutionary Computation 12, 4 (2004), 405--434.

Digital Library

[31]

Daniel Johannsen. 2010. Random combinatorial structures and randomized search heuristics. Ph.D. Dissertation. Universität des Saarlandes, Germany.

[32]

Martin S. Krejca and Carsten Witt. 2017. Lower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMax. In Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA '17). 65--79.

Digital Library

[33]

Pedro Larrañaga and Jose A. Lozano. 2001. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Springer US.

Digital Library

[34]

Per Kristian Lehre. 2010. Negative Drift in Populations. In Parallel Problem Solving from Nature, PPSN XI. Springer Berlin Heidelberg, 244--253.

Digital Library

[35]

Per Kristian Lehre. 2011. Fitness-levels for Non-elitist Populations. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '11). 2075--2082.

Digital Library

[36]

Per Kristian Lehre and Phan Trung Hai Nguyen. 2017. Improved Runtime Bounds for the Univariate Marginal Distribution Algorithm via Anti-concentration. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '17). 1383--1390.

Digital Library

[37]

Per Kristian Lehre and Phan Trung Hai Nguyen. 2018. Level-Based Analysis of the Population-Based Incremental Learning Algorithm. In Proceedings of the International Conference on Parallel Problem Solving from Nature (PPSN XV). 105--116.

[38]

Per Kristian Lehre and Phan Trung Hai Nguyen. 2019. Runtime Analysis of the Univariate Marginal Distribution Algorithm under Low Selective Pressure and Prior Noise. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '19). To appear.

Digital Library

[39]

Per Kristian Lehre and Pietro S. Oliveto. 2018. Theoretical Analysis of Stochastic Search Algorithms. Springer International Publishing, 1--36.

[40]

Johannes Lengler, Dirk Sudholt, and Carsten Witt. 2018. Medium step sizes are harmful for the compact genetic algorithm. In Proceedings of Genetic and Evolutionary Computation Conference (GECCO '18). 1499--1506.

Digital Library

[41]

Rajeev Motwani and Prabhakar Raghavan. 1995. Randomised algorithms. Cambridge University Press.

Digital Library

[42]

Heinz Mühlenbein and Gerhard Paaß. 1996. From recombination of genes to the estimation of distributions I. Binary parameters. 178--187.

Digital Library

[43]

Martin Pelikan, David E. Goldberg, and Fernando G. Lobo. 2002. A Survey of Optimization by Building and Using Probabilistic Models. Computational Optimization and Applications 21, 1 (2002), 5--20.

Digital Library

[44]

Dan Simon. 2013. Evolutionary Optimisation Algorithms. Wiley.

[45]

Montgomery Slatkin. 2008. Linkage disequilibrium - understanding the evolutionary past and mapping the medical future. Nature Reviews Genetics 9, 6 (2008), 477--485.

[46]

Dirk Sudholt. 2017. How Crossover Speeds Up Building Block Assembly in Genetic Algorithms. Evolutionary Computation 25, 2 (2017), 237--274.

Digital Library

[47]

Dirk Sudholt and Carsten Witt. 2016. Update Strength in EDAs and ACO: How to Avoid Genetic Drift. In Proceedings of the Genetic and Evolutionary Computation Conference 2016 (GECCO '16). 61--68.

Digital Library

[48]

Ingo Wegener. 2002. Methods for the Analysis of Evolutionary Algorithms on Pseudo-Boolean Functions. 349--369.

[49]

Eric W. Weisstein. {n. d.}. Binomial Distribution. ({n. d.}). http://mathworld.wolfram.com/BinomialDistribution.html

[50]

Carsten Witt. 2006. Runtime Analysis of the (µ + 1) EA on Simple Pseudo-Boolean Functions. Evolutionary Computation 14, 1 (2006), 65--86.

Digital Library

[51]

Carsten Witt. 2017. Upper Bounds on the Runtime of the Univariate Marginal Distribution Algorithm on Onemax. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '17). 1415--1422.

Digital Library

[52]

Carsten Witt. 2018. Domino convergence: why one should hill-climb on linear functions. In Proceedings of Genetic and Evolutionary Computation Conference (GECCO '18). 1539--1546.

Digital Library

[53]

Zijun Wu, Michael Kolonko, and Rolf H. Möhring. 2017. Stochastic Runtime Analysis of a Cross Entropy Algorithm. IEEE Transactions on Evolutionary Computation 21, 4 (2017), 616--628. Issue 99.

[54]

Weijie Zheng, Guangwen Yang, and Benjamin Doerr. 2018. Working Principles of Binary Differential Evolution. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '18). 1103--1110.

Digital Library

Cited By

Jedidia FDoerr BKrejca M(2024)Estimation-of-Distribution Algorithms for Multi-Valued Decision VariablesTheoretical Computer Science10.1016/j.tcs.2024.114622(114622)Online publication date: May-2024
https://doi.org/10.1016/j.tcs.2024.114622
Doerr BKelley A(2024)Fourier Analysis Meets Runtime Analysis: Precise Runtimes on PlateausAlgorithmica10.1007/s00453-024-01232-586:8(2479-2518)Online publication date: 10-May-2024
https://doi.org/10.1007/s00453-024-01232-5
Florescu CKaufmann MLengler JSchaller U(2024)Faster Optimization Through Genetic DriftParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_5(70-85)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70071-2_5
Show More Cited By

Index Terms

On the limitations of the univariate marginal distribution algorithm to deception and where bivariate EDAs might help
1. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Discrete optimization
        Optimization with randomized search heuristics
        Evolutionary algorithms

Recommendations

The Univariate Marginal Distribution Algorithm Copes Well with Deception and Epistasis
Evolutionary Computation in Combinatorial Optimization
Abstract
In their recent work, Lehre and Nguyen (FOGA 2019) show that the univariate marginal distribution algorithm (UMDA) needs time exponential in the parent populations size to optimize the DeceivingLeadingBlocks (DLB) problem. They conclude from this ...
The univariate marginal distribution algorithm copes well with deception and epistasis
GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion

In their recent work, Lehre and Nguyen (FOGA 2019) show that the univariate marginal distribution algorithm (UMDA) needs time exponential in the parent populations size to optimize the DeceptiveLeadingBlocks (DLB) problem. They conclude from this result ...
Quantifying Deception: A Case Study in the Evolution of Antimicrobial Resistance
GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

The concept of "deception" in fitness landscapes was introduced in the genetic algorithm (GA) literature to characterize problems where sign epistasis can mislead a GA away from the global optimum. Evolutionary geneticists have long recognized that sign ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FOGA '19: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

August 2019

187 pages

ISBN:9781450362542

DOI:10.1145/3299904

General Chair:
Tobias Friedrich
Hasso Plattner Institute
,
Program Chairs:
Carola Doerr
Sorbonne University
,
Dirk Arnold
Dalhousie University

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 August 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

FOGA '19

Sponsor:

SIGEVO

FOGA '19: Foundations of Genetic Algorithms XV

August 27 - 29, 2019

Potsdam, Germany

Acceptance Rates

FOGA '19 Paper Acceptance Rate 15 of 31 submissions, 48%;

Overall Acceptance Rate 72 of 131 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
141
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)3

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jedidia FDoerr BKrejca M(2024)Estimation-of-Distribution Algorithms for Multi-Valued Decision VariablesTheoretical Computer Science10.1016/j.tcs.2024.114622(114622)Online publication date: May-2024
https://doi.org/10.1016/j.tcs.2024.114622
Doerr BKelley A(2024)Fourier Analysis Meets Runtime Analysis: Precise Runtimes on PlateausAlgorithmica10.1007/s00453-024-01232-586:8(2479-2518)Online publication date: 10-May-2024
https://doi.org/10.1007/s00453-024-01232-5
Florescu CKaufmann MLengler JSchaller U(2024)Faster Optimization Through Genetic DriftParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_5(70-85)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70071-2_5
Doerr BKelley ASilva SPaquete L(2023)Fourier Analysis Meets Runtime Analysis: Precise Runtimes on PlateausProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590393(1555-1564)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590393
Doerr BEl Ghazi El Houssaini TRajabi AWitt CSilva SPaquete L(2023)How Well Does the Metropolis Algorithm Cope With Local Optima?Proceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590390(1000-1008)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590390
Ajimakin ADevi V(2023)The Competing Genes Evolutionary Algorithm: Avoiding Genetic Drift Through Competition, Local Search, and Majority VotingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.322903827:6(1678-1689)Online publication date: Dec-2023
https://doi.org/10.1109/TEVC.2022.3229038
Doerr BKrejca M(2023)Bivariate estimation-of-distribution algorithms can find an exponential number of optimaTheoretical Computer Science10.1016/j.tcs.2023.114074971:COnline publication date: 6-Sep-2023
https://dl.acm.org/doi/10.1016/j.tcs.2023.114074
Wang SZheng WDoerr B(2023)Choosing the Right Algorithm With Hints From Complexity TheoryInformation and Computation10.1016/j.ic.2023.105125(105125)Online publication date: Nov-2023
https://doi.org/10.1016/j.ic.2023.105125
Wang SZheng WDoerr BWagner M(2022)Choosing the right algorithm with hints from complexity theoryProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3534069(45-46)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3534069
Bambury HBultel ADoerr B(2022)An Extended Jump Functions Benchmark for the Analysis of Randomized Search HeuristicsAlgorithmica10.1007/s00453-022-00977-186:1(1-32)Online publication date: 23-May-2022
https://doi.org/10.1007/s00453-022-00977-1
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents