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 Owner/Author.
PY - 2020/7/8
Y1 - 2020/7/8
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 DeceptiveLeadingBlocks (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 λ(n/2 + 2e ln n) fitness evaluations. Since an offspring population size λ of order n log n can prevent genetic drift, the UMDA can solve the DLB problem with O(n2 log n) fitness evaluations. 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. This extended abstract summarizes our work "The Univariate Marginal Distribution Algorithm Copes Well with Deception and Epistasis", which appeared in the Proceedings of Evolutionary Computation in Combinatorial Optimization (EvoCOP), 2020, pp. 51 - 66, and won the conference's best-paper award.
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 DeceptiveLeadingBlocks (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 λ(n/2 + 2e ln n) fitness evaluations. Since an offspring population size λ of order n log n can prevent genetic drift, the UMDA can solve the DLB problem with O(n2 log n) fitness evaluations. 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. This extended abstract summarizes our work "The Univariate Marginal Distribution Algorithm Copes Well with Deception and Epistasis", which appeared in the Proceedings of Evolutionary Computation in Combinatorial Optimization (EvoCOP), 2020, pp. 51 - 66, and won the conference's best-paper award.
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/85089732884
U2 - 10.1145/3377929.3397487
DO - 10.1145/3377929.3397487
M3 - Conference contribution
AN - SCOPUS:85089732884
T3 - GECCO 2020 Companion - Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion
SP - 17
EP - 18
BT - GECCO 2020 Companion - Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion
PB - Association for Computing Machinery, Inc
T2 - 2020 Genetic and Evolutionary Computation Conference, GECCO 2020
Y2 - 8 July 2020 through 12 July 2020
ER -