{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T15:57:44Z","timestamp":1770047864611,"version":"3.49.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T00:00:00Z","timestamp":1767916800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T00:00:00Z","timestamp":1767916800000},"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":[[2026,2]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We compare the\n                    <jats:inline-formula>\n                      <jats:tex-math>$$(1, \\lambda )$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -EA and the\n                    <jats:inline-formula>\n                      <jats:tex-math>$$(1 + \\lambda )$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -EA on the recently introduced benchmark\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\textsc {DisOM}$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    , which is the\n                    <jats:sc>OneMax<\/jats:sc>\n                    function with randomly planted local optima. Previous work showed that if all local optima have the same relative height, then the plus strategy never loses more than a factor\n                    <jats:inline-formula>\n                      <jats:tex-math>$$O(n\\log n)$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    compared to the comma strategy. Here we show that even small random fluctuations in the heights of the local optima have a devastating effect for the plus strategy and lead to superpolynomial time to achieve a prescribed fitness target. On the other hand, due to their ability to escape local optima, comma strategies are unaffected by the height of the local optima and remain efficient. Our results hold for a broad class of possible distortions and show that the plus strategy, but not the comma strategy, is generally deceived by sparse unstructured fluctuations of a smooth landscape.\n                  <\/jats:p>","DOI":"10.1007\/s00453-025-01352-6","type":"journal-article","created":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T04:47:55Z","timestamp":1767934075000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Plus Strategies are Exponentially Slower for Planted Optima of Random Height"],"prefix":"10.1007","volume":"88","author":[{"given":"Johannes","family":"Lengler","sequence":"first","affiliation":[]},{"given":"Leon","family":"Schiller","sequence":"additional","affiliation":[]},{"given":"Oliver","family":"Sieberling","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,1,9]]},"reference":[{"issue":"2","key":"1352_CR1","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":"1352_CR2","first-page":"1133","volume":"2021","author":"D-C Dang","year":"2021","unstructured":"Dang, D.-C., Eremeev, A., Lehre, P.K.: Non-elitist evolutionary algorithms excel in fitness landscapes with sparse deceptive regions and dense valleys. Genetic Evol. Comput. Conf. 2021, 1133\u20131141 (2021)","journal-title":"Genetic Evol. Comput. Conf."},{"key":"1352_CR3","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":"1352_CR4","first-page":"1","volume":"5","author":"MA Hevia Fajardo","year":"2021","unstructured":"Hevia Fajardo, M.A., Sudholt, D.: Self-adjusting offspring population sizes outperform fixed parameters on the cliff function. Proc. Found. Genetic Algor. (FOGA 2021) 5, 1\u20135 (2021)","journal-title":"Proc. Found. Genetic Algor. (FOGA 2021)"},{"key":"1352_CR5","doi-asserted-by":"crossref","unstructured":"Jorritsma, J., Lengler, J., Sudholt, D.: Comma selection outperforms plus selection on onemax with randomly planted optima. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2023), pp. 1602\u20131610. ACM, New York (2023)","DOI":"10.1145\/3583131.3590488"},{"key":"1352_CR6","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"},{"issue":"3","key":"1352_CR7","first-page":"477","volume":"21","author":"T Friedrich","year":"2016","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 (2016)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"1352_CR8","doi-asserted-by":"crossref","unstructured":"Friedrich, T., K\u00f6tzing, T., Krejca, M.S., Sutton, A.M.: Graceful scaling on uniform versus steep-tailed noise. In: Parallel problem solving from nature (PPSN 2016), pp. 761\u2013770. Springer (2016)","DOI":"10.1007\/978-3-319-45823-6_71"},{"key":"1352_CR9","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"},{"issue":"6","key":"1352_CR10","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(6), 1659\u20131693 (2022)","journal-title":"Algorithmica"},{"key":"1352_CR11","doi-asserted-by":"crossref","unstructured":"J\u00e4gerskupper, J., Storch, T.: When the plus strategy outperforms the comma strategyand when not. In: Foundations of Computational Intelligence (FOCI 2007), pp. 25\u201332 (2007)","DOI":"10.1109\/FOCI.2007.372143"},{"key":"1352_CR12","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2023.104061","volume":"328","author":"MAH Fajardo","year":"2024","unstructured":"Fajardo, M.A.H., Sudholt, D.: Self-adjusting offspring population sizes outperform fixed parameters on the cliff function. Artif. Intell. 328, 104061 (2024)","journal-title":"Artif. Intell."},{"issue":"2","key":"1352_CR13","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)","journal-title":"Algorithmica"},{"key":"1352_CR14","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. Springer (2022)","DOI":"10.1007\/978-3-031-14721-0_40"},{"issue":"1","key":"1352_CR15","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1162\/evco_a_00348","volume":"33","author":"M Kaufmann","year":"2025","unstructured":"Kaufmann, M., Larcher, M., Lengler, J., Zou, X.: Onemax is not the easiest function for fitness improvements. Evol. Comput. 33(1), 27\u201354 (2025)","journal-title":"Evol. Comput."},{"key":"1352_CR16","doi-asserted-by":"crossref","unstructured":"Kaufmann, M., Larcher, M., Lengler, J., Sieberling, O.: Hardest monotone functions for evolutionary algorithms. In: Evolutionary computation in combinatorial optimization (EvoCOP 2024), pp. 146\u2013161. Springer (2024)","DOI":"10.1007\/978-3-031-57712-3_10"},{"issue":"4","key":"1352_CR17","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":"1352_CR18","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), vol. 35, pp. 12275\u201312283 (2021)","DOI":"10.1609\/aaai.v35i14.17457"},{"key":"1352_CR19","doi-asserted-by":"crossref","unstructured":"Dang, D.-C., Eremeev, A., Lehre, P.K., Qin, X.: Fast non-elitist evolutionary algorithms with power-law ranking selection. In: Genetic and evolutionary computation conference (GECCO 2022), pp. 1372\u20131380 (2022)","DOI":"10.1145\/3512290.3528873"},{"key":"1352_CR20","doi-asserted-by":"crossref","unstructured":"Pr\u00fcgel-Bennett, A., Rowe, J., Shapiro, J.: Run-time analysis of population-based evolutionary algorithm in noisy environments. In: Proceedings of foundations of genetic algorithms (FOGA 2015), pp. 69\u201375 (2015)","DOI":"10.1145\/2725494.2725498"},{"key":"1352_CR21","doi-asserted-by":"crossref","unstructured":"Lehre, P.K.: Fitness-levels for non-elitist populations. In: Proceedings of the genetic and evolutionary computation conference (GECCO 2011), pp. 2075\u20132082. ACM, Dublin Ireland (2011)","DOI":"10.1145\/2001576.2001855"},{"key":"1352_CR22","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":"1352_CR23","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: Proceedings of the genetic and evolutionary computation conference (GECCO 2019), pp. 1461\u20131469. ACM, New York (2019)","DOI":"10.1145\/3321707.3321838"},{"key":"1352_CR24","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"DP Dubhashi","year":"2009","unstructured":"Dubhashi, D.P., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge, UK (2009)"},{"issue":"4","key":"1352_CR25","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1017\/S0963548318000275","volume":"27","author":"J Lengler","year":"2018","unstructured":"Lengler, J., Steger, A.: Drift analysis and evolutionary algorithms revisited. Comb. Probab. Comput. 27(4), 643\u2013666 (2018)","journal-title":"Comb. Probab. Comput."},{"key":"1352_CR26","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 (2017)","DOI":"10.1145\/3071178.3071301"},{"issue":"10","key":"1352_CR27","doi-asserted-by":"publisher","first-page":"3115","DOI":"10.1007\/s00453-024-01258-9","volume":"86","author":"C Doerr","year":"2024","unstructured":"Doerr, C., Janett, D.A., Lengler, J.: Tight runtime bounds for static unary unbiased evolutionary algorithms on linear functions. Algorithmica 86(10), 3115\u20133152 (2024)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01352-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01352-6","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01352-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T05:11:50Z","timestamp":1770009110000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01352-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,9]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,2]]}},"alternative-id":["1352"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01352-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,9]]},"assertion":[{"value":"17 December 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 September 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 January 2026","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 declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Research Involving Human and\/or Animals"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Informed Consent"}}],"article-number":"17"}}