{"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":1783749321661,"version":"3.55.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2020,7,15]],"date-time":"2020-07-15T00:00:00Z","timestamp":1594771200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,7,15]],"date-time":"2020-07-15T00:00:00Z","timestamp":1594771200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/M004252\/1"],"award-info":[{"award-number":["EP\/M004252\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>It is generally accepted that populations are useful for the global exploration of multi-modal optimisation problems. Indeed, several theoretical results are available showing such advantages over single-trajectory search heuristics. In this paper we provide evidence that evolving populations via crossover and mutation may also benefit the optimisation time for hillclimbing unimodal functions. In particular, we prove bounds on the expected runtime of the standard (<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mu +1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03bc<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>) GA for OneMax that are lower than its unary black box complexity and decrease in the leading constant with the population size up to <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mu =o\\left( \\sqrt{\\log n}\\right) $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03bc<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>o<\/mml:mi>\n                    <mml:mfenced>\n                      <mml:msqrt>\n                        <mml:mrow>\n                          <mml:mo>log<\/mml:mo>\n                          <mml:mi>n<\/mml:mi>\n                        <\/mml:mrow>\n                      <\/mml:msqrt>\n                    <\/mml:mfenced>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Our analysis suggests that the optimal mutation strategy is to flip two bits most of the time. To achieve the results we provide two interesting contributions to the theory of randomised search heuristics: (1) A novel application of drift analysis which compares absorption times of different Markov chains without defining an explicit potential function. (2) The inversion of fundamental matrices to calculate the absorption times of the Markov chains. The latter strategy was previously proposed in the literature but to the best of our knowledge this is the first time is has been used to show non-trivial bounds on expected runtimes.<\/jats:p>","DOI":"10.1007\/s00453-020-00743-1","type":"journal-article","created":{"date-parts":[[2020,7,15]],"date-time":"2020-07-15T07:03:46Z","timestamp":1594796626000},"page":"3676-3706","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":26,"title":["On the Benefits of Populations for the Exploitation Speed of Standard Steady-State Genetic Algorithms"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4151-2734","authenticated-orcid":false,"given":"Dogan","family":"Corus","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pietro S.","family":"Oliveto","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,7,15]]},"reference":[{"issue":"5","key":"743_CR1","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."},{"issue":"5","key":"743_CR2","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1109\/TEVC.2017.2745715","volume":"22","author":"D Corus","year":"2018","unstructured":"Corus, D., Oliveto, P.S.: Standard steady state genetic algorithms can hillclimb faster than mutation-only evolutionary algorithms. IEEE Trans. Evolut. Comput. 22(5), 720\u2013732 (2018)","journal-title":"IEEE Trans. Evolut. Comput."},{"key":"743_CR3","doi-asserted-by":"crossref","unstructured":"Corus, D., Oliveto, P.S.: On the benefits of populations for the exploitation speed of standard steady-state genetic algorithms. In: Proceedings of the Genetic and Evolutionary Computation Conference, Proc. of GECCO\u201919, pp. 1452\u20131460 (2019)","DOI":"10.1145\/3321707.3321783"},{"issue":"3","key":"743_CR4","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1109\/TEVC.2017.2724201","volume":"22","author":"DC 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 Trans. Evolut. Comput. 22(3), 484\u2013497 (2018)","journal-title":"IEEE Trans. Evolut. Comput."},{"key":"743_CR5","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":"743_CR6","doi-asserted-by":"crossref","unstructured":"Doerr, B., Doerr, C.: Optimal parameter choices through self-adjustment: applying the 1\/5-th rule in discrete settings. In: Proceedings of GECCO\u201915, pp. 1335\u20131342 (2015)","DOI":"10.1145\/2739480.2754684"},{"key":"743_CR7","doi-asserted-by":"crossref","unstructured":"Doerr, B., Doerr, C.: A tight runtime analysis of the (1+(\u03bb, \u03bb)) genetic algorithm on OneMax. In: Proceedings of GECCO\u201915, pp. 1423\u20131430 (2015)","DOI":"10.1145\/2739480.2754683"},{"key":"743_CR8","doi-asserted-by":"crossref","unstructured":"Doerr, B., Doerr, C., Yang, J.: Optimal parameter choices via precise black-box analysis. In: Proceedings of GECCO\u201916, pp. 1123\u20131130 (2016)","DOI":"10.1145\/2908812.2908950"},{"key":"743_CR9","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)"},{"issue":"4","key":"743_CR10","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1162\/evco.2009.17.4.17401","volume":"17","author":"T Friedrich","year":"2009","unstructured":"Friedrich, T., Oliveto, P.S., Sudholt, D., Witt, C.: Analysis of diversity-preserving mechanisms for global exploration. Evolut. Comput. 17(4), 455\u2013476 (2009)","journal-title":"Evolut. Comput."},{"issue":"1\u20132","key":"743_CR11","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., Yao, X.: Towards an analytic framework for analysing the computation time of evolutionary algorithms. Artif. Intell. 145(1\u20132), 59\u201397 (2003)","journal-title":"Artif. Intell."},{"key":"743_CR12","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":"743_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17339-4","volume-title":"Analyzing Evolutionary Algorithms: The Computer Science Perspective","author":"T Jansen","year":"2013","unstructured":"Jansen, T.: Analyzing Evolutionary Algorithms: The Computer Science Perspective. Springer, Berlin (2013)"},{"issue":"1","key":"743_CR14","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/s00453-002-0940-2","volume":"34","author":"T Jansen","year":"2002","unstructured":"Jansen, T., Wegener, I.: The analysis of evolutionary algorithms-a proof that crossover really can help. Algorithmica 34(1), 47\u201366 (2002)","journal-title":"Algorithmica"},{"key":"743_CR15","volume-title":"Handbook of Heuristics","author":"PK Lehre","year":"2018","unstructured":"Lehre, P.K., Oliveto, P.S.: Theoretical analysis of stochastic search algorithms. In: Resende, R.M.M.G.C., Pardalos, P.M. (eds.) Handbook of Heuristics. Springer, Berlin (2018)"},{"issue":"4","key":"743_CR16","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"},{"issue":"9","key":"743_CR17","doi-asserted-by":"publisher","first-page":"1675","DOI":"10.1007\/s00500-010-0610-2","volume":"15","author":"PK Lehre","year":"2011","unstructured":"Lehre, P.K., Yao, X.: Crossover can be constructive when computing unique input-output sequences. Soft Comput. 15(9), 1675\u20131687 (2011)","journal-title":"Soft Comput."},{"key":"743_CR18","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/978-3-030-29414-4_2","volume-title":"Theory of Evolutionary Computation: Recent Developments in Discrete Optimization","author":"J Lengler","year":"2020","unstructured":"Lengler, J.: Drift analysis. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pp. 89\u2013131. Springer, Berlin (2020)"},{"key":"743_CR19","doi-asserted-by":"crossref","unstructured":"Lengler, J.: A general dichotomy of evolutionary algorithms on monotone functions. In: Proceedings of PPSN XV, pp. 3\u201315. Springer (2018)","DOI":"10.1007\/978-3-319-99259-4_1"},{"key":"743_CR20","doi-asserted-by":"crossref","unstructured":"Lengler, J., Zou, X.: Exponential slowdown for larger populations: The (\u03bc + 1)-ea on monotone functions. In: Proceedings of FOGA, pp. 87\u2013101 (2019)","DOI":"10.1145\/3299904.3340309"},{"issue":"5","key":"743_CR21","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1016\/j.laa.2010.04.042","volume":"433","author":"HB Li","year":"2010","unstructured":"Li, H.B., Huang, T.Z., Liu, X.P., Li, H.: On the inverses of general tridiagonal matrices. Linear Algebra Appl. 433(5), 965\u2013983 (2010)","journal-title":"Linear Algebra Appl."},{"key":"743_CR22","first-page":"51","volume-title":"Advances in Neural Information Processing Systems","author":"M Mitchell","year":"1994","unstructured":"Mitchell, M., Holland, J.H., Forrest, S.: When will a genetic algorithm outperform hill climbing. In: Cowan, J.D., Tesauro, G., Alspector, J. (eds.) Advances in Neural Information Processing Systems, vol. 6, pp. 51\u201358. Morgan Kaufmann Publishers, Burlington (1994)"},{"key":"743_CR23","doi-asserted-by":"crossref","unstructured":"Neumann, F., Oliveto, P.S., Rudolph, G., Sudholt, D.: On the effectiveness of crossover for migration in parallel evolutionary algorithms. In: Proceedings of GECCO\u201911, pp. 1587\u20131594 (2011)","DOI":"10.1145\/2001576.2001790"},{"key":"743_CR24","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2013.06.015","volume":"545","author":"PS Oliveto","year":"2014","unstructured":"Oliveto, P.S., Witt, C.: On the runtime analysis of the simple genetic algorithm. Theor. Comput. Sci. 545, 2\u201319 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"743_CR25","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.tcs.2015.01.002","volume":"605","author":"PS Oliveto","year":"2015","unstructured":"Oliveto, P.S., Witt, C.: Improved time complexity analysis of the simple genetic algorithm. Theor. Comput. Sci. 605, 21\u201341 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"743_CR26","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1142\/9789814282673_0002","volume-title":"Theory of Randomized Search Heuristics: Foundations and Recent Developments","author":"PS Oliveto","year":"2011","unstructured":"Oliveto, P.S., Yao, X.: Runtime analysis of evolutionary algorithms for discrete optimization. In: Doerr, B., Auger, A. (eds.) Theory of Randomized Search Heuristics: Foundations and Recent Developments, p. 21. World Scientific, Singapore (2011)"},{"key":"743_CR27","doi-asserted-by":"crossref","unstructured":"Oliveto, P.S., Sudholt, D., Witt, C.: A tight lower bound on the expected runtime of\nstandard steady state genetic algorithms. In: Proceedings of GECCO\u201920, p. 1323\u20131331 (2020)","DOI":"10.1145\/3377930.3390212"},{"key":"743_CR28","doi-asserted-by":"crossref","unstructured":"Pinto, E.C., Doerr, C.: A simple proof for the usefulness of crossover in black-box optimization. In: Proceedings of PPSN XV, pp. 29\u201341 (2018)","DOI":"10.1007\/978-3-319-99259-4_3"},{"key":"743_CR29","volume-title":"Handbook of Evolutionary Computation","author":"J Sarma","year":"1997","unstructured":"Sarma, J., Jong, K.D.: Generation gap methods. In: Back, T., Fogel, D.B., Michalewicz, Z. (eds.) Handbook of Evolutionary Computation. IOP Publishing Ltd, Bristol (1997)"},{"issue":"3","key":"743_CR30","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. Evolut. Comput. 17(3), 418\u2013435 (2013)","journal-title":"IEEE Trans. Evolut. Comput."},{"issue":"2","key":"743_CR31","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1162\/EVCO_a_00171","volume":"25","author":"D Sudholt","year":"2017","unstructured":"Sudholt, D.: How crossover speeds up building block assembly in genetic algorithms. Evolut. Comput. 25(2), 237\u2013274 (2017)","journal-title":"Evolut. Comput."},{"key":"743_CR32","doi-asserted-by":"crossref","unstructured":"Sudholt, D.: Crossover is provably essential for the ising model on trees. In: Proceedings of GECCO\u201911, pp. 1161\u20131167. New York, New York, USA (2005)","DOI":"10.1145\/1068009.1068202"},{"key":"743_CR33","doi-asserted-by":"crossref","unstructured":"Sutton, A.: Crossover can simulate bounded tree search on a fixed-parameter tractable optimization problem. In: Proceedings of GECCO\u201918, pp. 1531\u20131538 (2018)","DOI":"10.1145\/3205455.3205598"},{"issue":"1","key":"743_CR34","first-page":"65","volume":"14","author":"C Witt","year":"2006","unstructured":"Witt, C.: Runtime analysis of the (\u03bc + 1) ea on simple pseudo-boolean functions. Evolut. Comput. 14(1), 65\u201386 (2006)","journal-title":"Evolut. Comput."},{"issue":"2","key":"743_CR35","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. Combin. Probab. Comput. 22(2), 294\u2013318 (2013)","journal-title":"Combin. Probab. Comput."},{"issue":"6","key":"743_CR36","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1109\/TEVC.2014.2378891","volume":"19","author":"Y Yu","year":"2015","unstructured":"Yu, Y., Qian, C., Zhou, Z.H.: Switch analysis for running time analysis of evolutionary algorithms. IEEE Trans. Evolut. Comput. 19(6), 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-00743-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00743-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00743-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,14]],"date-time":"2021-07-14T23:58:35Z","timestamp":1626307115000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00743-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,15]]},"references-count":36,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["743"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00743-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,15]]},"assertion":[{"value":"21 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 June 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 July 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}