{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T19:54:25Z","timestamp":1775246065961,"version":"3.50.1"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,10,8]],"date-time":"2018-10-08T00:00:00Z","timestamp":1538956800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100011102","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["618091"],"award-info":[{"award-number":["618091"]}],"id":[{"id":"10.13039\/100011102","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,2]]},"DOI":"10.1007\/s00453-018-0507-5","type":"journal-article","created":{"date-parts":[[2018,10,8]],"date-time":"2018-10-08T14:06:07Z","timestamp":1539007567000},"page":"668-702","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":37,"title":["Level-Based Analysis of the Univariate Marginal Distribution Algorithm"],"prefix":"10.1007","volume":"81","author":[{"given":"Duc-Cuong","family":"Dang","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9521-1251","authenticated-orcid":false,"given":"Per Kristian","family":"Lehre","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0783-2224","authenticated-orcid":false,"given":"Phan Trung Hai","family":"Nguyen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,10,8]]},"reference":[{"issue":"1","key":"507_CR1","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1186\/1756-0381-1-6","volume":"1","author":"R Arma\u00f1anzas","year":"2008","unstructured":"Arma\u00f1anzas, R., Inza, I., Santana, R., Saeys, Y., Flores, J.L., Lozano, J.A., Van de Peer, Y., Blanco, R., Robles, V., Bielza, C., Larra\u00f1aga, P.: A review of estimation of distribution algorithms in bioinformatics. BioData Min 1(1), 6 (2008)","journal-title":"BioData Min"},{"key":"507_CR2","doi-asserted-by":"crossref","unstructured":"Asoh, H., M\u00fchlenbein, H.: On the mean convergence time of evolutionary algorithms without selection and mutation. In: Proceedings of the 3rd International Conference on Parallel Problem Solving from Nature, PPSN III, pp. 88\u201397 (1994)","DOI":"10.1007\/3-540-58484-6_253"},{"issue":"3","key":"507_CR3","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1017\/S0963548315000127","volume":"25","author":"J-B Baillon","year":"2016","unstructured":"Baillon, J.-B., Cominetti, R., Vaisman, J.: A sharp uniform bound for the distribution of sums of Bernoulli trials. Comb. Probab. Comput. 25(3), 352\u2013361 (2016)","journal-title":"Comb. Probab. Comput."},{"key":"507_CR4","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)"},{"key":"507_CR5","doi-asserted-by":"crossref","unstructured":"Chen, T., Lehre, P.K., Tang, K., Yao, X.: When is an estimation of distribution algorithm better than an evolutionary algorithm? In: Proceedings of 2009 IEEE Congress on Evolutionary Computation, pp. 1470\u20131477 (2009)","DOI":"10.1109\/CEC.2009.4983116"},{"key":"507_CR6","doi-asserted-by":"crossref","unstructured":"Chen, T., Tang, K., Chen, G., Yao, X.: On the analysis of average time complexity of estimation of distribution algorithms. In: Proceedings of 2007 IEEE Congress on Evolutionary Computation, pp. 453\u2013460 (2007)","DOI":"10.1109\/CEC.2007.4424506"},{"key":"507_CR7","doi-asserted-by":"crossref","unstructured":"Chen, T., Tang, K., Chen, G., Yao, X.: Rigorous time complexity analysis of univariate marginal distribution algorithm with margins. In: Proceedings of 2009 IEEE Congress on Evolutionary Computation, pp. 2157\u20132164 (2009)","DOI":"10.1109\/CEC.2009.4983208"},{"issue":"1","key":"507_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TEVC.2009.2040019","volume":"14","author":"T Chen","year":"2010","unstructured":"Chen, T., Tang, K., Chen, G., Yao, X.: Analysis of computational time of simple estimation of distribution algorithms. IEEE Trans. Evol. Comput. 14(1), 1\u201322 (2010)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"507_CR9","doi-asserted-by":"publisher","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. https:\/\/doi.org\/10.1109\/TEVC.2017.2753538 (2017)","DOI":"10.1109\/TEVC.2017.2753538"},{"key":"507_CR10","doi-asserted-by":"crossref","unstructured":"Dang D.-C., Lehre P.K.: Simplified runtime analysis of estimation of distribution algorithms. In: Proceedings of Genetic and Evolutionary Computation, GECCO\u201915, pp. 513\u2013518 (2015)","DOI":"10.1145\/2739480.2754814"},{"key":"507_CR11","doi-asserted-by":"crossref","unstructured":"Dang, D.-C., Lehre, P.K.: Self-adaptation of mutation rates in non-elitist populations. In: Proceedings of the 14th International Conference on Parallel Problem Solving from Nature, PPSN XIV, pp. 803\u2013813 (2016)","DOI":"10.1007\/978-3-319-45823-6_75"},{"key":"507_CR12","doi-asserted-by":"crossref","unstructured":"Doerr, B.: Probabilistic tools for the analysis of randomized optimization heuristics. CoRR. arXiv:1801.06733 (2018)","DOI":"10.1007\/978-3-030-29414-4_1"},{"key":"507_CR13","doi-asserted-by":"crossref","unstructured":"Doerr, B., Krejca, M.S.: Significance-based estimation-of-distribution algorithms. In: Proceedings of Genetic and Evolutionary Computation Conference, GECCO\u201918, pp. 1483\u20131490 (2018)","DOI":"10.1145\/3205455.3205553"},{"issue":"3","key":"507_CR14","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. Natl. Comput. 5(3), 257\u2013283 (2006)","journal-title":"Natl. Comput."},{"key":"507_CR15","first-page":"177","volume-title":"Probabilistic Models for Linkage Learning in Forest Management","author":"EI Ducheyne","year":"2005","unstructured":"Ducheyne, E.I., De Baets, B., De Wulf, R.: Probabilistic Models for Linkage Learning in Forest Management, pp. 177\u2013194. Springer, Berlin (2005)"},{"issue":"4","key":"507_CR16","doi-asserted-by":"publisher","first-page":"964","DOI":"10.1137\/S0097539704447304","volume":"35","author":"U Feige","year":"2006","unstructured":"Feige, U.: On sums of independent random variables with unbounded variance and estimating the average degree in a graph. SIAM J. Comput. 35(4), 964\u2013984 (2006)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"507_CR17","first-page":"477","volume":"21","author":"T Friedrich","year":"2017","unstructured":"Friedrich, T., K\u00f6tzing, T., Krejca, M., 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."},{"key":"507_CR18","doi-asserted-by":"crossref","unstructured":"Friedrich, T., K\u00f6tzing, T., Krejca, M.S.: EDAs cannot be balanced and stable. In: Proceedings of Genetic and Evolutionary Computation Conference, GECCO\u201916, pp. 1139\u20131146 (2016)","DOI":"10.1145\/2908812.2908895"},{"issue":"1","key":"507_CR19","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."},{"issue":"2","key":"507_CR20","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1002\/etep.1854","volume":"25","author":"W Gu","year":"2015","unstructured":"Gu, W., Wu, Y., Zhang, G.Y.: A hybrid univariate marginal distribution algorithm for dynamic economic dispatch of units considering valve-point effects and ramp rates. Int. Trans. Electr. Energy Syst. 25(2), 374\u2013392 (2015)","journal-title":"Int. Trans. Electr. Energy Syst."},{"issue":"4","key":"507_CR21","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1109\/4235.797971","volume":"3","author":"GR Harik","year":"1999","unstructured":"Harik, G.R., Lobo, F.G., Goldberg, D.E.: The compact genetic algorithm. IEEE Trans. Evol. Comput. 3(4), 287\u2013297 (1999)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"3","key":"507_CR22","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":"4","key":"507_CR23","doi-asserted-by":"publisher","first-page":"1191","DOI":"10.1214\/aoms\/1177698243","volume":"39","author":"K Jogdeo","year":"1968","unstructured":"Jogdeo, K., Samuels, S.M.: Monotone convergence of binomial probabilities and a generalization of ramanujan\u2018s equation. Ann. Math. Stat. 39(4), 1191\u20131195 (1968)","journal-title":"Ann. Math. Stat."},{"issue":"5","key":"507_CR24","doi-asserted-by":"publisher","first-page":"828","DOI":"10.1016\/j.advwatres.2008.01.017","volume":"31","author":"JB Kollat","year":"2008","unstructured":"Kollat, J.B., Reed, P.M., Kasprzyk, J.R.: A new epsilon-dominance hierarchical Bayesian optimization algorithm for large multiobjective monitoring network design problems. Adv. Water Resour. 31(5), 828\u2013845 (2008)","journal-title":"Adv. Water Resour."},{"key":"507_CR25","doi-asserted-by":"crossref","unstructured":"Krejca, M.S., Witt, C.: Theory of estimation-of-distribution algorithms. CoRR. arXiv:1806.05392 (2018)","DOI":"10.1007\/978-3-030-29414-4_9"},{"key":"507_CR26","doi-asserted-by":"crossref","unstructured":"Krejca, M.S., Witt, C.: Lower bounds on the run time of the univariate marginal distribution algorithm on OneMax. In: Proceedings of Foundations of Genetic Algorithms XIV, FOGA\u201917, pp. 65\u201379 (2017)","DOI":"10.1145\/3040718.3040724"},{"key":"507_CR27","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 Genetic and Evolutionary Computation Conference, GECCO\u201917, pp. 1383\u20131390 (2017)","DOI":"10.1145\/3071178.3071317"},{"key":"507_CR28","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 15th International Conference on Parallel Problem Solving from Nature, PPSN XV, pp. 105\u2013116 (2018)","DOI":"10.1007\/978-3-319-99259-4_9"},{"key":"507_CR29","doi-asserted-by":"crossref","unstructured":"Lehre, P.K., Witt, C.: Black-box search by unbiased variation. In: Proceedings of Genetic and Evolutionary Computation Conference, GECCO\u201910, pp. 1441\u20131448 (2010)","DOI":"10.1145\/1830483.1830747"},{"key":"507_CR30","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1016\/j.ins.2010.01.031","volume":"259","author":"PK Lehre","year":"2014","unstructured":"Lehre, P.K., Yao, X.: Runtime analysis of the (1+1) EA on computing unique input output sequences. Inf. Sci. 259, 510\u2013531 (2014)","journal-title":"Inf. Sci."},{"key":"507_CR31","volume-title":"Introduction to Algorithms","author":"CE Leiserson","year":"2009","unstructured":"Leiserson, C.E., Stein, C., Rivest, R., Cormen, T.H.: Introduction to Algorithms. MIT Press, Cambridge (2009)"},{"key":"507_CR32","doi-asserted-by":"crossref","unstructured":"Lengler, J., Sudholt, D., Witt, C.: Medium step sizes are harmful for the compact genetic algorithm. In: Proceedings of Genetic and Evolutionary Computation Conference, GECCO\u201918, pp. 1499\u20131506 (2018)","DOI":"10.1145\/3205455.3205576"},{"key":"507_CR33","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, New York (2011)"},{"issue":"3","key":"507_CR34","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":"507_CR35","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-99970-3","volume-title":"Analytic Inequalities","author":"DS Mitrinovic","year":"1970","unstructured":"Mitrinovic, D.S.: Analytic Inequalities. Springer, Berlin (1970)"},{"key":"507_CR36","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/S0304-3975(02)00098-1","volume":"287","author":"H M\u00fchlenbein","year":"2002","unstructured":"M\u00fchlenbein, H., Mahnig, T.: Evolutionary computation and wright\u2018s equation. Theor. Comput. Sci. 287, 145\u2013165 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"507_CR37","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 9th International Conference on Parallel Problem Solving from Nature, PPSN IV, pp. 178\u2013187 (1996)","DOI":"10.1007\/3-540-61723-X_982"},{"key":"507_CR38","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-4321-0","volume-title":"The Cross Entropy Method: A Unified Approach To Combinatorial Optimization, Monte\u2013Carlo Simulation (Information Science and Statistics)","author":"RY Rubinstein","year":"2004","unstructured":"Rubinstein, R.Y., Kroese, D.P.: The Cross Entropy Method: A Unified Approach To Combinatorial Optimization, Monte\u2013Carlo Simulation (Information Science and Statistics). Springer, New York (2004)"},{"issue":"1","key":"507_CR39","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/s11047-014-9473-2","volume":"15","author":"R Santana","year":"2016","unstructured":"Santana, R., Mendiburu, A., Lozano, J.A.: A review of message passing algorithms in estimation of distribution algorithms. Natl. Comput. 15(1), 165\u2013180 (2016)","journal-title":"Natl. Comput."},{"issue":"1","key":"507_CR40","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1162\/1063656053583414","volume":"13","author":"JL Shapiro","year":"2005","unstructured":"Shapiro, J.L.: Drift and scaling in estimation of distribution algorithms. Evol. Comput. 13(1), 99\u2013123 (2005)","journal-title":"Evol. Comput."},{"issue":"6","key":"507_CR41","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1038\/nrg2361","volume":"9","author":"M Slatkin","year":"2008","unstructured":"Slatkin, M.: Linkage disequilibrium\u2014understanding the evolutionary past and mapping the medical future. Nat. Rev. Genet. 9(6), 477\u2013485 (2008)","journal-title":"Nat. Rev. Genet."},{"key":"507_CR42","doi-asserted-by":"crossref","unstructured":"Sudholt, D., Witt, C.: Update strength in EDAs and ACO: how to avoid genetic drift. In: Proceedings of Genetic and Evolutionary Computation Conference, GECCO\u201916, pp. 61\u201368 (2016)","DOI":"10.1145\/2908812.2908867"},{"key":"507_CR43","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-9999-5","volume-title":"Algebra","author":"BL Waerden van der","year":"1991","unstructured":"van der Waerden, B.L.: Algebra, vol. 1. Springer, New York (1991)"},{"key":"507_CR44","doi-asserted-by":"crossref","unstructured":"Witt, C.: Upper bounds on the runtime of the univariate marginal distribution algorithm on OneMax. In: Proceedings of Genetic and Evolutionary Computation Conference, GECCO\u201917, pp. 1415\u20131422 (2017)","DOI":"10.1145\/3071178.3071216"},{"key":"507_CR45","doi-asserted-by":"crossref","unstructured":"Witt, C.: Domino convergence: why one should hill-climb on linear functions. In: Proceedings of Genetic and Evolutionary Computation Conference, GECCO\u201918, pp. 1539\u20131546 (2018)","DOI":"10.1145\/3205455.3205581"},{"issue":"4","key":"507_CR46","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 the cross-entropy algorithm. IEEE Trans. Evol. Comput. 21(4), 616\u2013628 (2017)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"507_CR47","first-page":"275","volume-title":"Military Antenna Design Using a Simple Genetic Algorithm and hBOA","author":"T-L Yu","year":"2006","unstructured":"Yu, T.-L., Santarelli, S., Goldberg, D.E.: Military Antenna Design Using a Simple Genetic Algorithm and hBOA, pp. 275\u2013289. Springer, Berlin (2006)"},{"key":"507_CR48","doi-asserted-by":"crossref","unstructured":"Zinchenko, L., M\u00fchlenbein, H., Kureichik, V., Mahnig, T.: Application of the univariate marginal distribution algorithm to analog circuit design. In: Proceedings of 2002 NASA\/DoD Conference on Evolvable Hardware, pp. 93\u2013101 (2002)","DOI":"10.1109\/EH.2002.1029871"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0507-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0507-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0507-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T18:59:25Z","timestamp":1775242765000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0507-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,8]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,2]]}},"alternative-id":["507"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0507-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10,8]]},"assertion":[{"value":"11 September 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 August 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 October 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}