{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T05:55:21Z","timestamp":1783749321641,"version":"3.55.0"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,6,25]],"date-time":"2020-06-25T00:00:00Z","timestamp":1593043200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,6,25]],"date-time":"2020-06-25T00:00:00Z","timestamp":1593043200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Government of Russian Federation","award":["Grant 08-08"],"award-info":[{"award-number":["Grant 08-08"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,4]]},"DOI":"10.1007\/s00453-020-00731-5","type":"journal-article","created":{"date-parts":[[2020,6,25]],"date-time":"2020-06-25T09:02:27Z","timestamp":1593075747000},"page":"1054-1095","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["A Tight Runtime Analysis for the $${(\\mu + \\lambda )}$$\u00a0EA"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7906-096X","authenticated-orcid":false,"given":"Denis","family":"Antipov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benjamin","family":"Doerr","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,6,25]]},"reference":[{"key":"731_CR1","doi-asserted-by":"crossref","unstructured":"Antipov, D., Doerr, B., Fang, J., Hetet, T.: Runtime analysis for the $$(\\mu +\\lambda )$$ EA optimizing OneMax. In: Genetic and Evolutionary Computation Conference, GECCO 2018, pp. 1459\u20131466. ACM (2018)","DOI":"10.1145\/3205455.3205627"},{"key":"731_CR2","doi-asserted-by":"crossref","unstructured":"Antipov, D., Doerr, B., Yang, Q.: The efficiency threshold for the offspring population size of the $${(\\mu ,\\lambda )}$$ EA. In: Genetic and Evolutionary Computation Conference, GECCO 2019, pp. 1461\u20131469. ACM (2019)","DOI":"10.1145\/3321707.3321838"},{"key":"731_CR3","doi-asserted-by":"crossref","unstructured":"B\u00f6ttcher, S., Doerr, B., Neumann, F.: Optimal fixed and adaptive mutation rates for the LeadingOnes problem. In: Parallel Problem Solving from Nature, PPSN XI, Part I, pp. 1\u201310 (2010)","DOI":"10.1007\/978-3-642-15844-5_1"},{"key":"731_CR4","doi-asserted-by":"crossref","unstructured":"Badkobeh, G., Lehre, P.K., Sudholt, D.: Unbiased black-box complexity of parallel search. In: Parallel Problem Solving from Nature, PPSN 2014, pp. 892\u2013901. Springer (2014)","DOI":"10.1007\/978-3-319-10762-2_88"},{"issue":"5","key":"731_CR5","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 Evolut Comput 22(5), 707\u2013719 (2018)","journal-title":"IEEE Trans Evolut Comput"},{"key":"731_CR6","doi-asserted-by":"crossref","unstructured":"Colin, S., Doerr, B., F\u00e9rey, G.: Monotonic functions in EC: anything but monotone! In: Genetic and Evolutionary Computation Conference, GECCO 2014, pp. 753\u2013760. ACM (2014)","DOI":"10.1145\/2576768.2598338"},{"key":"731_CR7","doi-asserted-by":"publisher","first-page":"1092","DOI":"10.1109\/TSMCB.2008.2012167","volume":"39","author":"T Chen","year":"2009","unstructured":"Chen, T., He, J., Sun, G., Chen, G., Yao, X.: A new approach for analyzing average time complexity of population-based evolutionary algorithms on unimodal problems. IEEE Trans. Syst. Man Cybern. Part B (Cybern.) 39, 1092\u20131106 (2009)","journal-title":"IEEE Trans. Syst. Man Cybern. Part B (Cybern.)"},{"key":"731_CR8","doi-asserted-by":"publisher","first-page":"1658","DOI":"10.1007\/s00453-017-0354-9","volume":"80","author":"B Doerr","year":"2018","unstructured":"Doerr, B., Doerr, C.: Optimal static and self-adjusting parameter choices for the $$(1+(\\lambda,\\lambda ))$$ genetic algorithm. Algorithmica 80, 1658\u20131709 (2018)","journal-title":"Algorithmica"},{"key":"731_CR9","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.tcs.2014.11.028","volume":"567","author":"B Doerr","year":"2015","unstructured":"Doerr, B., Doerr, C., Ebel, F.: From black-box complexity to designing new genetic algorithms. Theor. Comput. Sci. 567, 87\u2013104 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"731_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2019.06.014","volume":"801","author":"B Doerr","year":"2020","unstructured":"Doerr, B., Doerr, C., Yang, J.: Optimal parameter choices via precise black-box analysis. Theor. Comput. Sci. 801, 1\u201334 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"731_CR11","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1109\/TEVC.2017.2724201","volume":"22","author":"D-C Dang","year":"2018","unstructured":"Dang, D.-C., Friedrich, T., K\u00f6tzing, T., Krejca, M.S., Lehre, P.K., Oliveto, P.S., Sudholt, D., Sutton, A.M.: Escaping local optima using crossover with emergent diversity. IEEE Transa. Evolut. Comput. 22, 484\u2013497 (2018)","journal-title":"IEEE Transa. Evolut. Comput."},{"key":"731_CR12","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/s00453-011-9585-3","volume":"65","author":"B Doerr","year":"2013","unstructured":"Doerr, B., Goldberg, L.A.: Adaptive drift analysis. Algorithmica 65, 224\u2013250 (2013)","journal-title":"Algorithmica"},{"key":"731_CR13","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1007\/s00453-018-0502-x","volume":"81","author":"B Doerr","year":"2019","unstructured":"Doerr, B., Gie\u00dfen, C., Witt, C., Yang, J.: The $${(1 + \\lambda )}$$ evolutionary algorithm with self-adjusting mutation rate. Algorithmica 81, 593\u2013631 (2019)","journal-title":"Algorithmica"},{"key":"731_CR14","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.tcs.2010.10.035","volume":"425","author":"B Doerr","year":"2012","unstructured":"Doerr, B., Happ, E., Klein, C.: Crossover can provably be useful in evolutionary computation. Theor. Comput. Sci. 425, 17\u201333 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"731_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1162\/EVCO_a_00055","volume":"21","author":"B Doerr","year":"2013","unstructured":"Doerr, B., Jansen, T., Sudholt, D., Winzen, C., Zarges, C.: Mutation rate matters even when optimizing monotone functions. Evolut. Comput. 21, 1\u201321 (2013)","journal-title":"Evolut. Comput."},{"key":"731_CR16","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\u00a0+\u00a01) evolutionary algorithm. Theor. Comput. Sci. 276, 51\u201381 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"731_CR17","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1007\/s00453-012-9622-x","volume":"64","author":"B Doerr","year":"2012","unstructured":"Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. Algorithmica 64, 673\u2013697 (2012)","journal-title":"Algorithmica"},{"key":"731_CR18","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.tcs.2014.03.015","volume":"561","author":"B Doerr","year":"2015","unstructured":"Doerr, B., K\u00fcnnemann, M.: Optimizing linear functions with the (1\u00a0+\u00a0$$\\lambda $$) evolutionary algorithm\u2014different asymptotic runtimes for different instances. Theor. Comput. Sci. 561, 3\u201323 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"731_CR19","doi-asserted-by":"crossref","unstructured":"Doerr, B., Kodric, B., Voigt, M.: Lower bounds for the runtime of a global multi-objective evolutionary algorithm. In: Congress on Evolutionary Computation, CEC 2013, pp. 432\u2013439. IEEE (2013)","DOI":"10.1109\/CEC.2013.6557601"},{"key":"731_CR20","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1007\/s00453-015-0103-x","volume":"75","author":"D-C Dang","year":"2016","unstructured":"Dang, D.-C., Lehre, P.K.: Runtime analysis of non-elitist populations: from classical optimisation to partial information. Algorithmica 75, 428\u2013461 (2016)","journal-title":"Algorithmica"},{"key":"731_CR21","doi-asserted-by":"crossref","unstructured":"Doerr, B., Le, H.P., Makhmara, R., Nguyen, T.D.: Fast genetic algorithms. In: Genetic and Evolutionary Computation Conference, GECCO 2017. ACM (2017)","DOI":"10.1145\/3071178.3071301"},{"key":"731_CR22","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.spl.2018.03.016","volume":"139","author":"B Doerr","year":"2018","unstructured":"Doerr, B.: An elementary analysis of the probability that a binomial random variable exceeds its expectation. Stat. Probab. Lett. 139, 67\u201374 (2018)","journal-title":"Stat. Probab. Lett."},{"key":"731_CR23","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.tcs.2018.09.024","volume":"773","author":"B Doerr","year":"2019","unstructured":"Doerr, B.: Analyzing randomized search heuristics via stochastic domination. Theor. Comput. Sci. 773, 115\u2013137 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"731_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-030-29414-4","volume-title":"Theory of Evolutionary Computation: Recent Developments in Discrete Optimization","author":"B Doerr","year":"2020","unstructured":"Doerr, B.: Probabilistic tools for the analysis of randomized optimization heuristics. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pp. 1\u201387. Springer, Berlin (2020). arXiv:1801.06733"},{"key":"731_CR25","doi-asserted-by":"crossref","unstructured":"de\u00a0Perthuis\u00a0de Laillevault, A., Doerr, B., Doerr, C.: Money for nothing: speeding up evolutionary algorithms through better initialization. In: Genetic and Evolutionary Computation Conference, GECCO 2015, pp. 815\u2013822. ACM (2015)","DOI":"10.1145\/2739480.2754760"},{"key":"731_CR26","doi-asserted-by":"crossref","unstructured":"Droste, S.: Not all linear functions are equally difficult for the compact genetic algorithm. In: Genetic and Evolutionary Computation Conference, GECCO 2005, pp. 679\u2013686. ACM (2005)","DOI":"10.1145\/1068009.1068124"},{"key":"731_CR27","doi-asserted-by":"crossref","unstructured":"Doerr, B., Witt, C., Yang, J.: Runtime analysis for self-adaptive mutation rates. In: Genetic and Evolutionary Computation Conference, GECCO 2018, pp. 1475\u20131482. ACM (2018)","DOI":"10.1145\/3205455.3205569"},{"key":"731_CR28","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, 462\u2013489 (2016)","journal-title":"Algorithmica"},{"key":"731_CR29","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.spl.2013.12.009","volume":"86","author":"S Greenberg","year":"2014","unstructured":"Greenberg, S., Mohri, M.: Tight lower bound on the probability of a binomial exceeding its expectation. Stat. Probab. Lett. 86, 91\u201398 (2014)","journal-title":"Stat. Probab. Lett."},{"key":"731_CR30","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1007\/s00453-016-0214-z","volume":"78","author":"C Gie\u00dfen","year":"2017","unstructured":"Gie\u00dfen, C., Witt, C.: The interplay of population size and mutation probability in the $$(1+\\lambda )$$ EA on OneMax. Algorithmica 78, 587\u2013609 (2017)","journal-title":"Algorithmica"},{"key":"731_CR31","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0004-3702(01)00058-3","volume":"127","author":"J He","year":"2001","unstructured":"He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artif. Intell. 127, 51\u201381 (2001)","journal-title":"Artif. Intell."},{"key":"731_CR32","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1023\/B:NACO.0000023417.31393.c7","volume":"3","author":"J He","year":"2004","unstructured":"He, J., Yao, X.: A study of drift analysis for estimating computation time of evolutionary algorithms. Nat. Comput. 3, 21\u201335 (2004)","journal-title":"Nat. Comput."},{"key":"731_CR33","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1162\/106365605774666921","volume":"13","author":"T Jansen","year":"2005","unstructured":"Jansen, T., De Jong, K.A., Wegener, I.: On the choice of the offspring population size in evolutionary algorithms. Evolut. Comput. 13, 413\u2013440 (2005)","journal-title":"Evolut. Comput."},{"key":"731_CR34","doi-asserted-by":"crossref","unstructured":"J\u00e4gersk\u00fcpper, J., Witt, C.: Rigorous runtime analysis of a ($$\\mu $$+ 1) ES for the sphere function. In: Genetic and Evolutionary Computation Conference, GECCO 2005, pp. 849\u2013856. ACM (2005)","DOI":"10.1145\/1068009.1068153"},{"key":"731_CR35","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1016\/j.tcs.2010.03.032","volume":"412","author":"T Jansen","year":"2011","unstructured":"Jansen, T., Zarges, C.: On benefits and drawbacks of aging strategies for randomized search heuristics. Theor. Comput. Sci. 412, 543\u2013559 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"731_CR36","doi-asserted-by":"crossref","unstructured":"Lehre, P.K.: Negative drift in populations. In: Parallel Problem Solving from Nature, PPSN 2010, pp. 244\u2013253. Springer (2010)","DOI":"10.1007\/978-3-642-15844-5_25"},{"key":"731_CR37","doi-asserted-by":"crossref","unstructured":"Lengler, J.: A general dichotomy of evolutionary algorithms on monotone functions. In: Parallel Problem Solving from Nature, PPSN 2018, Part II, pp. 3\u201315. Springer (2018)","DOI":"10.1007\/978-3-319-99259-4_1"},{"key":"731_CR38","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, 623\u2013642 (2012)","journal-title":"Algorithmica"},{"key":"731_CR39","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1109\/TEVC.2011.2112665","volume":"16","author":"PK Lehre","year":"2012","unstructured":"Lehre, P.K., Yao, X.: On the impact of mutation-selection balance on the runtime of evolutionary algorithms. IEEE Trans. Evolut. Comput. 16, 225\u2013241 (2012)","journal-title":"IEEE Trans. Evolut. Comput."},{"key":"731_CR40","doi-asserted-by":"crossref","unstructured":"Qian, C., Yu, Y., Zhou, Z.-H.: A lower bound analysis of population-based evolutionary algorithms for pseudo-Boolean functions. In: International Conference on Intelligent Data Engineering and Automated Learning, IDEAL 2016, pp. 457\u2013467. Springer, (2016)","DOI":"10.1007\/978-3-319-46257-8_49"},{"key":"731_CR41","first-page":"26","volume":"62","author":"H Robbins","year":"1955","unstructured":"Robbins, H.: A remark on Stirling\u2019s formula. Am. Math. Mon. 62, 26\u201329 (1955)","journal-title":"Am. Math. Mon."},{"key":"731_CR42","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1002\/(SICI)1098-2418(199807)12:4<313::AID-RSA1>3.0.CO;2-W","volume":"12","author":"Y Rabani","year":"1998","unstructured":"Rabani, Y., Rabinovich, Y., Sinclair, A.: A computational view of population genetics. Random Struct. Algorithms 12, 313\u2013334 (1998)","journal-title":"Random Struct. Algorithms"},{"key":"731_CR43","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.tcs.2013.09.036","volume":"545","author":"JE Rowe","year":"2014","unstructured":"Rowe, J.E., Sudholt, D.: The choice of the offspring population size in the $$(1,\\lambda )$$ evolutionary algorithm. Theor. Comput. Sci. 545, 20\u201338 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"731_CR44","doi-asserted-by":"publisher","first-page":"2511","DOI":"10.1016\/j.tcs.2009.03.003","volume":"410","author":"D Sudholt","year":"2009","unstructured":"Sudholt, D.: The impact of parametrization in memetic evolutionary algorithms. Theor. Comput. Sci. 410, 2511\u20132528 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"731_CR45","doi-asserted-by":"crossref","unstructured":"Wegener, I.: Theoretical aspects of evolutionary algorithms. In: International Colloquium on Automata, Languages, and Programming, ICALP 2001, pp. 64\u201378. Springer (2001)","DOI":"10.1007\/3-540-48224-5_6"},{"key":"731_CR46","doi-asserted-by":"crossref","unstructured":"Witt, C.: Population size vs. runtime of a simple EA. In: Congress on Evolutionary Computation, CEC 2003, pp. 1996\u20132003. IEEE (2003)","DOI":"10.1109\/CEC.2003.1299918"},{"key":"731_CR47","first-page":"65","volume":"14","author":"C Witt","year":"2006","unstructured":"Witt, C.: Runtime analysis of the ($$\\mu $$ + 1) EA on simple pseudo-Boolean functions. Evolut. Comput. 14, 65\u201386 (2006)","journal-title":"Evolut. Comput."},{"key":"731_CR48","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1016\/j.tcs.2008.05.011","volume":"403","author":"C Witt","year":"2008","unstructured":"Witt, C.: Population size versus runtime of a simple evolutionary algorithm. Theor. Comput. Sci. 403, 104\u2013120 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"731_CR49","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1017\/S0963548312000600","volume":"22","author":"C Witt","year":"2013","unstructured":"Witt, C.: Tight bounds on the optimization time of a randomized search heuristic on linear functions. Comb. Probab. Comput. 22, 294\u2013318 (2013)","journal-title":"Comb. Probab. Comput."},{"key":"731_CR50","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1109\/TEVC.2014.2378891","volume":"19","author":"Y Yang","year":"2015","unstructured":"Yang, Y., Qian, C., Zhou, Z.-H.: Switch analysis for running time analysis of evolutionary algorithms. IEEE Trans. Evolut. Comput. 19, 777\u2013792 (2015)","journal-title":"IEEE Trans. Evolut. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00731-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00731-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00731-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T11:19:23Z","timestamp":1723115963000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00731-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,25]]},"references-count":50,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["731"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00731-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,25]]},"assertion":[{"value":"28 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 June 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 June 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}