{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T00:27:33Z","timestamp":1772497653137,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,12,23]],"date-time":"2021-12-23T00:00:00Z","timestamp":1640217600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,12,23]],"date-time":"2021-12-23T00:00:00Z","timestamp":1640217600000},"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":"crossref","award":["EP\/M004252\/1"],"award-info":[{"award-number":["EP\/M004252\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Recent progress in the runtime analysis of evolutionary algorithms (EAs) has allowed the derivation of upper bounds on the expected runtime of standard steady-state genetic algorithms (GAs). These upper bounds have shown speed-ups of the GAs using crossover and mutation over the same algorithms that only use mutation operators (i.e., steady-state EAs) both for standard unimodal (i.e., <jats:sc>OneMax<\/jats:sc>) and multimodal (i.e., <jats:sc>Jump<\/jats:sc>) benchmark functions. The bounds suggest that populations are beneficial to the GA as well as higher mutation rates than the default 1\/<jats:italic>n<\/jats:italic> rate. However, making rigorous claims was not possible because matching lower bounds were not available. Proving lower bounds on crossover-based EAs is a notoriously difficult task as it is hard to capture the progress that a diverse population can make. We use a potential function approach to prove a tight lower bound on the expected runtime of the (2+1)\u00a0GA for <jats:sc>OneMax<\/jats:sc> for all mutation rates <jats:italic>c<\/jats:italic>\/<jats:italic>n<\/jats:italic> with <jats:inline-formula><jats:alternatives><jats:tex-math>$$c &lt; 1.422$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>c<\/mml:mi>\n                    <mml:mo>&lt;<\/mml:mo>\n                    <mml:mn>1.422<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This provides the last piece of the puzzle that completes the proof that larger population sizes improve the performance of the standard steady-state GA for <jats:sc>OneMax<\/jats:sc> for various mutation rates, and it proves that the optimal mutation rate for the (2+1)\u00a0GA on <jats:sc>OneMax<\/jats:sc> is <jats:inline-formula><jats:alternatives><jats:tex-math>$$(\\sqrt{97}-5)\/(4n) \\approx 1.2122\/n$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:msqrt>\n                        <mml:mn>97<\/mml:mn>\n                      <\/mml:msqrt>\n                      <mml:mo>-<\/mml:mo>\n                      <mml:mn>5<\/mml:mn>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mn>4<\/mml:mn>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>\u2248<\/mml:mo>\n                    <mml:mn>1.2122<\/mml:mn>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00453-021-00893-w","type":"journal-article","created":{"date-parts":[[2021,12,23]],"date-time":"2021-12-23T04:19:39Z","timestamp":1640233179000},"page":"1603-1658","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Tight Bounds on the Expected Runtime of a Standard Steady State Genetic Algorithm"],"prefix":"10.1007","volume":"84","author":[{"given":"Pietro S.","family":"Oliveto","sequence":"first","affiliation":[]},{"given":"Dirk","family":"Sudholt","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6105-7700","authenticated-orcid":false,"given":"Carsten","family":"Witt","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,12,23]]},"reference":[{"key":"893_CR1","volume-title":"Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables","author":"M Abramowitz","year":"1964","unstructured":"Abramowitz, M., Stegun, I.A.: Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, tenth GPO printing edition Dover, Ninth Dover Printing, New York (1964)","edition":"tenth GPO print"},{"key":"893_CR2","volume-title":"Theory of Randomized Search Heuristics","year":"2011","unstructured":"Auger, A., Doerr, B. (eds.): Theory of Randomized Search Heuristics. World Scientific Publishing, Springer (2011)"},{"key":"893_CR3","doi-asserted-by":"crossref","unstructured":"Carvalho Pinto, E., Doerr, C.: A simple proof for the usefulness of crossover in black-box optimization. In: Auger, A., Fonseca, C.M., Louren\u00e7o, N., Machado, P., Paquete, L., Whitley, D. (eds) Parallel Problem Solving From Nature - PPSN XV, volume 11102 of LNCS, pp. 29\u201341. Springer (2018)","DOI":"10.1007\/978-3-319-99259-4_3"},{"key":"893_CR4","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H Chernoff","year":"1952","unstructured":"Chernoff, H.: A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Stat. 23, 493\u2013507 (1952)","journal-title":"Ann. Math. Stat."},{"issue":"5","key":"893_CR5","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. Evol. Comput. 22(5), 720\u2013732 (2018)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"12","key":"893_CR6","doi-asserted-by":"publisher","first-page":"3676","DOI":"10.1007\/s00453-020-00743-1","volume":"82","author":"D Corus","year":"2020","unstructured":"Corus, D., Oliveto, P.S.: On the benefits of populations for the exploitation speed of standard steady-state genetic algorithms. Algorithmica 82(12), 3676\u20133706 (2020)","journal-title":"Algorithmica"},{"issue":"3","key":"893_CR7","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 Trans. Evol. Comput. 22(3), 484\u2013497 (2018)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"893_CR8","doi-asserted-by":"crossref","unstructured":"Dang, D.-C., Friedrich, T., Krejca, M.S., K\u00f6tzing, T., Lehre, P.K., Oliveto, P.S., Sudholt, D., Sutton, A.M.: Escaping local optima with diversity-mechanisms and crossover. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2016), pp. 645\u2013652. ACM Press (2016)","DOI":"10.1145\/2908812.2908956"},{"key":"893_CR9","doi-asserted-by":"crossref","unstructured":"Doerr, B.: Probabilistic tools for the analysis of randomized optimization heuristics. In: Doerr, B., Neumann, F. (eds) Theory of Evolutionary Computation\u2013Recent Developments in Discrete Optimization, Natural Computing Series, pp. 1\u201387. Springer (2020)","DOI":"10.1007\/978-3-030-29414-4_1"},{"key":"893_CR10","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. Theoret. Comput. Sci. 425, 17\u201333 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"893_CR11","doi-asserted-by":"crossref","unstructured":"Doerr, B., Neumann, F. (eds.): Theory of Evolutionary Computation-Recent Developments in Discrete Optimization. Springer, Natural Computing Series (2020)","DOI":"10.1007\/978-3-030-29414-4"},{"key":"893_CR12","series-title":"Optimization and Machine Learning","volume-title":"Genetic Algorithms in Search","author":"DE Goldberg","year":"1989","unstructured":"Goldberg, D.E.: Genetic Algorithms in Search. Optimization and Machine Learning, Addison-Wesley Longman, LOndon (1989)"},{"key":"893_CR13","unstructured":"Gruder, O.: The theory of risk. In: 9th International Congress of Actuaries, vol 2, pp. 222 (1930)"},{"key":"893_CR14","doi-asserted-by":"crossref","unstructured":"Hwang, H.-K., Panholzer, A., Rolin, N., Tsai, T.-H., Chen, W.-M.: Probabilistic analysis of the (1+1)-evolutionary algorithm. Evolut. Comput. 26(2) (2018)","DOI":"10.1162\/evco_a_00212"},{"key":"893_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17339-4","volume-title":"Analyzing Evolutionary Algorithms\u2014The Computer Science Perspective","author":"T Jansen","year":"2013","unstructured":"Jansen, T.: Analyzing Evolutionary Algorithms\u2014The Computer Science Perspective. Springer, Berlin (2013)"},{"issue":"1","key":"893_CR16","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.: On the analysis of evolutionary algorithms\u2014a proof that crossover really can help. Algorithmica 34(1), 47\u201366 (2002)","journal-title":"Algorithmica"},{"issue":"3\u20134","key":"893_CR17","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1093\/biomet\/44.3-4.532","volume":"44","author":"NL Johnson","year":"1957","unstructured":"Johnson, N.L.: A note on the mean deviation of the binomial distribution. Biometrika 44(3\u20134), 532\u2013533 (1957)","journal-title":"Biometrika"},{"key":"893_CR18","doi-asserted-by":"crossref","unstructured":"K\u00f6tzing, T., Sudholt, D., Theile, M.: How crossover helps in pseudo-Boolean optimization. In: Proceedings of the 13th Annual Genetic and Evolutionary Computation Conference (GECCO\u00a02011), pp. 989\u2013996. ACM Press (2011)","DOI":"10.1145\/2001576.2001711"},{"issue":"4","key":"893_CR19","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":"893_CR20","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\u2013output sequences. Soft. Comput. 15(9), 1675\u20131687 (2011)","journal-title":"Soft. Comput."},{"issue":"6","key":"893_CR21","doi-asserted-by":"publisher","first-page":"995","DOI":"10.1109\/TEVC.2019.2917014","volume":"24","author":"J Lengler","year":"2020","unstructured":"Lengler, J.: A general dichotomy of evolutionary algorithms on monotone functions. IEEE Trans. Evol. Comput. 24(6), 995\u20131009 (2020)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"893_CR22","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 the Genetic and Evolutionary Computation Conference (GECCO\u00a02011), pp. 1587\u20131594. ACM Press (2011)","DOI":"10.1145\/2001576.2001790"},{"key":"893_CR23","volume-title":"Bioinspired Computation in Combinatorial Optimization\u2014Algorithms and Their Computational Complexity","author":"F Neumann","year":"2010","unstructured":"Neumann, F., Witt, C.: Bioinspired Computation in Combinatorial Optimization\u2014Algorithms and Their Computational Complexity. Springer, Berlin (2010)"},{"key":"893_CR24","doi-asserted-by":"crossref","unstructured":"Oliveto, P.S., Sudholt, D., Witt, C.: A tight lower bound on the expected runtime of standard steady state genetic algorithms. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2020), pp. 1323\u20131331. ACM (2020)","DOI":"10.1145\/3377930.3390212"},{"key":"893_CR25","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. Theoret. Comput. Sci. 545, 2\u201319 (2014)","journal-title":"Theoret. Comput. Sci."},{"key":"893_CR26","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. Theoret. Comput. Sci. 605, 21\u201341 (2015)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"893_CR27","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. Evol. Comput. 25(2), 237\u2013274 (2017)","journal-title":"Evol. Comput."},{"issue":"4","key":"893_CR28","doi-asserted-by":"publisher","first-page":"1138","DOI":"10.1007\/s00453-021-00809-8","volume":"83","author":"AM Sutton","year":"2021","unstructured":"Sutton, A.M.: Fixed-parameter tractability of crossover: steady-state GAs on the closest string problem. Algorithmica 83(4), 1138\u20131163 (2021)","journal-title":"Algorithmica"},{"key":"893_CR29","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."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00893-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00893-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00893-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,28]],"date-time":"2022-05-28T08:34:32Z","timestamp":1653726872000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00893-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,23]]},"references-count":29,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["893"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00893-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,23]]},"assertion":[{"value":"16 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 December 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}