{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:16:59Z","timestamp":1760203019250},"reference-count":36,"publisher":"MIT Press - Journals","issue":"4","content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,12,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>In their recent work, Lehre and Nguyen (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 the 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 \u03bb(n2+2elnn) fitness evaluations. Since an offspring population size \u03bb of order nlogn can prevent genetic drift, the UMDA can solve the DLB problem with O(n2logn) fitness evaluations. In contrast, for classic evolutionary algorithms no better runtime guarantee than O(n3) is known (which we prove to be tight for the (1+1) EA), so our result rather suggests that the UMDA can cope well with deception and epistatis. From a broader perspective, our result shows that the UMDA can cope better with local optima than many classic evolutionary algorithms; such a result was previously known only for the compact genetic algorithm. Together with the lower bound 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.<\/jats:p>","DOI":"10.1162\/evco_a_00293","type":"journal-article","created":{"date-parts":[[2021,4,15]],"date-time":"2021-04-15T00:49:50Z","timestamp":1618447790000},"page":"543-563","update-policy":"http:\/\/dx.doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":11,"title":["The Univariate Marginal Distribution Algorithm Copes Well with\n                    Deception and Epistasis"],"prefix":"10.1162","volume":"29","author":[{"given":"Benjamin","family":"Doerr","sequence":"first","affiliation":[{"name":"Laboratoire d'Informatique (LIX), CNRS, \u00c9cole Polytechnique, Institut Polytechnique de Paris, Palaiseau, France doerr@lix.polytechnique.fr"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin S.","family":"Krejca","sequence":"additional","affiliation":[{"name":"Sorbonne Universit\u00e9, CNRS, LIP6, Paris, France*martin.krejca@lip.fr"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","published-online":{"date-parts":[[2021,12,1]]},"reference":[{"key":"2021120113010028500_B1","first-page":"1","volume-title":"Proceedings of Parallel Problem Solving from\n                            Nature","author":"B\u00f6ttcher","year":"2010"},{"key":"2021120113010028500_B2","doi-asserted-by":"crossref","unstructured":"Chen,\n                            T.,\n                                Lehre, P.\n                                K.,\n                            Tang,\n                            K., and\n                                Yao,\n                            X.\n                        (2009). When is an estimation of distribution\n                        algorithm better than an evolutionary algorithm? In\n                            Proceedings of Congress on Evolutionary\n                            Computation, pp.\n                        1470\u20131477.","DOI":"10.1109\/CEC.2009.4983116"},{"issue":"5","key":"2021120113010028500_B3","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1109\/TEVC.2017.2753538","article-title":"Level-based analysis of genetic algorithms and other search\n                        processes","volume":"22","author":"Corus","year":"2018","journal-title":"IEEE Transactions on Evolutionary\n                            Computation"},{"key":"2021120113010028500_B4","first-page":"645","volume-title":"Proceedings of the Genetic and\n                            Evolutionary Computation Conference (GECCO)","author":"Dang","year":"2016"},{"issue":"3","key":"2021120113010028500_B5","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1109\/TEVC.2017.2724201","article-title":"Escaping local optima using crossover with emergent\n                        diversity","volume":"22","author":"Dang","year":"2018","journal-title":"IEEE Transactions on Evolutionary\n                            Computation"},{"key":"2021120113010028500_B6","first-page":"513","volume-title":"Proceedings of the Genetic\n                            and Evolutionary Computation Conference (GECCO)","author":"Dang","year":"2015"},{"issue":"3","key":"2021120113010028500_B7","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1007\/s00453-015-0103-x","article-title":"Runtime analysis of non-elitist populations: From classical\n                        optimisation to partial information","volume":"75","author":"Dang","year":"2016","journal-title":"Algorithmica"},{"key":"2021120113010028500_B8","first-page":"424","volume-title":"Proceedings of Neural\n                            Information Processing Systems","author":"De Bonet","year":"1996"},{"key":"2021120113010028500_B9","doi-asserted-by":"crossref","unstructured":"Doerr,\n                                B.\n          \n                        (2019a). Analyzing randomized search heuristics\n                        via stochastic domination.Theoretical Computer Science,\n                        773:115\u2013137.","DOI":"10.1016\/j.tcs.2018.09.024"},{"key":"2021120113010028500_B10","doi-asserted-by":"crossref","first-page":"1488","DOI":"10.1145\/3321707.3321747","volume-title":"Proceedings of the Genetic and\n                            Evolutionary Computation Conference (GECCO)","author":"Doerr","year":"2019"},{"key":"2021120113010028500_B11","doi-asserted-by":"crossref","unstructured":"Doerr,\n                                B.\n          \n                        (2020a). Does comma selection help to cope with\n                        local optima? In Proceedings of the Genetic\n                            and Evolutionary Computation Conference (GECCO), pp.\n                        1304\u20131313.","DOI":"10.1145\/3377930.3389823"},{"key":"2021120113010028500_B12","doi-asserted-by":"crossref","unstructured":"Doerr,\n                                B.\n          \n                        (2020b). Probabilistic tools for the analysis of\n                        randomized optimization heuristics. In\n                            Theory of evolutionary computation: Recent developments\n                            in discrete optimization, pp.\n                        1\u201387.\n                        Berlin:\n                        Springer. Retrieved from https:\/\/arxiv.org\/abs\/1801.06733.","DOI":"10.1007\/978-3-030-29414-4_1"},{"key":"2021120113010028500_B13","first-page":"759","volume-title":"Genetic and Evolutionary Computation Conference\n                            (GECCO)","author":"Doerr","year":"2010"},{"key":"2021120113010028500_B14","doi-asserted-by":"crossref","unstructured":"Doerr,\n                                B., and\n                                K\u00fcnnemann,\n                                M.\n                        (2015). Optimizing linear functions with the\n                                        (1+\u03bb)\n                        evolutionary algorithm\u2014Different asymptotic runtimes for different\n                        instances.Theoretical Computer Science,\n                        561:3\u201323.","DOI":"10.1016\/j.tcs.2014.03.015"},{"key":"2021120113010028500_B15","doi-asserted-by":"crossref","first-page":"1470","DOI":"10.1145\/3321707.3321819","volume-title":"Proceedings of the Genetic and Evolutionary Computation\n                            Conference (GECCO)","author":"Doerr","year":"2019"},{"key":"2021120113010028500_B16","first-page":"796","volume-title":"Proceedings\n                            of the Genetic and Evolutionary Computation Conference\n                        (GECCO)","author":"Doerr","year":"2020"},{"issue":"6","key":"2021120113010028500_B17","doi-asserted-by":"crossref","first-page":"1025","DOI":"10.1109\/TEVC.2019.2956633","article-title":"Significance-based estimation-of-distribution\n                        algorithms","volume":"24","author":"Doerr","year":"2020","journal-title":"IEEE Transactions on\n                            Evolutionary Computation"},{"key":"2021120113010028500_B18","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/978-3-030-43680-3_4","volume-title":"Proceedings\n                            of Evolutionary Computation in Combinatorial\n                        Optimization","author":"Doerr","year":"2020"},{"issue":"6","key":"2021120113010028500_B19","doi-asserted-by":"crossref","first-page":"1140","DOI":"10.1109\/TEVC.2020.2987361","article-title":"Sharp bounds for genetic drift in\n                        estimation-of-distribution algorithms","volume":"24","author":"Doerr","year":"2020","journal-title":"IEEE\n                            Transactions on Evolutionary Computation"},{"issue":"3","key":"2021120113010028500_B20","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/s11047-006-9001-0","article-title":"A rigorous analysis of the compact\n                        genetic algorithm for linear functions","volume":"5","author":"Droste","year":"2006","journal-title":"Natural Computing"},{"issue":"1-2","key":"2021120113010028500_B21","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/S0304-3975(01)00182-7","article-title":"On the analysis of the (1+1)\n                        evolutionary algorithm","volume":"276","author":"Droste","year":"2002","journal-title":"Theoretical Computer\n                            Science"},{"key":"2021120113010028500_B22","doi-asserted-by":"crossref","unstructured":"Fan,\n                            X.,\n                                Grama,\n                            I., and\n                                Liu,\n                            Q.\n                        (2015). Exponential inequalities for martingales\n                        with applications.Electronic Journal of Probability,\n                        20:1\u201322.","DOI":"10.1214\/EJP.v20-3496"},{"key":"2021120113010028500_B23","doi-asserted-by":"crossref","first-page":"967","DOI":"10.1145\/3205455.3205608","volume-title":"Proceedings of the\n                            Genetic and Evolutionary Computation Conference\n                        (GECCO)","author":"Hasen\u00f6hrl","year":"2018"},{"issue":"301","key":"2021120113010028500_B24","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","article-title":"Probability inequalities for sums of\n                        bounded random variables","volume":"58","author":"Hoeffding","year":"1963","journal-title":"Journal of the\n                            American Statistical Association"},{"key":"2021120113010028500_B25","doi-asserted-by":"crossref","unstructured":"K\u00f6tzing,\n                                T.\n          \n                        (2016). Concentration of first hitting times\n                        under additive drift.Algorithmica,\n                        75:490\u2013506.","DOI":"10.1007\/s00453-015-0048-0"},{"key":"2021120113010028500_B26","doi-asserted-by":"crossref","unstructured":"Krejca, M.\n                                S., and\n                                Witt,\n                            C.\n                        (2020a). Lower bounds on the run time of the\n                        univariate marginal distribution algorithm on OneMax.Theoretical Computer Science,\n                        832:143\u2013165.","DOI":"10.1016\/j.tcs.2018.06.004"},{"key":"2021120113010028500_B27","doi-asserted-by":"crossref","unstructured":"Krejca, M.\n                                S., and\n                                Witt,\n                            C.\n                        (2020b). Theory of estimation-of-distribution\n                        algorithms. In Theory of evolutionary\n                            computation: Recent developments in discrete\n                        optimization, pp.\n                        405\u2013442.\n                        Berlin:\n                        Springer. Retrieved from http:\/\/arxiv.org\/abs\/1806.05392.","DOI":"10.1007\/978-3-030-29414-4_9"},{"key":"2021120113010028500_B28","first-page":"2075","volume-title":"Proceedings of the Genetic and Evolutionary Computation\n                            Conference (GECCO)","author":"Lehre","year":"2011"},{"key":"2021120113010028500_B29","doi-asserted-by":"crossref","first-page":"1383","DOI":"10.1145\/3071178.3071317","volume-title":"Proceedings of the Genetic and Evolutionary Computation\n                            Conference (GECCO)","author":"Lehre","year":"2017"},{"key":"2021120113010028500_B30","first-page":"154","volume-title":"Proceedings of Foundations of Genetic\n                        Algorithms","author":"Lehre","year":"2019"},{"key":"2021120113010028500_B31","doi-asserted-by":"crossref","first-page":"1499","DOI":"10.1145\/3205455.3205576","volume-title":"Proceedings of\n                            the Genetic and Evolutionary Computation Conference\n                        (GECCO)","author":"Lengler","year":"2018"},{"key":"2021120113010028500_B32","first-page":"178","volume-title":"Proceedings of Parallel Problem Solving from\n                            Nature","author":"M\u00fchlenbein","year":"1996"},{"key":"2021120113010028500_B33","doi-asserted-by":"crossref","unstructured":"Pelikan,\n                                M.,\n                                Hauschild,\n                                M., and\n                                Lobo, F.\n                                G. (2015).\n                        Estimation of distribution algorithms. In\n                            Springer handbook of computational\n                        intelligence, pp.\n                        899\u2013928.\n                        Berlin:\n                        Springer.","DOI":"10.1007\/978-3-662-43505-2_45"},{"issue":"4","key":"2021120113010028500_B34","doi-asserted-by":"crossref","first-page":"1450","DOI":"10.1007\/s00453-018-0480-z","article-title":"On the choice of the update strength in\n                        estimation-of-distribution algorithms and ant colony\n                        optimization","volume":"81","author":"Sudholt","year":"2019","journal-title":"Algorithmica"},{"key":"2021120113010028500_B35","doi-asserted-by":"crossref","first-page":"1539","DOI":"10.1145\/3205455.3205581","volume-title":"Proceedings of the Genetic and Evolutionary Computation\n                            Conference (GECCO)","author":"Witt","year":"2018"},{"issue":"2","key":"2021120113010028500_B36","doi-asserted-by":"crossref","first-page":"632","DOI":"10.1007\/s00453-018-0463-0","article-title":"Upper bounds on the running time of the\n                        univariate marginal distribution algorithm on OneMax","volume":"81","author":"Witt","year":"2019","journal-title":"Algorithmica"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/29\/4\/543\/1974860\/evco_a_00293.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/29\/4\/543\/1974860\/evco_a_00293.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,1]],"date-time":"2021-12-01T17:58:33Z","timestamp":1638381513000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/29\/4\/543\/99839\/The-Univariate-Marginal-Distribution-Algorithm"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"references-count":36,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,12,1]]},"published-print":{"date-parts":[[2021,12,1]]}},"URL":"https:\/\/doi.org\/10.1162\/evco_a_00293","relation":{},"ISSN":["1530-9304"],"issn-type":[{"value":"1530-9304","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021]]},"published":{"date-parts":[[2021]]}}}