{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T21:29:45Z","timestamp":1770067785160,"version":"3.49.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2022,3,25]],"date-time":"2022-03-25T00:00:00Z","timestamp":1648166400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,3,25]],"date-time":"2022-03-25T00:00:00Z","timestamp":1648166400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-11-LABX-0056-LMH"],"award-info":[{"award-number":["ANR-11-LABX-0056-LMH"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["LabEx LMH"],"award-info":[{"award-number":["LabEx LMH"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"name":"RFBR and CNRS","award":["20-51-15009"],"award-info":[{"award-number":["20-51-15009"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,6]]},"DOI":"10.1007\/s00453-022-00957-5","type":"journal-article","created":{"date-parts":[[2022,3,25]],"date-time":"2022-03-25T16:30:21Z","timestamp":1648225821000},"page":"1724-1761","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":26,"title":["Fast Mutation in Crossover-Based Algorithms"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7906-096X","authenticated-orcid":false,"given":"Denis","family":"Antipov","sequence":"first","affiliation":[]},{"given":"Maxim","family":"Buzdalov","sequence":"additional","affiliation":[]},{"given":"Benjamin","family":"Doerr","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,3,25]]},"reference":[{"key":"957_CR1","doi-asserted-by":"crossref","unstructured":"Antipov, D., Buzdalov, M., Doerr, B.: Fast mutation in crossover-based algorithms. In Genetic and Evolutionary Computation Conference, GECCO 2020, pp. 1268\u20131276. ACM (2020)","DOI":"10.1145\/3377930.3390172"},{"key":"957_CR2","doi-asserted-by":"crossref","unstructured":"Auger, A., Doerr, B. (eds.): Theory of Randomized Search Heuristics. World Scientific Publishing (2011)","DOI":"10.1142\/7438"},{"key":"957_CR3","doi-asserted-by":"crossref","unstructured":"Antipov, D., Doerr, B.: Runtime analysis of a heavy-tailed $$(1+(\\lambda , \\lambda ))$$ genetic algorithm on jump functions. In: Parallel Problem Solving From Nature, PPSN 2020, Part II, pp. 545\u2013559. Springer (2020)","DOI":"10.1007\/978-3-030-58115-2_38"},{"key":"957_CR4","doi-asserted-by":"crossref","unstructured":"Antipov, D., Doerr, B., Karavaev, V.: A tight runtime analysis for the $${(1 + (\\lambda ,\\lambda ))}$$ GA on LeadingOnes. In: Foundations of Genetic Algorithms, FOGA 2019, pp. 169\u2013182. ACM (2019)","DOI":"10.1145\/3299904.3340317"},{"key":"957_CR5","unstructured":"Antipov, D., Doerr, B., Karavaev, V.: The $$(1 + (\\lambda ,\\lambda ))$$ GA is even faster on multimodal problems. In: Genetic and Evolutionary Computation Conference, GECCO 2020, pp. 1259\u20131267. ACM (2020)"},{"key":"957_CR6","unstructured":"B\u00e4ck, T.: Optimal mutation rates in genetic search. In: International Conference on Genetic Algorithms, ICGA 1993, pp. 2\u20138. Morgan Kaufmann (1993)"},{"key":"957_CR7","doi-asserted-by":"crossref","unstructured":"Buzdalov, M., Doerr, B.: Runtime analysis of the $${(1+(\\lambda ,\\lambda ))}$$ genetic algorithm on random satisfiable 3-CNF formulas. In: Genetic and Evolutionary Computation Conference, GECCO 2017, pp. 1343\u20131350. ACM (2017)","DOI":"10.1145\/3071178.3071297"},{"key":"957_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":"957_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. Theoret. Comput. Sci. 567, 87\u2013104 (2015)","journal-title":"Theoret. Comput. Sci."},{"key":"957_CR10","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. Evol. Comput. 21, 1\u201321 (2013)","journal-title":"Evol. Comput."},{"key":"957_CR11","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+\\lambda )$$ evolutionary algorithm\u2013different asymptotic runtimes for different instances. Theoret. Comput. Sci. 561, 3\u201323 (2015)","journal-title":"Theoret. Comput. Sci."},{"key":"957_CR12","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, pp. 777\u2013784. ACM (2017)","DOI":"10.1145\/3071178.3071301"},{"key":"957_CR13","doi-asserted-by":"crossref","unstructured":"Doerr, B., Neumann, F. (eds.): Theory of Evolutionary Computation\u2014Recent Developments in Discrete Optimization. Springer. https:\/\/cs.adelaide.edu.au\/~frank\/papers\/TheoryBook2019-selfarchived.pdf (2020)","DOI":"10.1007\/978-3-030-29414-4"},{"key":"957_CR14","doi-asserted-by":"crossref","unstructured":"Doerr, B.: Does comma selection help to cope with local optima? In: Genetic and Evolutionary Computation Conference, GECCO 2020, pp. 1304\u20131313. ACM (2020)","DOI":"10.1145\/3377930.3389823"},{"key":"957_CR15","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: Recent Developments in Discrete Optimization, pp. 1\u201387. Springer, https:\/\/arxiv.org\/abs\/1801.06733 (2020)","DOI":"10.1007\/978-3-030-29414-4_1"},{"key":"957_CR16","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1162\/evco.1999.7.2.173","volume":"7","author":"J Garnier","year":"1999","unstructured":"Garnier, J., Kallel, L., Schoenauer, M.: Rigorous hitting times for binary mutations. Evol. Comput. 7, 173\u2013203 (1999)","journal-title":"Evol. Comput."},{"key":"957_CR17","doi-asserted-by":"crossref","unstructured":"Goldman, B.W., Punch, W.F.: Parameter-less population pyramid. In: Genetic and Evolutionary Computation Conference, GECCO 2014, pp. 785\u2013792. ACM (2014)","DOI":"10.1145\/2576768.2598350"},{"key":"957_CR18","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":"957_CR19","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":"957_CR20","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)"},{"key":"957_CR21","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. Evol. Comput. 13, 413\u2013440 (2005)","journal-title":"Evol. Comput."},{"key":"957_CR22","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":"957_CR23","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. ACM (2011)","DOI":"10.1145\/2001576.2001855"},{"key":"957_CR24","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":"957_CR25","unstructured":"M\u00fchlenbein, H.: How genetic algorithms really work: mutation and hillclimbing. In: Parallel Problem Solving from Nature, PPSN 1992, pp. 15\u201326. Elsevier (1992)"},{"key":"957_CR26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16544-3","volume-title":"Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity","author":"F Neumann","year":"2010","unstructured":"Neumann, F., Witt, C.: Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity. Springer, Berlin (2010)"},{"key":"957_CR27","unstructured":"Pinto, E.C., Doerr, C.: Towards a more practice-aware runtime analysis of evolutionary algorithms. CoRR, arXiv:1812.00493 [abs] (2018)"},{"key":"957_CR28","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.tcs.2004.03.038","volume":"320","author":"A Pr\u00fcgel-Bennett","year":"2004","unstructured":"Pr\u00fcgel-Bennett, A.: When a genetic algorithm outperforms hill-climbing. Theoret. Comput. Sci. 320, 135\u2013153 (2004)","journal-title":"Theoret. Comput. Sci."},{"key":"957_CR29","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":"957_CR30","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0375-9601(87)90796-1","volume":"122","author":"HH Szu","year":"1987","unstructured":"Szu, H.H., Hartley, R.L.: Fast simulated annealing. Phys. Lett. A 122, 157\u2013162 (1987)","journal-title":"Phys. Lett. A"},{"key":"957_CR31","doi-asserted-by":"crossref","unstructured":"Teytaud, O., Gelly, S.: General lower bounds for evolutionary algorithms. In: Parallel Problem Solving from Nature, PPSN 2006, pp. 21\u201331. Springer (2006)","DOI":"10.1007\/11844297_3"},{"key":"957_CR32","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1214\/aoms\/1177731092","volume":"16","author":"A Wald","year":"1945","unstructured":"Wald, A.: Some generalizations of the theory of cumulative sums of random variables. Ann. Math. Stat. 16, 287\u2013293 (1945)","journal-title":"Ann. Math. Stat."},{"key":"957_CR33","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. Evol. Comput. 14, 65\u201386 (2006)","journal-title":"Evol. Comput."},{"key":"957_CR34","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":"957_CR35","doi-asserted-by":"crossref","unstructured":"Yao, X., Liu, Y.: Fast evolution strategies. In: Evolutionary Programming, volume 1213 of Lecture Notes in Computer Science, pp. 151\u2013162. Springer (1997)","DOI":"10.1007\/BFb0014808"},{"key":"957_CR36","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1109\/4235.771163","volume":"3","author":"X Yao","year":"1999","unstructured":"Yao, X., Liu, Y., Lin, G.: Evolutionary programming made faster. IEEE Trans. Evol. Comput. 3, 82\u2013102 (1999)","journal-title":"IEEE Trans. Evol. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00957-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00957-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00957-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,28]],"date-time":"2022-05-28T08:34:45Z","timestamp":1653726885000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00957-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,25]]},"references-count":36,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["957"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00957-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,25]]},"assertion":[{"value":"18 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 March 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 March 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}