TY - GEN
T1 - The Univariate Marginal Distribution Algorithm Copes Well with Deception and Epistasis
AU - Doerr, Benjamin
AU - Krejca, Martin S.
N1 - Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
PY - 2020/1/1
Y1 - 2020/1/1
N2 - 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 result that univariate EDAs have difficulties with deception and epistasis. In this work, we show that this negative finding is caused by an unfortunate choice of the parameters of the UMDA. When the population sizes are chosen large enough to prevent genetic drift, then the UMDA optimizes the DLB problem with high probability with at most fitness evaluations. Since an offspring population size of order can prevent genetic drift, the UMDA can solve the DLB problem with fitness evaluations. In contrast, for classic evolutionary algorithms no better run time guarantee than is known, so our result rather suggests that the UMDA can cope well with deception and epistatis. Together with the result of Lehre and Nguyen, our result for the first time rigorously proves that running EDAs in the regime with genetic drift can lead to drastic performance losses.
AB - 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 result that univariate EDAs have difficulties with deception and epistasis. In this work, we show that this negative finding is caused by an unfortunate choice of the parameters of the UMDA. When the population sizes are chosen large enough to prevent genetic drift, then the UMDA optimizes the DLB problem with high probability with at most fitness evaluations. Since an offspring population size of order can prevent genetic drift, the UMDA can solve the DLB problem with fitness evaluations. In contrast, for classic evolutionary algorithms no better run time guarantee than is known, so our result rather suggests that the UMDA can cope well with deception and epistatis. Together with the result of Lehre and Nguyen, our result for the first time rigorously proves that running EDAs in the regime with genetic drift can lead to drastic performance losses.
KW - Epistasis
KW - Estimation-of-distribution algorithm
KW - Run time analysis
KW - Theory
KW - Univariate marginal distribution algorithm
UR - https://www.scopus.com/pages/publications/85084973519
U2 - 10.1007/978-3-030-43680-3_4
DO - 10.1007/978-3-030-43680-3_4
M3 - Conference contribution
AN - SCOPUS:85084973519
SN - 9783030436797
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 51
EP - 66
BT - Evolutionary Computation in Combinatorial Optimization - 20th European Conference, EvoCOP 2020, Held as Part of EvoStar 2020, Proceedings
A2 - Paquete, Luís
A2 - Zarges, Christine
PB - Springer
T2 - 20th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2020, held as part of Evostar 2020
Y2 - 15 April 2020 through 17 April 2020
ER -