{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T00:27:40Z","timestamp":1772497660299,"version":"3.50.1"},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2022,1,15]],"date-time":"2022-01-15T00:00:00Z","timestamp":1642204800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,15]],"date-time":"2022-01-15T00:00:00Z","timestamp":1642204800000},"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":"crossref","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":"crossref"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"crossref","award":["LabEx LMH"],"award-info":[{"award-number":["LabEx LMH"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"crossref"}]},{"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-021-00907-7","type":"journal-article","created":{"date-parts":[[2022,1,15]],"date-time":"2022-01-15T00:05:35Z","timestamp":1642205135000},"page":"1573-1602","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["A Rigorous Runtime Analysis of the $$(1 + (\\lambda , \\lambda ))$$ GA on Jump Functions"],"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":"Benjamin","family":"Doerr","sequence":"additional","affiliation":[]},{"given":"Vitalii","family":"Karavaev","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,15]]},"reference":[{"key":"907_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":"907_CR2","doi-asserted-by":"crossref","unstructured":"Antipov, D., Buzdalov, M., Doerr, B.: Lazy parameter tuning and control: choosing all parameters randomly from a power-law distribution. In: Genetic and Evolutionary Computation Conference, GECCO 2021, pp. 1115\u20131123. ACM (2021)","DOI":"10.1145\/3449639.3459377"},{"key":"907_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\u00a0II, pp. 545\u2013559. Springer (2020)","DOI":"10.1007\/978-3-030-58115-2_38"},{"key":"907_CR4","doi-asserted-by":"publisher","first-page":"1054","DOI":"10.1007\/s00453-020-00731-5","volume":"83","author":"D Antipov","year":"2021","unstructured":"Antipov, D., Doerr, B.: A tight runtime analysis for the $$(\\mu +\\lambda )$$ EA. Algorithmica 83, 1054\u20131095 (2021)","journal-title":"Algorithmica"},{"key":"907_CR5","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":"907_CR6","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":"907_CR7","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":"907_CR8","doi-asserted-by":"crossref","unstructured":"Bambury, H., Bultel, A., Doerr, B.: Generalized jump functions. In: Genetic and Evolutionary Computation Conference, GECCO 2021, pp. 1124\u20131132. ACM (2021)","DOI":"10.1145\/3449639.3459367"},{"key":"907_CR9","doi-asserted-by":"crossref","unstructured":"Benbaki, R., Benomar, Z., Doerr, B.: A rigorous runtime analysis of the 2-MMAS$$_{\\rm ib}$$ on jump functions: ant colony optimizers can cope well with local optima. In: Genetic and Evolutionary Computation Conference, GECCO 2021, pp. 4\u201313. ACM (2021)","DOI":"10.1145\/3449639.3459350"},{"key":"907_CR10","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":"907_CR11","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1162\/EVCO_a_00185","volume":"24","author":"M Buzdalov","year":"2016","unstructured":"Buzdalov, M., Doerr, B., Kever, M.: The unrestricted black-box complexity of jump functions. Evol. Comput. 24, 719\u2013744 (2016)","journal-title":"Evol. Comput."},{"key":"907_CR12","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"},{"key":"907_CR13","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":"907_CR14","doi-asserted-by":"crossref","unstructured":"Doerr, B., Doerr, C.: Theory of parameter control for discrete black-box optimization: provable performance gains through dynamic parameter choices. In: Benjamin, D., Frank, N. (eds.) Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pp. 271\u2013321. Springer (2020). arXiv:1804.05650","DOI":"10.1007\/978-3-030-29414-4_6"},{"key":"907_CR15","doi-asserted-by":"crossref","unstructured":"Doerr, B., Doerr, C., Ebel, F.: Lessons from the black-box: fast crossover-based genetic algorithms. In: Genetic and Evolutionary Computation Conference, GECCO 2013, pp. 781\u2013788. ACM (2013)","DOI":"10.1145\/2463372.2463480"},{"key":"907_CR16","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":"907_CR17","doi-asserted-by":"crossref","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 with diversity mechanisms and crossover. In: Genetic and Evolutionary Computation Conference, GECCO 2016, pp. 645\u2013652. ACM (2016)","DOI":"10.1145\/2908812.2908956"},{"key":"907_CR18","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, 484\u2013497 (2018)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"907_CR19","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":"907_CR20","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+1) evolutionary algorithm. Theor. Comput. Sci. 276, 51\u201381 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"907_CR21","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/s00224-004-1177-z","volume":"39","author":"S Droste","year":"2006","unstructured":"Droste, S., Jansen, T., Wegener, I.: Upper and lower bounds for randomized search heuristics in black-box optimization. Theory Comput. Syst. 39, 525\u2013544 (2006)","journal-title":"Theory Comput. Syst."},{"key":"907_CR22","doi-asserted-by":"crossref","unstructured":"Doerr, B., Krejca, M.S.: The univariate marginal distribution algorithm copes well with deception and epistasis. In: Evolutionary Computation in Combinatorial Optimization, EvoCOP 2020, pp. 51\u201366. Springer (2020)","DOI":"10.1007\/978-3-030-43680-3_4"},{"key":"907_CR23","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":"907_CR24","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/s00453-016-0190-3","volume":"78","author":"B Doerr","year":"2017","unstructured":"Doerr, B., Neumann, F., Sutton, A.M.: Time complexity analysis of evolutionary algorithms on random satisfiable $$k$$-CNF formulas. Algorithmica 78, 561\u2013586 (2017)","journal-title":"Algorithmica"},{"key":"907_CR25","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":"907_CR26","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":"907_CR27","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 (2020). arXiv:1801.06733","DOI":"10.1007\/978-3-030-29414-4_1"},{"key":"907_CR28","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"},{"key":"907_CR29","doi-asserted-by":"crossref","unstructured":"Droste, S.: Analysis of the (1+1) EA for a dynamically changing OneMax-variant. In: Congress on Evolutionary Computation, CEC 2002, pp. 55\u201360. IEEE (2002)","DOI":"10.1007\/3-540-45105-6_103"},{"key":"907_CR30","doi-asserted-by":"crossref","unstructured":"Droste, S.: Analysis of the (1+1) EA for a noisy OneMax. In: Genetic and Evolutionary Computation Conference, GECCO 2004, pp. 1088\u20131099. Springer (2004)","DOI":"10.1007\/978-3-540-24854-5_107"},{"key":"907_CR31","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":"907_CR32","unstructured":"Erd\u0151s, P., R\u00e9nyi, A.: On two problems of information theory. Magyar Tudom\u00e1nyos Akad\u00e9mia Matematikai Kutat\u00f3 Int\u00e9zet K\u00f6zlem\u00e9nyei 8, 229\u2013243 (1963)"},{"key":"907_CR33","doi-asserted-by":"crossref","unstructured":"Friedrich, T., K\u00f6tzing, T., Krejca, M.S., Nallaperuma, S., Neumann, F., Schirneck, M.: Fast building block assembly by majority vote crossover. In: Genetic and Evolutionary Computation Conference, GECCO 2016, pp. 661\u2013668. ACM (2016)","DOI":"10.1145\/2908812.2908884"},{"key":"907_CR34","doi-asserted-by":"crossref","unstructured":"Fajardo, M.A.H., Sudholt, D.: On the choice of the parameter control mechanism in the $$(1+(\\lambda ,\\lambda ))$$ genetic algorithm. In: Genetic and Evolutionary Computation Conference, GECCO 2020, pp. 832\u2013840. ACM (2020)","DOI":"10.1145\/3377930.3390200"},{"key":"907_CR35","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":"907_CR36","doi-asserted-by":"crossref","unstructured":"Hasen\u00f6hrl, V., Sutton, A.M.: On the runtime dynamics of the compact genetic algorithm on jump functions. In: Genetic and Evolutionary Computation Conference, GECCO 2018, pp. 967\u2013974. ACM (2018)","DOI":"10.1145\/3205455.3205608"},{"key":"907_CR37","doi-asserted-by":"crossref","unstructured":"Jansen, T.: On the black-box complexity of example functions: the real jump function. In: Foundations of Genetic Algorithms, FOGA 2015, pp. 16\u201324. ACM (2015)","DOI":"10.1145\/2725494.2725507"},{"key":"907_CR38","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":"907_CR39","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\u2014a proof that crossover really can help. Algorithmica 34, 47\u201366 (2002)","journal-title":"Algorithmica"},{"key":"907_CR40","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":"907_CR41","doi-asserted-by":"crossref","unstructured":"Mironovich, V., Buzdalov, M.: Evaluation of heavy-tailed mutation operator on maximum flow test generation problem. In: Genetic and Evolutionary Computation Conference, GECCO 2017, Companion Material, pp. 1423\u20131426. ACM (2017)","DOI":"10.1145\/3067695.3082507"},{"key":"907_CR42","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":"907_CR43","doi-asserted-by":"crossref","unstructured":"Rowe, J.E.: The benefits and limitations of voting mechanisms in evolutionary optimisation. In: Foundations of Genetic Algorithms, FOGA 2019, pp. 34\u201342. ACM (2019)","DOI":"10.1145\/3299904.3340305"},{"key":"907_CR44","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":"907_CR45","doi-asserted-by":"crossref","unstructured":"Rajabi, A., Witt, C.: Self-adjusting evolutionary algorithms for multimodal optimization. In: Genetic and Evolutionary Computation Conference, GECCO 2020, pp. 1314\u20131322. ACM (2020)","DOI":"10.1145\/3377930.3389833"},{"key":"907_CR46","doi-asserted-by":"crossref","unstructured":"Rajabi, A., Witt, C.: Stagnation detection in highly multimodal fitness landscapes. In: Genetic and Evolutionary Computation Conference, GECCO 2021, pp. 1178\u20131186. ACM (2021)","DOI":"10.1145\/3449639.3459336"},{"key":"907_CR47","doi-asserted-by":"crossref","unstructured":"Rajabi, A., Witt, C.: Stagnation detection with randomized local search. In: Evolutionary Computation in Combinatorial Optimization, EvoCOP 2021, pp. 152\u2013168. Springer (2021)","DOI":"10.1007\/978-3-030-72904-2_10"},{"key":"907_CR48","doi-asserted-by":"crossref","unstructured":"Sutton, A.M., Neumann, F.: Runtime analysis of evolutionary algorithms on randomly constructed high-density satisfiable 3-CNF formulas. In: Parallel Problem Solving from Nature, PPSN 2014, pp. 942\u2013951. Springer (2014)","DOI":"10.1007\/978-3-319-10762-2_93"},{"key":"907_CR49","doi-asserted-by":"crossref","unstructured":"Sudholt, D.: Crossover is provably essential for the Ising model on trees. In: Genetic and Evolutionary Computation Conference, GECCO 2005, pp. 1161\u20131167. ACM (2005)","DOI":"10.1145\/1068009.1068202"},{"key":"907_CR50","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/j.tcs.2004.03.047","volume":"320","author":"T Storch","year":"2004","unstructured":"Storch, T., Wegener, I.: Real royal road functions for constant population size. Theor. Comput. Sci. 320, 123\u2013134 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"907_CR51","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":"907_CR52","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, 294\u2013318 (2013)","journal-title":"Combin. Probab. Comput."},{"key":"907_CR53","doi-asserted-by":"crossref","unstructured":"Witt, C.: On crossing fitness valleys with majority-vote crossover and estimation-of-distribution algorithms. In: Foundations of Genetic Algorithms, FOGA 2021, pp. 2:1\u20132:15. ACM (2021)","DOI":"10.1145\/3450218.3477303"},{"key":"907_CR54","doi-asserted-by":"crossref","unstructured":"Whitley, D., Varadarajan, S., Hirsch, R., Mukhopadhyay, A.: Exploration and exploitation without mutation: solving the jump function in $${\\Theta (n)}$$ time. In: Parallel Problem Solving from Nature, PPSN 2018, Part II, pp. 55\u201366. Springer (2018)","DOI":"10.1007\/978-3-319-99259-4_5"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00907-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00907-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00907-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,16]],"date-time":"2024-09-16T09:59:09Z","timestamp":1726480749000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00907-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,15]]},"references-count":54,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["907"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00907-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,15]]},"assertion":[{"value":"19 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}