{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,3]],"date-time":"2025-06-03T04:03:45Z","timestamp":1748923425804,"version":"3.41.0"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T00:00:00Z","timestamp":1748822400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T00:00:00Z","timestamp":1748822400000},"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":["SN COMPUT. SCI."],"abstract":"Abstract<\/jats:title>\n In this paper we revisit the question how hard it can be for the \n \n $$(1+1)$$<\/jats:tex-math>\n \n \n (<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> Evolutionary Algorithm to optimize monotone pseudo-Boolean functions. By introducing a more pessimistic stochastic process, the partially-ordered evolutionary algorithm (PO-EA) model, Jansen first proved a runtime bound of \n \n $$O(n^{3\/2})$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 3<\/mml:mn>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. More recently, Lengler, Martinsson and Steger improved this upper bound to \n \n $$O(n \\log ^2 n)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n \n log<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:msup>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> by an entropy compression argument. In this work, we analyze monotone functions that may adversarially vary at each step of the optimization, so-called dynamic monotone functions. We introduce the function Switching Dynamic BinVal (SDBV) and prove, using a combinatorial argument, that for the \n \n $$(1 + 1)$$<\/jats:tex-math>\n \n \n (<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-EA with any mutation rate \n \n $$p \\in [0,1]$$<\/jats:tex-math>\n \n \n p<\/mml:mi>\n \u2208<\/mml:mo>\n [<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, SDBV is drift minimizing within the class of dynamic monotone functions. We further show that the \n \n $$(1 + 1)$$<\/jats:tex-math>\n \n \n (<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-EA optimizes SDBV in \n \n $$\\Theta (n^{3\/2})$$<\/jats:tex-math>\n \n \n \u0398<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 3<\/mml:mn>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> generations. Therefore, our construction provides the first explicit example which realizes the pessimism of the PO-EA model. Our simulations demonstrate matching runtimes for both the static and the self-adjusting \n \n $$(1, \\lambda )$$<\/jats:tex-math>\n \n \n (<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n \u03bb<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-EA and \n \n $$(1 + \\lambda )$$<\/jats:tex-math>\n \n \n (<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n \u03bb<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-EA. Moreover, devising an example for fixed dimension, we illustrate that drift minimization does not equal maximal runtime beyond asymptotic analysis.<\/jats:p>","DOI":"10.1007\/s42979-025-03999-y","type":"journal-article","created":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T12:08:14Z","timestamp":1748866094000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Hardest Monotone Functions for Evolutionary Algorithms"],"prefix":"10.1007","volume":"6","author":[{"given":"Marc","family":"Kaufmann","sequence":"first","affiliation":[]},{"given":"Maxime","family":"Larcher","sequence":"additional","affiliation":[]},{"given":"Johannes","family":"Lengler","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0008-4682-903X","authenticated-orcid":false,"given":"Oliver","family":"Sieberling","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,6,2]]},"reference":[{"key":"3999_CR1","doi-asserted-by":"crossref","unstructured":"Doerr B, Jansen T, Sudholt D, Winzen C, Zarges C. Optimizing monotone functions can be difficult. PPSNature (PPSN). 2010; 42\u201351.","DOI":"10.1007\/978-3-642-15844-5_5"},{"issue":"4","key":"3999_CR2","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. 2018;27(4):643\u201366.","journal-title":"Comb. Probab. Comput."},{"issue":"6","key":"3999_CR3","doi-asserted-by":"publisher","first-page":"995","DOI":"10.1109\/TEVC.2019.2917014","volume":"24","author":"J Lengler","year":"2019","unstructured":"Lengler J. A general dichotomy of evolutionary algorithms on monotone functions. IEEE Trans Evol Comput. 2019;24(6):995\u20131009.","journal-title":"IEEE Trans. Evol. Comput."},{"key":"3999_CR4","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.tcs.2021.03.025","volume":"875","author":"J Lengler","year":"2021","unstructured":"Lengler J, Zou X. Exponential slowdown for larger populations: The $$(\\mu + 1)$$-EA on monotone functions. Theor Computer Sci. 2021;875:28\u201351.","journal-title":"Theor. Computer Sci."},{"key":"3999_CR5","doi-asserted-by":"crossref","unstructured":"Jansen T. On the brittleness of evolutionary algorithms. In: Foundations of Genetic Algorithms (FOGA), pp. 54\u201369 (2007)","DOI":"10.1007\/978-3-540-73482-6_4"},{"key":"3999_CR6","doi-asserted-by":"crossref","unstructured":"Colin S, Doerr B, F\u00e9rey G. Monotonic functions in EC: anything but monotone! In: Genetic and Evolutionary Computation Conference (GECCO), pp. 753\u2013760 (2014)","DOI":"10.1145\/2576768.2598338"},{"issue":"2","key":"3999_CR7","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. 2013;22(2):294\u2013318.","journal-title":"Comb. Probab. Comput."},{"issue":"1","key":"3999_CR8","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 monotonic functions. Evol Comput. 2013;21(1):1\u201327.","journal-title":"Evol. Comput."},{"key":"3999_CR9","doi-asserted-by":"crossref","unstructured":"Lengler J, Schaller U. The $$(1+1)$$-EA on noisy linear functions with random positive weights. In: Symposium Series on Computational Intelligence (SSCI), pp. 712\u2013719 (2018)","DOI":"10.1109\/SSCI.2018.8628785"},{"key":"3999_CR10","doi-asserted-by":"crossref","unstructured":"Lengler J, Riedi S. Runtime Analysis of the $$(\\mu + 1)$$-EA on the Dynamic BinVal Function. In: Evolutionary Computation in Combinatorial Optimization (EvoCOP), pp. 84\u201399 (2021)","DOI":"10.1007\/978-3-030-72904-2_6"},{"key":"3999_CR11","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.114181","volume":"979","author":"M Kaufmann","year":"2023","unstructured":"Kaufmann M, Larcher M, Lengler J, Zou X. Self-adjusting population sizes for the (1, $$\\lambda$$)-EA on monotone functions. Theor Comput Sci. 2023;979: 114181.","journal-title":"Theor. Comput. Sci."},{"key":"3999_CR12","doi-asserted-by":"crossref","unstructured":"Lengler J, Martinsson A, Steger A. When does hillclimbing fail on monotone functions: An entropy compression argument. In: Analytic Algorithmics and Combinatorics (ANALCO), pp. 94\u2013102 (2019)","DOI":"10.1137\/1.9781611975505.10"},{"key":"3999_CR13","doi-asserted-by":"crossref","unstructured":"Lengler J. Drift analysis. In: Theory of Evolutionary Computation, pp. 89\u2013131. Springer, Cham (2020)","DOI":"10.1007\/978-3-030-29414-4_2"},{"issue":"4","key":"3999_CR14","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1162\/evco_a_00290","volume":"29","author":"N Buskulic","year":"2021","unstructured":"Buskulic N, Doerr C. Maximizing Drift Is Not Optimal for Solving OneMax. Evol Comput. 2021;29(4):521\u201341.","journal-title":"Evol. Comput."},{"key":"3999_CR15","doi-asserted-by":"crossref","unstructured":"Doerr C, Wagner M. Simple on-the-fly parameter selection mechanisms for two classical discrete black-box optimization benchmark problems. In: Genetic and Evolutionary Computation Conference (GECCO), pp. 943\u2013950 (2018)","DOI":"10.1145\/3205455.3205560"},{"key":"3999_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2019.06.014","volume":"801","author":"B Doerr","year":"2020","unstructured":"Doerr B, Doerr C, Yang J. Optimal parameter choices via precise black-box analysis. Theor Comput Sci. 2020;801:1\u201334.","journal-title":"Theor. Comput. Sci."},{"key":"3999_CR17","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1007\/s00453-012-9622-x","volume":"64","author":"B Doerr","year":"2012","unstructured":"Doerr B, Johannsen D, Winzen C. Multiplicative drift analysis. Algorithmica. 2012;64:673\u201397.","journal-title":"Algorithmica."},{"issue":"3","key":"3999_CR18","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1109\/TEVC.2012.2202241","volume":"17","author":"D Sudholt","year":"2012","unstructured":"Sudholt D. A new method for lower bounds on the running time of evolutionary algorithms. IEEE Trans Evol Comput. 2012;17(3):418\u201335.","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"2","key":"3999_CR19","doi-asserted-by":"publisher","first-page":"714","DOI":"10.1007\/s00453-016-0201-4","volume":"78","author":"D Corus","year":"2017","unstructured":"Corus D, He J, Jansen T, Oliveto PS, Sudholt D, Zarges C. On easiest functions for mutation operators in bio-inspired optimisation. Algorithmica. 2017;78(2):714\u201340.","journal-title":"Algorithmica."},{"key":"3999_CR20","doi-asserted-by":"crossref","unstructured":"Jorritsma J, Lengler J, Sudholt D. Comma selection outperforms plus selection on onemax with randomly planted optima. In: Genetic and Evolutionary Computation Conference (GECCO), pp. 1602\u20131610 (2023)","DOI":"10.1145\/3583131.3590488"},{"key":"3999_CR21","doi-asserted-by":"crossref","unstructured":"Kaufmann M, Larcher M, Lengler J, Zou X. OneMax is not the easiest function for fitness improvements. In: Evolutionary Computation in Combinatorial Optimization (EvoCOP), pp. 162\u2013178 (2023)","DOI":"10.1007\/978-3-031-30035-6_11"},{"issue":"2","key":"3999_CR22","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1109\/TEVC.2014.2318025","volume":"19","author":"J He","year":"2014","unstructured":"He J, Chen T, Yao X. On the easiest and hardest fitness functions. IEEE Trans Evol Comput. 2014;19(2):295\u2013305.","journal-title":"IEEE Trans. Evol. Comput."},{"key":"3999_CR23","doi-asserted-by":"crossref","unstructured":"Doerr C, Janett DA, Lengler J. Tight runtime bounds for static unary unbiased evolutionary algorithms on linear functions. In: Genetic and Evolutionary Computation Conference (GECCO), pp. 1565\u20131574 (2023)","DOI":"10.1145\/3583131.3590482"},{"key":"3999_CR24","doi-asserted-by":"crossref","unstructured":"Doerr B, Le HP, Makhmara R, Nguyen TD. Fast genetic algorithms. In: Genetic and Evolutionary Computation Conference (GECCO), pp. 777\u2013784 (2017)","DOI":"10.1145\/3071178.3071301"},{"key":"3999_CR25","doi-asserted-by":"crossref","unstructured":"Lengler J, Meier J. Large population sizes and crossover help in dynamic environments. In: Parallel Problem Solving from Nature (PPSN), pp. 610\u2013622 (2020)","DOI":"10.1007\/978-3-030-58112-1_42"},{"key":"3999_CR26","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.114072","volume":"971","author":"D Janett","year":"2023","unstructured":"Janett D, Lengler J. Two-dimensional drift analysis: Optimizing two functions simultaneously can be hard. Theor Comput Sci. 2023;971: 114072.","journal-title":"Theor. Comput. Sci."},{"key":"3999_CR27","doi-asserted-by":"crossref","unstructured":"Kaufmann M, Larcher M, Lengler J, Sieberling O. Hardest monotone functions for evolutionary algorithms. In: European Conference on Evolutionary Computation in Combinatorial Optimization (EvoCOP), pp. 146\u2013161 (2024). Springer","DOI":"10.1007\/978-3-031-57712-3_10"},{"key":"3999_CR28","doi-asserted-by":"crossref","unstructured":"J\u00e4gersk\u00fcpper J, Storch T. When the plus strategy outperforms the comma strategyand when not. In: Foundations of Computational Intelligence (FOCI), pp. 25\u201332 (2007)","DOI":"10.1109\/FOCI.2007.372143"},{"key":"3999_CR29","doi-asserted-by":"crossref","unstructured":"Neumann F, Oliveto PS, Witt C. Theoretical analysis of fitness-proportional selection: landscapes and efficiency. In: Genetic and Evolutionary Computation (GECCO), pp. 835\u2013842 (2009)","DOI":"10.1145\/1569901.1570016"},{"key":"3999_CR30","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. How the (1+ $$\\lambda$$) evolutionary algorithm optimizes linear functions. Theoretical Computer Science. 2015;561:3\u201323.","journal-title":"Theoretical Computer Science."},{"issue":"4","key":"3999_CR31","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1162\/106365605774666921","volume":"13","author":"T Jansen","year":"2005","unstructured":"Jansen T, De Jong KA, Wegener I. On the choice of the offspring population size in evolutionary algorithms. Evol Comput. 2005;13(4):413\u201340.","journal-title":"Evol. Comput."},{"key":"3999_CR32","doi-asserted-by":"crossref","unstructured":"L\u00e4ssig J, Sudholt D. General scheme for analyzing running times of parallel evolutionary algorithms. In: Parallel Problem Solving from Nature (PPSN), pp. 234\u2013243 (2010)","DOI":"10.1007\/978-3-642-15844-5_24"},{"key":"3999_CR33","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.tcs.2013.09.036","volume":"545","author":"JE Rowe","year":"2014","unstructured":"Rowe JE, Sudholt D. The choice of the offspring population size in the (1, $$\\lambda$$) evolutionary algorithm. Theor Comput Sci. 2014;545:20\u201338.","journal-title":"Theor. Comput. Sci."},{"key":"3999_CR34","doi-asserted-by":"crossref","unstructured":"Doerr B, Lissovoi A, Oliveto PS, Warwicker JA. On the runtime analysis of selection hyper-heuristics with adaptive learning periods. In: Genetic and Evolutionary Computation Conference (GECCO), pp. 1015\u20131022 (2018)","DOI":"10.1145\/3205455.3205611"},{"key":"3999_CR35","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), pp. 569\u2013585 (2022)","DOI":"10.1007\/978-3-031-14721-0_40"},{"key":"3999_CR36","first-page":"1151","volume":"86","author":"MA Hevia Fajardo","year":"2023","unstructured":"Hevia Fajardo MA, Sudholt D. Self-adjusting population sizes for non-elitist evolutionary algorithms: why success rates matter. Algorithmica. 2023;86:1151\u20139.","journal-title":"Algorithmica."},{"key":"3999_CR37","doi-asserted-by":"crossref","unstructured":"L\u00e4ssig J, Sudholt D. Adaptive population models for offspring populations and parallel evolutionary algorithms. In: Foundations of Genetic Algorithms (FOGA), pp. 181\u2013192 (2011)","DOI":"10.1145\/1967654.1967671"},{"key":"3999_CR38","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1007\/s00453-018-0502-x","volume":"81","author":"B Doerr","year":"2019","unstructured":"Doerr B, Gie\u00dfen C, Witt C, Yang J. The (1+ $$\\lambda$$) evolutionary algorithm with self-adjusting mutation rate. Algorithmica. 2019;81:593\u2013631.","journal-title":"Algorithmica."},{"key":"3999_CR39","doi-asserted-by":"crossref","unstructured":"Doerr B. Probabilistic tools for the analysis of randomized optimization heuristics. In: Theory of Evolutionary Computation, pp. 1\u201387. Springer, Cham (2020)","DOI":"10.1007\/978-3-030-29414-4_1"},{"key":"3999_CR40","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511779398","volume-title":"Probability: Theory and Examples","author":"R Durrett","year":"2010","unstructured":"Durrett R. Probability: Theory and Examples. 4th ed. USA: Cambridge University Press; 2010.","edition":"4"}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-025-03999-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-025-03999-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-025-03999-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T12:08:17Z","timestamp":1748866097000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-025-03999-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,2]]},"references-count":40,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2025,6]]}},"alternative-id":["3999"],"URL":"https:\/\/doi.org\/10.1007\/s42979-025-03999-y","relation":{},"ISSN":["2661-8907"],"issn-type":[{"value":"2661-8907","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,2]]},"assertion":[{"value":"24 August 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 June 2025","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 have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"512"}}