{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,16]],"date-time":"2026-08-16T10:37:34Z","timestamp":1786876654488,"version":"build-2736575974"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2021,8,28]],"date-time":"2021-08-28T00:00:00Z","timestamp":1630108800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,8,28]],"date-time":"2021-08-28T00:00:00Z","timestamp":1630108800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,10]]},"abstract":"Abstract<\/jats:title>We perform rigorous runtime analyses for the univariate marginal distribution algorithm (UMDA<\/jats:sc>) and the population-based incremental learning (PBIL<\/jats:sc>) Algorithm on LeadingOnes<\/jats:sc>. For the UMDA<\/jats:sc>, the currently known expected runtime on the function is $${\\mathcal {O}}\\left( n\\lambda \\log \\lambda +n^2\\right)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n \n n<\/mml:mi>\n \u03bb<\/mml:mi>\n log<\/mml:mo>\n \u03bb<\/mml:mi>\n +<\/mml:mo>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> under an offspring population size $$\\lambda =\\Omega (\\log n)$$<\/jats:tex-math>\n \n \u03bb<\/mml:mi>\n =<\/mml:mo>\n \u03a9<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and a parent population size $$\\mu \\le \\lambda \/(e(1+\\delta ))$$<\/jats:tex-math>\n \n \u03bc<\/mml:mi>\n \u2264<\/mml:mo>\n \u03bb<\/mml:mi>\n \/<\/mml:mo>\n (<\/mml:mo>\n e<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n \u03b4<\/mml:mi>\n )<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for any constant $$\\delta >0$$<\/jats:tex-math>\n \n \u03b4<\/mml:mi>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> (Dang and Lehre, GECCO 2015). There is no lower bound on the expected runtime under the same parameter settings. It also remains unknown whether the algorithm can still optimise the LeadingOnes<\/jats:sc> function within a polynomial runtime when $$\\mu \\ge \\lambda \/(e(1+\\delta ))$$<\/jats:tex-math>\n \n \u03bc<\/mml:mi>\n \u2265<\/mml:mo>\n \u03bb<\/mml:mi>\n \/<\/mml:mo>\n (<\/mml:mo>\n e<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n \u03b4<\/mml:mi>\n )<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. In case of the PBIL<\/jats:sc>, an expected runtime of $${\\mathcal {O}}(n^{2+c})$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 2<\/mml:mn>\n +<\/mml:mo>\n c<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> holds for some constant $$c \\in (0,1)$$<\/jats:tex-math>\n \n c<\/mml:mi>\n \u2208<\/mml:mo>\n (<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> (Wu, Kolonko and M\u00f6hring, IEEE TEVC 2017). Despite being a generalisation of the UMDA<\/jats:sc>, this upper bound is significantly asymptotically looser than the upper bound of $${\\mathcal {O}}\\left( n^2\\right)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n \n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of the UMDA<\/jats:sc> for $$\\lambda =\\Omega (\\log n)\\cap {\\mathcal {O}}\\left( n\/\\log n\\right)$$<\/jats:tex-math>\n \n \u03bb<\/mml:mi>\n =<\/mml:mo>\n \u03a9<\/mml:mi>\n \n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2229<\/mml:mo>\n O<\/mml:mi>\n \n n<\/mml:mi>\n \/<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Furthermore, the required population size is very large, i.e., $$\\lambda =\\Omega (n^{1+c})$$<\/jats:tex-math>\n \n \u03bb<\/mml:mi>\n =<\/mml:mo>\n \u03a9<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 1<\/mml:mn>\n +<\/mml:mo>\n c<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Our contributions are then threefold: (1) we show that the UMDA<\/jats:sc> with $$\\mu =\\Omega (\\log n)$$<\/jats:tex-math>\n \n \u03bc<\/mml:mi>\n =<\/mml:mo>\n \u03a9<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$\\lambda \\le \\mu e^{1-\\varepsilon }\/(1+\\delta )$$<\/jats:tex-math>\n \n \u03bb<\/mml:mi>\n \u2264<\/mml:mo>\n \u03bc<\/mml:mi>\n \n e<\/mml:mi>\n \n 1<\/mml:mn>\n -<\/mml:mo>\n \u03b5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n \/<\/mml:mo>\n \n (<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n \u03b4<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for any constants $$\\varepsilon \\in (0,1)$$<\/jats:tex-math>\n \n \u03b5<\/mml:mi>\n \u2208<\/mml:mo>\n (<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$0<\\delta \\le e^{1-\\varepsilon }-1$$<\/jats:tex-math>\n \n 0<\/mml:mn>\n <<\/mml:mo>\n \u03b4<\/mml:mi>\n \u2264<\/mml:mo>\n \n e<\/mml:mi>\n \n 1<\/mml:mn>\n -<\/mml:mo>\n \u03b5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> requires an expected runtime of $$e^{\\Omega (\\mu )}$$<\/jats:tex-math>\n \n e<\/mml:mi>\n \n \u03a9<\/mml:mi>\n (<\/mml:mo>\n \u03bc<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> on LeadingOnes<\/jats:sc>, (2) an upper bound of $${\\mathcal {O}}\\left( n\\lambda \\log \\lambda +n^2\\right)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n \n n<\/mml:mi>\n \u03bb<\/mml:mi>\n log<\/mml:mo>\n \u03bb<\/mml:mi>\n +<\/mml:mo>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is shown for the PBIL<\/jats:sc>, which improves the current bound $${\\mathcal {O}}\\left( n^{2+c}\\right)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n \n \n n<\/mml:mi>\n \n 2<\/mml:mn>\n +<\/mml:mo>\n c<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> by a significant factor of $$\\Theta (n^{c})$$<\/jats:tex-math>\n \n \u0398<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n c<\/mml:mi>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and (3) we for the first time consider the two algorithms on the LeadingOnes<\/jats:sc> function in a noisy environment and obtain an expected runtime of $${\\mathcal {O}}\\left( n^2\\right)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n \n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for appropriate parameter settings. Our results emphasise that despite the independence assumption in the probabilistic models, the UMDA<\/jats:sc> and the PBIL<\/jats:sc> with fine-tuned parameter choices can still cope very well with variable interactions.<\/jats:p>","DOI":"10.1007\/s00453-021-00862-3","type":"journal-article","created":{"date-parts":[[2021,8,28]],"date-time":"2021-08-28T03:27:55Z","timestamp":1630121275000},"page":"3238-3280","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Runtime Analyses of the Population-Based Univariate Estimation of Distribution Algorithms on LeadingOnes"],"prefix":"10.1007","volume":"83","author":[{"given":"Per Kristian","family":"Lehre","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0783-2224","authenticated-orcid":false,"given":"Phan Trung Hai","family":"Nguyen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,8,28]]},"reference":[{"key":"862_CR1","unstructured":"Baluja, S.: Population-based incremental learning: a method for integrating genetic search based function optimization and competitive learning. Technical report, Carnegie Mellon University (1994)"},{"issue":"2","key":"862_CR2","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1109\/TEVC.2003.810761","volume":"7","author":"PAN Bosman","year":"2003","unstructured":"Bosman, P.A.N., Thierens, D.: The balance between proximity and diversity in multiobjective evolutionary algorithms. IEEE Trans. Evol. Comput. 7(2), 174\u2013188 (2003)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"5","key":"862_CR3","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1109\/TEVC.2017.2753538","volume":"22","author":"D Corus","year":"2018","unstructured":"Corus, D., Dang, D.C., Eremeev, A.V., Lehre, P.K.: Level-based analysis of genetic algorithms and other search processes. IEEE Trans. Evol. Comput. 22(5), 707\u2013719 (2018)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"862_CR4","doi-asserted-by":"crossref","unstructured":"Dang, D.C., Lehre, P.K.: Efficient optimisation of noisy fitness functions with population-based evolutionary algorithms. In: Proceedings of the Conference on Foundations of Genetic Algorithms, FOGA \u201915, pp. 62\u201368 (2015)","DOI":"10.1145\/2725494.2725508"},{"key":"862_CR5","doi-asserted-by":"crossref","unstructured":"Dang, D.C., Lehre, P.K.: Simplified runtime analysis of estimation of distribution algorithms. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO \u201915, pp. 513\u2013518 (2015)","DOI":"10.1145\/2739480.2754814"},{"key":"862_CR6","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1007\/s00453-018-0507-5","volume":"81","author":"DC Dang","year":"2018","unstructured":"Dang, D.C., Lehre, P.K., Nguyen, P.T.H.: Level-based analysis of the univariate marginal distribution algorithm. Algorithmica 81, 668\u2013702 (2018)","journal-title":"Algorithmica"},{"key":"862_CR7","unstructured":"Doerr, B. Probabilistic tools for the analysis of randomized optimization heuristics. CoRR. abs\/1801.06733 (2018)"},{"key":"862_CR8","doi-asserted-by":"crossref","unstructured":"Doerr , B., K\u00f6tzing, T. Multiplicative up-drift. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO \u201919, pp. 1470\u20131478 (2019)","DOI":"10.1145\/3321707.3321819"},{"key":"862_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TEVC.2019.2902626","volume":"24","author":"B Doerr","year":"2020","unstructured":"Doerr, B., Zheng, W.: Sharp bounds for genetic drift in estimation of distribution algorithms. IEEE Trans. Evol. Comput. 24, 1 (2020)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"3","key":"862_CR10","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/s11047-006-9001-0","volume":"5","author":"S Droste","year":"2006","unstructured":"Droste, S.: A rigorous analysis of the compact genetic algorithm for linear functions. Nat. Comput. 5(3), 257\u2013283 (2006)","journal-title":"Nat. Comput."},{"issue":"1\u20132","key":"862_CR11","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0304-3975(01)00182-7","volume":"276","author":"S Droste","year":"2002","unstructured":"Droste, S., Jansen, T., Wegener, I.: On the analysis of the (1 + 1) evolutionary algorithm. Theor. Comput. Sci. 276(1\u20132), 51\u201381 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"862_CR12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"D Dubhashi","year":"2009","unstructured":"Dubhashi, D., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms, 1st edn. Cambridge University Press, Cambridge (2009)","edition":"1"},{"key":"862_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-05094-1","volume-title":"Introduction to Evolutionary Computing","author":"AE Eiben","year":"2003","unstructured":"Eiben, A.E., Smith, J.E.: Introduction to Evolutionary Computing. Springer, Berlin (2003)"},{"key":"862_CR14","volume-title":"An Introduction to Probability Theory and Its Applications","author":"W Feller","year":"1968","unstructured":"Feller, W.: An Introduction to Probability Theory and Its Applications, vol. 1, 3rd edn. Wiley, New York (1968)","edition":"3"},{"key":"862_CR15","doi-asserted-by":"crossref","unstructured":"Friedrich, T., K\u00f6tzing, T., Krejca, M.S.: EDAs cannot be balanced and stable. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO \u201916, pp. 1139\u20131146 (2016)","DOI":"10.1145\/2908812.2908895"},{"issue":"3","key":"862_CR16","first-page":"477","volume":"21","author":"T Friedrich","year":"2017","unstructured":"Friedrich, T., K\u00f6tzing, T., Krejca, M.S., Sutton, A.M.: The compact genetic algorithm is efficient under extreme gaussian noise. IEEE Trans. Evol. Comput. 21(3), 477\u2013490 (2017)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"3","key":"862_CR17","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1007\/s00453-015-0072-0","volume":"75","author":"C Gie\u00dfen","year":"2016","unstructured":"Gie\u00dfen, C., K\u00f6tzing, T.: Robustness of populations in stochastic environments. Algorithmica 75(3), 462\u2013489 (2016)","journal-title":"Algorithmica"},{"issue":"1","key":"862_CR18","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1214\/aop\/1176996461","volume":"3","author":"LJ Gleser","year":"1975","unstructured":"Gleser, L.J.: On the distribution of the number of successes in independent trials. Ann. Probab. 3(1), 182\u2013188 (1975)","journal-title":"Ann. Probab."},{"key":"862_CR19","unstructured":"Harik, G.R., Lobo, F.G., Goldberg, D.E.: The compact genetic algorithm. IlliGAL report No. 97006. University of Illinois at Urbana-Champaign (1997)"},{"issue":"3","key":"862_CR20","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.swevo.2011.08.003","volume":"1","author":"M Hauschild","year":"2011","unstructured":"Hauschild, M., Pelikan, M.: An introduction and survey of estimation of distribution algorithms. Swarm Evol. Comput. 1(3), 111\u2013128 (2011)","journal-title":"Swarm Evol. Comput."},{"issue":"1","key":"862_CR21","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0004-3702(02)00381-8","volume":"145","author":"J He","year":"2003","unstructured":"He, J.: Towards an analytic framework for analysing the computation time of evolutionary algorithms. Artif. Intell. 145(1), 59\u201397 (2003)","journal-title":"Artif. Intell."},{"key":"862_CR22","unstructured":"Krejca M.S., Carsten, W.: Theory of estimation-of-distribution algorithms. CoRR, arXiv:1806.05392 (2018)"},{"issue":"5","key":"862_CR23","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1007\/s10732-012-9208-4","volume":"18","author":"P Larra\u00f1aga","year":"2012","unstructured":"Larra\u00f1aga, P., Karshenas, H., Bielza, C., Santana, R.: A review on probabilistic graphical models in evolutionary computation. J. Heuristics 18(5), 795\u2013819 (2012)","journal-title":"J. Heuristics"},{"key":"862_CR24","series-title":"Genetic Algorithms and Evolutionary Computation","volume-title":"Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation","author":"P Larra\u00f1aga","year":"2001","unstructured":"Larra\u00f1aga, P., Lozano, J.A.: Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Genetic Algorithms and Evolutionary Computation, Springer, New York (2001)"},{"key":"862_CR25","doi-asserted-by":"crossref","unstructured":"Lehre, P.K.: Fitness-levels for non-elitist populations. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO \u201911, pp. 2075\u20132082 (2011)","DOI":"10.1145\/2001576.2001855"},{"key":"862_CR26","doi-asserted-by":"crossref","unstructured":"Lehre, P.K., Nguyen, P.T.H.: Improved runtime bounds for the univariate marginal distribution algorithm via anti-concentration. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO \u201917, pp. 1383\u20131390 (2017)","DOI":"10.1145\/3071178.3071317"},{"key":"862_CR27","doi-asserted-by":"crossref","unstructured":"Lehre, P.K., Nguyen, P.T.H.: Level-based analysis of the population-based incremental learning algorithm. In: Proceedings of the Conference on Parallel Problem Solving from Nature. PPSN XV, pp. 105\u2013116 (2018)","DOI":"10.1007\/978-3-319-99259-4_9"},{"key":"862_CR28","doi-asserted-by":"crossref","unstructured":"Lehre, P.K., Nguyen, P.T.H.: On the limitations of the univariate marginal distribution algorithm to deception and where bivariate EDAs might help. In: Proceedings of the Conference on Foundations of Genetic Algorithms, FOGA \u201919, pp. 154\u2013168 (2019)","DOI":"10.1145\/3299904.3340316"},{"key":"862_CR29","doi-asserted-by":"crossref","unstructured":"Lehre, P.K., Nguyen, P.T.H.: 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 \u201919. pp. 1497\u20131505 (2019)","DOI":"10.1145\/3321707.3321834"},{"key":"862_CR30","first-page":"1","volume-title":"Theoretical Analysis of Stochastic Search Algorithms","author":"PK Lehre","year":"2018","unstructured":"Lehre, P.K., Oliveto, P.S.: Theoretical Analysis of Stochastic Search Algorithms, pp. 1\u201336. Springer, Berlin (2018)"},{"issue":"4","key":"862_CR31","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1007\/s00453-012-9616-8","volume":"64","author":"PK Lehre","year":"2012","unstructured":"Lehre, P.K., Witt, C.: Black-box search by unbiased variation. Algorithmica 64(4), 623\u2013642 (2012)","journal-title":"Algorithmica"},{"key":"862_CR32","series-title":"Springer Series in Statistics","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68276-1","volume-title":"Inequalities: Theory of Majorization and Its Applications","author":"AW Marshall","year":"2011","unstructured":"Marshall, A.W., Olkin, I., Arnold, B.C.: Inequalities: Theory of Majorization and Its Applications. Springer Series in Statistics, Springer, New York (2011)"},{"issue":"3","key":"862_CR33","doi-asserted-by":"publisher","first-page":"1269","DOI":"10.1214\/aop\/1176990746","volume":"18","author":"P Massart","year":"1990","unstructured":"Massart, P.: The tight constant in the Dvoretzky\u2013Kiefer\u2013Wolfowitz inequality. Ann. Probab. 18(3), 1269\u20131283 (1990)","journal-title":"Ann. Probab."},{"key":"862_CR34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-99970-3","volume-title":"Analytic Inequalities","author":"DS Mitrinovi\u0107","year":"1970","unstructured":"Mitrinovi\u0107, D.S.: Analytic Inequalities. Springer, Berlin (1970)"},{"key":"862_CR35","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"M Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (2005)"},{"key":"862_CR36","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomised Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomised Algorithms. Cambridge University Press, Cambridge (1995)"},{"issue":"1","key":"862_CR37","first-page":"19","volume":"7","author":"H M\u00fchlenbein","year":"1999","unstructured":"M\u00fchlenbein, H., Mahnig, T.: Convergence theory and applications of the factorized distribution algorithm. CIT J. Comput. Inform. Technol. 7(1), 19\u201332 (1999)","journal-title":"CIT J. Comput. Inform. Technol."},{"key":"862_CR38","doi-asserted-by":"crossref","unstructured":"M\u00fchlenbein, H., Paa\u00df, G.: From recombination of genes to the estimation of distributions I. binary parameters. In: Proceedings of the Conference on Parallel Problem Solving from NaturE. PPSN IV, pp. 178\u2013187 (1996)","DOI":"10.1007\/3-540-61723-X_982"},{"key":"862_CR39","unstructured":"Natural logarithm: Inequalities\u2014wolfram functions site. https:\/\/functions.wolfram.com\/ElementaryFunctions\/Log\/29\/. Accessed 09 Nov 2020"},{"issue":"1","key":"862_CR40","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1023\/A:1013500812258","volume":"21","author":"M Pelikan","year":"2002","unstructured":"Pelikan, M., Goldberg, D.E., Lobo, F.G.: A survey of optimization by building and using probabilistic models. Comput. Optim. Appl. 21(1), 5\u201320 (2002)","journal-title":"Comput. Optim. Appl."},{"key":"862_CR41","doi-asserted-by":"crossref","unstructured":"Qian, C., Bian, C., Jiang, W., Tang, K.: Running time analysis of the (1+1)-EA for Onemax and Leadingones under bit-wise noise. In: Proceedings of the Conference on Genetic and Evolutionary Computation, GECCO \u201917, pp. 1399-1406 (2017)","DOI":"10.1145\/3071178.3071347"},{"issue":"8","key":"862_CR42","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1016\/S0167-739X(00)00043-1","volume":"16","author":"T St\u00fctzle","year":"2000","unstructured":"St\u00fctzle, T., Hoos, H.H.: Max\u2013Min ant system. Fut. Gen. Comput. Syst. 16(8), 889\u2013914 (2000)","journal-title":"Fut. Gen. Comput. Syst."},{"key":"862_CR43","doi-asserted-by":"crossref","unstructured":"Sudholt, D.: On the robustness of evolutionary algorithms to noise: refined results and an example where noise helps. In: Proceedings of the Conference on Genetic and Evolutionary Computation, GECCO \u201918, pp. 1523-1530 (2018)","DOI":"10.1145\/3205455.3205595"},{"key":"862_CR44","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813658","volume-title":"Probability with Martingales","author":"D Williams","year":"1991","unstructured":"Williams, D.: Probability with Martingales. Cambridge University Press, Cambridge (1991)"},{"key":"862_CR45","doi-asserted-by":"crossref","unstructured":"Witt, C.: Upper bounds on the runtime of the univariate marginal distribution algorithm on Onemax. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO \u201917, pp. 1415\u20131422 (2017)","DOI":"10.1145\/3071178.3071216"},{"key":"862_CR46","doi-asserted-by":"crossref","unstructured":"Witt, C.: Domino convergence: why one should hill-climb on linear functions. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO \u201918, pp. 1539\u20131546 (2018)","DOI":"10.1145\/3205455.3205581"},{"issue":"4","key":"862_CR47","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1109\/TEVC.2017.2667713","volume":"21","author":"Z Wu","year":"2017","unstructured":"Wu, Z., Kolonko, M., M\u00f6hring, R.H.: Stochastic runtime analysis of a cross entropy algorithm. IEEE Trans. Evol. Comput. 21(4), 616\u2013628 (2017)","journal-title":"IEEE Trans. Evol. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00862-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00862-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00862-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,1]],"date-time":"2021-10-01T15:38:19Z","timestamp":1633102699000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00862-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,28]]},"references-count":47,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["862"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00862-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,28]]},"assertion":[{"value":"29 May 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 July 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 August 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}