{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T00:18:28Z","timestamp":1759796308806,"version":"build-2065373602"},"reference-count":59,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2025,8,18]],"date-time":"2025-08-18T00:00:00Z","timestamp":1755475200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,8,18]],"date-time":"2025-08-18T00:00:00Z","timestamp":1755475200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Swiss Federal Institute of Technology Zurich"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Evolutionary algorithms (EAs) are general-purpose optimisation algorithms that maintain a population (multiset) of candidate solutions and apply variation operators to create new solutions called offspring. A new population is typically formed using one of two strategies: a <jats:inline-formula>\n              <jats:tex-math>$$(\\mu +\\lambda )$$<\/jats:tex-math>\n            <\/jats:inline-formula>\u00a0EA (plus selection) keeps the best <jats:inline-formula>\n              <jats:tex-math>$$\\mu $$<\/jats:tex-math>\n            <\/jats:inline-formula> search points out of the union of <jats:inline-formula>\n              <jats:tex-math>$$\\mu $$<\/jats:tex-math>\n            <\/jats:inline-formula> parents in the old population and <jats:inline-formula>\n              <jats:tex-math>$$\\lambda $$<\/jats:tex-math>\n            <\/jats:inline-formula> offspring, whereas a <jats:inline-formula>\n              <jats:tex-math>$$(\\mu ,\\lambda )$$<\/jats:tex-math>\n            <\/jats:inline-formula>\u00a0EA (comma selection) discards all parents and only keeps the best <jats:inline-formula>\n              <jats:tex-math>$$\\mu $$<\/jats:tex-math>\n            <\/jats:inline-formula> out of <jats:inline-formula>\n              <jats:tex-math>$$\\lambda $$<\/jats:tex-math>\n            <\/jats:inline-formula> offspring. Comma selection may help to escape from local optima, however when and how it is beneficial is subject to an ongoing debate. We propose a new benchmark function to investigate the benefits of comma selection: the well known benchmark function <jats:sc>OneMax<\/jats:sc>with randomly planted local optima, generated by frozen noise. We show that comma selection (the <jats:inline-formula>\n              <jats:tex-math>$${(1,\\lambda )}$$<\/jats:tex-math>\n            <\/jats:inline-formula>\u00a0EA) is faster than plus selection (the <jats:inline-formula>\n              <jats:tex-math>$${(1+\\lambda )}$$<\/jats:tex-math>\n            <\/jats:inline-formula>\u00a0EA) on this benchmark, in a fixed-target scenario, and for offspring population sizes\u00a0<jats:inline-formula>\n              <jats:tex-math>$$\\lambda $$<\/jats:tex-math>\n            <\/jats:inline-formula> for which both algorithms behave differently. For certain parameters, the <jats:inline-formula>\n              <jats:tex-math>$${(1,\\lambda )}$$<\/jats:tex-math>\n            <\/jats:inline-formula>\u00a0EAfinds the target in <jats:inline-formula>\n              <jats:tex-math>$$\\Theta (n \\ln n)$$<\/jats:tex-math>\n            <\/jats:inline-formula> evaluations, with high probability (w.h.p.), while the <jats:inline-formula>\n              <jats:tex-math>$${(1+\\lambda )}$$<\/jats:tex-math>\n            <\/jats:inline-formula>\u00a0EAw.h.p. requires <jats:inline-formula>\n              <jats:tex-math>$$\\omega (n^2)$$<\/jats:tex-math>\n            <\/jats:inline-formula> evaluations. We further show that the advantage of comma selection is not arbitrarily large: w.h.p. comma selection outperforms plus selection at most by a factor of <jats:inline-formula>\n              <jats:tex-math>$$O(n \\ln n)$$<\/jats:tex-math>\n            <\/jats:inline-formula> for most reasonable parameter choices. We develop novel methods for analysing frozen noise and give powerful and general fixed-target results with tail bounds that are of independent interest.<\/jats:p>","DOI":"10.1007\/s00453-025-01330-y","type":"journal-article","created":{"date-parts":[[2025,8,18]],"date-time":"2025-08-18T09:47:49Z","timestamp":1755510469000},"page":"1804-1863","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Comma Selection Outperforms Plus Selection on OneMax with Randomly Planted Optima"],"prefix":"10.1007","volume":"87","author":[{"given":"Joost","family":"Jorritsma","sequence":"first","affiliation":[]},{"given":"Johannes","family":"Lengler","sequence":"additional","affiliation":[]},{"given":"Dirk","family":"Sudholt","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,8,18]]},"reference":[{"issue":"4","key":"1330_CR1","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1162\/evco_a_00195","volume":"25","author":"C Doerr","year":"2017","unstructured":"Doerr, C., Lengler, J.: Introducing elitist black-box models: When does elitist behavior weaken the performance of evolutionary algorithms? Evol. Comput. 25(4), 587\u2013606 (2017)","journal-title":"Evol. Comput."},{"key":"1330_CR2","doi-asserted-by":"crossref","unstructured":"Dang, D.-C., Eremeev, A., Lehre, P.K.: Escaping local optima with non-elitist evolutionary algorithms. In: AAAI Conference on artificial intelligence (AAAI 2021), 35, 12275\u201312283 (2021)","DOI":"10.1609\/aaai.v35i14.17457"},{"key":"1330_CR3","doi-asserted-by":"crossref","unstructured":"Dang, D.-C., Eremeev, A., Lehre, P.K.: Non-elitist evolutionary algorithms excel in fitness landscapes with sparse deceptive regions and dense valleys. In: Genetic and evolutionary computation conference (GECCO 2021), pp. 1133\u20131141 (2021)","DOI":"10.1145\/3449639.3459398"},{"issue":"2","key":"1330_CR4","first-page":"87","volume":"12","author":"A Auger","year":"2022","unstructured":"Auger, A., Fonseca, C.M., Friedrich, T., Lengler, J., Gissler, A.: Theory of Randomized Optimization Heuristics (Dagstuhl Seminar 22081). Dagstuhl Rep. 12(2), 87\u2013102 (2022)","journal-title":"Dagstuhl Rep."},{"key":"1330_CR5","doi-asserted-by":"publisher","first-page":"1659","DOI":"10.1007\/s00453-021-00896-7","volume":"84","author":"B Doerr","year":"2022","unstructured":"Doerr, B.: Does comma selection help to cope with local optima? Algorithmica 84, 1659\u20131693 (2022)","journal-title":"Algorithmica"},{"key":"1330_CR6","doi-asserted-by":"crossref","unstructured":"J\u00e4gersk\u00fcpper, J., Storch, T.: When the plus strategy outperforms the comma strategy and when not. In: Foundations of computational intelligence (FOCI 2007), pp. 25\u201332 (2007)","DOI":"10.1109\/FOCI.2007.372143"},{"key":"1330_CR7","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. Theoret. Comput. Sci. 545, 20\u201338 (2014)","journal-title":"Theoret. Comput. Sci."},{"key":"1330_CR8","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2023.104061","volume":"328","author":"MA Hevia Fajardo","year":"2024","unstructured":"Hevia Fajardo, M.A., Sudholt, D.: Self-adjusting offspring population sizes outperform fixed parameters on the Cliff function. Artif. Intell. 328, 104061 (2024). https:\/\/doi.org\/10.1016\/j.artint.2023.104061","journal-title":"Artif. Intell."},{"key":"1330_CR9","doi-asserted-by":"crossref","unstructured":"Kaufmann, M., Larcher, M., Lengler, J., Zou, X.: Self-adjusting population sizes for the (1, $$\\lambda $$)-EA on monotone functions. In: Parallel problem solving from nature (PPSN 2022), pp. 569\u2013585 (2022). Springer","DOI":"10.1007\/978-3-031-14721-0_40"},{"key":"1330_CR10","doi-asserted-by":"crossref","unstructured":"Kaufmann, M., Larcher, M., Lengler, J., Zou, X.: OneMax is not the easiest function for fitness improvements. In: Evolutionary computation in combinatorial optimization (EvoCOP 2023), pp. 162\u2013178. Springer, New York (2023)","DOI":"10.1007\/978-3-031-30035-6_11"},{"key":"1330_CR11","doi-asserted-by":"crossref","unstructured":"Hevia\u00a0Fajardo, M.A., Sudholt, D.: Hard problems are easier for success-based parameter control. In: Genetic and evolutionary computation conference (GECCO 2022), pp. 796\u2013804 (2022)","DOI":"10.1145\/3512290.3528781"},{"key":"1330_CR12","doi-asserted-by":"crossref","unstructured":"Droste, S.: Analysis of the (1+1)\u00a0EA for a noisy OneMax. In: Proceedings of the genetic and evolutionary computation conference (GECCO 2004), pp. 1088\u20131099. Springer, New York (2004)","DOI":"10.1007\/978-3-540-24854-5_107"},{"issue":"3","key":"1330_CR13","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":"3","key":"1330_CR14","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(3), 428\u2013461 (2016)","journal-title":"Algorithmica"},{"issue":"1","key":"1330_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1162\/evco_a_00170","volume":"26","author":"C Qian","year":"2018","unstructured":"Qian, C., Yu, Y., Zhou, Z.-H.: Analyzing evolutionary optimization in noisy environments. Evol. Comput. 26(1), 1\u201341 (2018)","journal-title":"Evol. Comput."},{"key":"1330_CR16","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. Algorithmica (2018)","DOI":"10.1145\/3071178.3071347"},{"issue":"4","key":"1330_CR17","doi-asserted-by":"publisher","first-page":"976","DOI":"10.1007\/s00453-020-00671-0","volume":"83","author":"D Sudholt","year":"2021","unstructured":"Sudholt, D.: Analysing the robustness of evolutionary algorithms to noise: refined runtime bounds and an example where noise is beneficial. Algorithmica 83(4), 976\u20131011 (2021)","journal-title":"Algorithmica"},{"key":"1330_CR18","doi-asserted-by":"crossref","unstructured":"Bian, C., Qian, C., Tang, K.: Towards a running time analysis of the (1+1)-EA for OneMax and LeadingOnes under general bit-wise noise. In: Parallel problem solving from nature (PPSN 2018), pp. 165\u2013177. Springer, Cham (2018)","DOI":"10.1007\/978-3-319-99259-4_14"},{"key":"1330_CR19","doi-asserted-by":"crossref","unstructured":"Prugel-Bennett, A., Rowe, J., Shapiro, J.: Run-time analysis of population-based evolutionary algorithm in noisy environments. In: Foundations of genetic algorithms (FOGA\u00a02015), pp. 69\u201375. ACM, New York (2015)","DOI":"10.1145\/2725494.2725498"},{"key":"1330_CR20","doi-asserted-by":"crossref","unstructured":"Dang, D.-C., Lehre, P.K.: Efficient optimisation of noisy fitness functions with population-based evolutionary algorithms. In: Foundations of genetic algorithms (FOGA 2015), pp. 62\u201368. ACM, New York (2015)","DOI":"10.1145\/2725494.2725508"},{"issue":"4","key":"1330_CR21","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1007\/s00453-011-9606-2","volume":"64","author":"D Sudholt","year":"2012","unstructured":"Sudholt, D., Thyssen, C.: A simple ant colony optimizer for stochastic shortest path problems. Algorithmica 64(4), 643\u2013672 (2012)","journal-title":"Algorithmica"},{"key":"1330_CR22","doi-asserted-by":"crossref","unstructured":"Doerr, B., Hota, A., K\u00f6tzing, T.: Ants easily solve stochastic shortest path problems. In: Genetic and evolutionary computation conference (GECCO 2012), pp. 17\u201324 (2012)","DOI":"10.1145\/2330163.2330167"},{"key":"1330_CR23","doi-asserted-by":"crossref","unstructured":"Feldmann, M., K\u00f6tzing, T.: Optimizing expected path lengths with ant colony optimization using fitness proportional update. In: Foundations of genetic algorithms (FOGA 2013), pp. 65\u201374. ACM, New York (2013)","DOI":"10.1145\/2460239.2460246"},{"issue":"3","key":"1330_CR24","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."},{"key":"1330_CR25","doi-asserted-by":"crossref","unstructured":"Dang, D.-C., Opris, A., Salehi, B., Sudholt, D.: Analysing the robustness of NSGA-II under noise. In: Genetic and evolutionary computation conference (GECCO\u00a02023), pp. 642\u2013651 (2023)","DOI":"10.1145\/3583131.3590421"},{"key":"1330_CR26","doi-asserted-by":"crossref","unstructured":"Dinot, M., Doerr, B., Hennebelle, U., Will, S.: Runtime analyses of multi-objective evolutionary algorithms in the presence of noise. In: International joint conference on artificial intelligence (IJCAI\u00a02023) (2023)","DOI":"10.24963\/ijcai.2023\/616"},{"key":"1330_CR27","doi-asserted-by":"crossref","unstructured":"Friedrich, T., K\u00f6tzing, T., Neumann, F., Radhakrishnan, A.: Theoretical study of optimizing rugged landscapes with the cGA. In: Parallel problem solving from nature (PPSN\u00a02022), pp. 586\u2013599. Springer, New York (2022)","DOI":"10.1007\/978-3-031-14721-0_41"},{"key":"1330_CR28","doi-asserted-by":"crossref","unstructured":"Dang, D.-C., Lehre, P.K.: The SLO hierarchy of pseudo-boolean functions and runtime of evolutionary algorithms. In: Genetic and evolutionary computation conference (GECCO 2024), pp. 1551\u20131559 (2024)","DOI":"10.1145\/3638529.3654221"},{"key":"1330_CR29","doi-asserted-by":"crossref","unstructured":"Lengler, J., Schiller, L., Sieberling, O.: Plus strategies are exponentially slower for planted optima of random height. In: Genetic and evolutionary computation conference (GECCO 2024), pp. 1587\u20131595 (2024)","DOI":"10.1145\/3638529.3654088"},{"issue":"6","key":"1330_CR30","doi-asserted-by":"publisher","first-page":"1762","DOI":"10.1007\/s00453-021-00881-0","volume":"84","author":"M Buzdalov","year":"2022","unstructured":"Buzdalov, M., Doerr, B., Doerr, C., Vinokurov, D.: Fixed-target runtime analysis. Algorithmica 84(6), 1762\u20131793 (2022)","journal-title":"Algorithmica"},{"key":"1330_CR31","doi-asserted-by":"crossref","unstructured":"Lehre, P.K.: Fitness-levels for non-elitist populations. In: Genetic and evolutionary computation conference (GECCO 2011), pp. 2075\u20132082 (2011)","DOI":"10.1145\/2001576.2001855"},{"key":"1330_CR32","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 (2019)","DOI":"10.1145\/3321707.3321838"},{"key":"1330_CR33","doi-asserted-by":"crossref","unstructured":"Jorritsma, J., Lengler, J., Sudholt, D.: Comma selection outperform plus selection on OneMax with randomly planted optima. In: Genetic and evolutionary computation conference (GECCO\u00a02023). ACM Press, New York (2023). To appear","DOI":"10.1145\/3583131.3590488"},{"key":"1330_CR34","doi-asserted-by":"crossref","unstructured":"Lengler, J.: Drift analysis. In: Theory of evolutionary computation, pp. 89\u2013131. Springer, New York (2020)","DOI":"10.1007\/978-3-030-29414-4_2"},{"key":"1330_CR35","unstructured":"Johannsen, D.: Random combinatorial structures and randomized search heuristics. PhD thesis, Universit\u00e4t des Saarlandes (2010)"},{"issue":"1","key":"1330_CR36","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(1), 224\u2013250 (2013)","journal-title":"Algorithmica"},{"key":"1330_CR37","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.113757","author":"J Bossek","year":"2023","unstructured":"Bossek, J., Sudholt, D.: Do additional target points speed up evolutionary algorithms? Theor. Comput. Sci. (2023). https:\/\/doi.org\/10.1016\/j.tcs.2023.113757","journal-title":"Theor. Comput. Sci."},{"key":"1330_CR38","doi-asserted-by":"crossref","unstructured":"Doerr, B.: Probabilistic tools for the analysis of randomized optimization heuristics. In: Theory of evolutionary computation, pp. 1\u201387. Springer, New York (2020)","DOI":"10.1007\/978-3-030-29414-4_1"},{"key":"1330_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.spl.2017.11.017","volume":"135","author":"S Janson","year":"2018","unstructured":"Janson, S.: Tail bounds for sums of geometric and exponential variables. Stat. Probab. Lett. 135, 1\u20136 (2018)","journal-title":"Stat. Probab. Lett."},{"issue":"2","key":"1330_CR40","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1007\/S00453-023-01153-9","volume":"86","author":"MA Hevia Fajardo","year":"2024","unstructured":"Hevia Fajardo, M.A., Sudholt, D.: Self-adjusting population sizes for non-elitist evolutionary algorithms: why success rates matter. Algorithmica 86(2), 526\u2013565 (2024). https:\/\/doi.org\/10.1007\/S00453-023-01153-9","journal-title":"Algorithmica"},{"issue":"64","key":"1330_CR41","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1007\/s00453-012-9622-x","volume":"4","author":"B Doerr","year":"2012","unstructured":"Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. Algorithmica 4(64), 673\u2013697 (2012)","journal-title":"Algorithmica"},{"issue":"3","key":"1330_CR42","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1109\/TEVC.2012.2202241","volume":"17","author":"D Sudholt","year":"2013","unstructured":"Sudholt, D.: A new method for lower bounds on the running time of evolutionary algorithms. IEEE Trans. Evol. Comput. 17(3), 418\u2013435 (2013)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"2","key":"1330_CR43","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(2), 294\u2013318 (2013)","journal-title":"Comb. Probab. Comput."},{"key":"1330_CR44","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. Theoret. Comput. Sci. 773, 115\u2013137 (2019)","journal-title":"Theoret. Comput. Sci."},{"key":"1330_CR45","doi-asserted-by":"publisher","first-page":"3059","DOI":"10.1007\/s00453-020-00780-w","volume":"83","author":"B Doerr","year":"2021","unstructured":"Doerr, B.: The runtime of the compact genetic algorithm on jump functions. Algorithmica 83, 3059\u20133107 (2021)","journal-title":"Algorithmica"},{"issue":"4","key":"1330_CR46","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1162\/106365605774666921","volume":"13","author":"T Jansen","year":"2005","unstructured":"Jansen, T., Jong, K., Wegener, I.: On the choice of the offspring population size in evolutionary algorithms. Evol. Comput. 13(4), 413\u2013440 (2005)","journal-title":"Evol. Comput."},{"key":"1330_CR47","doi-asserted-by":"crossref","unstructured":"L\u00e4ssig, J., Sudholt, D.: Adaptive population models for offspring populations and parallel evolutionary algorithms. In: Foundations of genetic algorithms (FOGA 2011), pp. 181\u2013192. ACM, New York (2011)","DOI":"10.1145\/1967654.1967671"},{"issue":"2","key":"1330_CR48","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(2), 587\u2013609 (2017)","journal-title":"Algorithmica"},{"key":"1330_CR49","doi-asserted-by":"crossref","unstructured":"Doerr, B., K\u00fcnnemann, M.: How the (1+$$\\lambda $$) evolutionary algorithm optimizes linear functions. In: Genetic and evolutionary computation conference (GECCO\u00a02013), pp. 1589\u20131596. ACM, New York (2013)","DOI":"10.1145\/2463372.2463569"},{"key":"1330_CR50","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, New York (2014)","DOI":"10.1007\/978-3-319-10762-2_88"},{"issue":"6","key":"1330_CR51","doi-asserted-by":"publisher","first-page":"1010","DOI":"10.1109\/TEVC.2019.2954234","volume":"24","author":"PK Lehre","year":"2020","unstructured":"Lehre, P.K., Sudholt, D.: Parallel black-box complexity with tail bounds. IEEE Trans. Evol. Comput. 24(6), 1010\u20131024 (2020)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"4","key":"1330_CR52","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1017\/S0963548320000565","volume":"30","author":"PK Lehre","year":"2021","unstructured":"Lehre, P.K., Witt, C.: Tail bounds on hitting times of randomized search heuristics using variable drift analysis. Comb. Probab. Comput. 30(4), 550\u2013569 (2021)","journal-title":"Comb. Probab. Comput."},{"issue":"2","key":"1330_CR53","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1007\/s00453-016-0212-1","volume":"78","author":"T Paix\u00e3o","year":"2017","unstructured":"Paix\u00e3o, T., P\u00e9rez Heredia, J., Sudholt, D., Trubenov\u00e1, B.: Towards a runtime comparison of natural and artificial evolution. Algorithmica 78(2), 681\u2013713 (2017)","journal-title":"Algorithmica"},{"key":"1330_CR54","doi-asserted-by":"crossref","unstructured":"Hevia\u00a0Fajardo, M.A., Sudholt, D.: Self-adjusting population sizes for non-elitist Evolutionary Algorithms: Why success rates matter. In: Genetic and evolutionary computation conference (GECCO 2021), pp. 1151\u20131159 (2021)","DOI":"10.1145\/3449639.3459338"},{"key":"1330_CR55","unstructured":"Feller, W., et al.: An introduction to probability theory and its applications (1971)"},{"key":"1330_CR56","doi-asserted-by":"crossref","unstructured":"Lehre, P.K., Qin, X.: More precise runtime analyses of non-elitist evolutionary algorithms in uncertain environments. Algorithmica, 1\u201346 (2022)","DOI":"10.1007\/s00453-022-01044-5"},{"key":"1330_CR57","doi-asserted-by":"crossref","unstructured":"Happ, E., Johannsen, D., Klein, C., Neumann, F.: Rigorous analyses of fitness-proportional selection for optimizing linear functions. In: Genetic and evolutionary computation conference (GECCO 2008), pp. 953\u2013960 (2008)","DOI":"10.1145\/1389095.1389277"},{"key":"1330_CR58","doi-asserted-by":"crossref","unstructured":"Goldberg, D.E., Deb, K.: A comparative analysis of selection schemes used in genetic algorithms. In: Foundations of genetic algorithms (FOGA 1991) vol. 1, pp. 69\u201393 (1991)","DOI":"10.1016\/B978-0-08-050684-5.50008-2"},{"key":"1330_CR59","doi-asserted-by":"crossref","unstructured":"Lehre, P.K.: Negative drift in populations. In: Parallel problem solving from nature (PPSN 2010), pp. 244\u2013253 (2010). Springer","DOI":"10.1007\/978-3-642-15844-5_25"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01330-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01330-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01330-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T08:08:10Z","timestamp":1759738090000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01330-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,18]]},"references-count":59,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["1330"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01330-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2025,8,18]]},"assertion":[{"value":"12 June 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 June 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 August 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no Conflict of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}