{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,25]],"date-time":"2026-08-25T10:08:10Z","timestamp":1787652490990,"version":"build-2736575974"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T00:00:00Z","timestamp":1654819200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T00:00:00Z","timestamp":1654819200000},"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."],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study evolutionary algorithms in a dynamic setting, where for each generation a different fitness function is chosen, and selection is performed with respect to the current fitness function. Specifically, we consider Dynamic BinVal, in which the fitness functions for each generation is given by the linear function BinVal, but in each generation the order of bits is randomly permuted. For the <jats:inline-formula><jats:alternatives><jats:tex-math>$$(1 + 1)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-EA it was known that there is an efficiency threshold <jats:inline-formula><jats:alternatives><jats:tex-math>$$c_0$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>c<\/mml:mi>\n                    <mml:mn>0<\/mml:mn>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for the mutation parameter, at which the runtime switches from quasilinear to exponential. Previous empirical evidence suggested that for larger population size <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mu$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03bc<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the threshold may increase. We prove that this is at least the case in an <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varepsilon$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03b5<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-neighborhood around the optimum: the threshold of the <jats:inline-formula><jats:alternatives><jats:tex-math>$$(\\mu + 1)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>\u03bc<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-EA becomes arbitrarily large if the <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mu$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03bc<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is chosen large enough. However, the most surprising result is obtained by a second-order analysis for <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mu =2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03bc<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>: the threshold <jats:italic>in<\/jats:italic>creases with increasing proximity to the optimum. In particular, the hardest region for optimization is <jats:italic>not<\/jats:italic> around the optimum.<\/jats:p>","DOI":"10.1007\/s42979-022-01203-z","type":"journal-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T06:04:41Z","timestamp":1654841081000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Runtime Analysis of the $$(\\mu + 1)$$-EA on the Dynamic BinVal Function"],"prefix":"10.1007","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0004-7629","authenticated-orcid":false,"given":"Johannes","family":"Lengler","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Simone","family":"Riedi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"1203_CR1","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). ACM; 2014. pp. 753\u2013760.","DOI":"10.1145\/2576768.2598338"},{"key":"1203_CR2","doi-asserted-by":"crossref","unstructured":"Dang-Nhu R, Dardinier T, Doerr B, Izacard G, Nogneng D. A new analysis method for evolutionary optimization of dynamic and noisy objective functions. In: Genetic and Evolutionary Computation Conference (GECCO). ACM; 2018. pp. 1467\u20131474.","DOI":"10.1145\/3205455.3205563"},{"key":"1203_CR3","doi-asserted-by":"crossref","unstructured":"Doerr B. Probabilistic tools for the analysis of randomized optimization heuristics. In: Theory of evolutionary computation. Springer; 2020. pp. 1\u201387.","DOI":"10.1007\/978-3-030-29414-4_1"},{"issue":"1","key":"1203_CR4","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/s00453-011-9585-3","volume":"65","author":"B Doerr","year":"2013","unstructured":"Doerr B, Goldberg LA. Adaptive drift analysis. Algorithmica. 2013;65(1):224\u201350.","journal-title":"Algorithmica"},{"key":"1203_CR5","doi-asserted-by":"crossref","unstructured":"Doerr B, Hota A, K\u00f6tzing T. Ants easily solve stochastic shortest path problems. In: Genetic and Evolutionary Computation Conference (GECCO). ACM; 2012. pp. 17\u201324.","DOI":"10.1145\/2330163.2330167"},{"issue":"1","key":"1203_CR6","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":"1203_CR7","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), vol.\u00a01, IEEE; 2002. pp. 55\u201360.","DOI":"10.1007\/3-540-45105-6_103"},{"key":"1203_CR8","doi-asserted-by":"crossref","unstructured":"Horoba C, Sudholt D. Ant colony optimization for stochastic shortest path problems. In: Genetic and Evolutionary Computation Conference (GECCO). ACM; 2010. pp. 1465\u20131472.","DOI":"10.1145\/1830483.1830750"},{"key":"1203_CR9","doi-asserted-by":"crossref","unstructured":"Jansen T. On the brittleness of evolutionary algorithms. In: Foundations of genetic algorithms (FOGA). Springer; 2007. pp. 54\u201369.","DOI":"10.1007\/978-3-540-73482-6_4"},{"issue":"3","key":"1203_CR10","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1007\/s00453-015-0048-0","volume":"75","author":"T K\u00f6tzing","year":"2016","unstructured":"K\u00f6tzing T. Concentration of first hitting times under additive drift. Algorithmica. 2016;75(3):490\u2013506.","journal-title":"Algorithmica"},{"key":"1203_CR11","doi-asserted-by":"crossref","unstructured":"K\u00f6tzing T, Lissovoi A, Witt C. (1+1) EA on generalized dynamic OneMax. In: Foundations of genetic algorithms (FOGA). Springer; 2015. pp. 40\u201351.","DOI":"10.1145\/2725494.2725502"},{"key":"1203_CR12","doi-asserted-by":"crossref","unstructured":"K\u00f6tzing T, Molter H. ACO beats EA on a dynamic pseudo-boolean function. In: Parallel problem solving from nature (PPSN). Springer; 2012. pp. 113\u2013122.","DOI":"10.1007\/978-3-642-32937-1_12"},{"issue":"6","key":"1203_CR13","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":"1203_CR14","doi-asserted-by":"crossref","unstructured":"Lengler J. Drift analysis. In: Theory of evolutionary computation. Springer; 2020. pp. 89\u2013131.","DOI":"10.1007\/978-3-030-29414-4_2"},{"key":"1203_CR15","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). SIAM; 2019. pp. 94\u2013102.","DOI":"10.1137\/1.9781611975505.10"},{"key":"1203_CR16","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). Springer; 2020. pp. 610\u2013622.","DOI":"10.1007\/978-3-030-58112-1_42"},{"key":"1203_CR17","doi-asserted-by":"crossref","unstructured":"Lengler J, Meier J. Large population sizes and crossover help in dynamic environments, full version. arXiv preprint; 2020. http:\/\/arxiv.org\/abs\/2004.09949","DOI":"10.1007\/978-3-030-58112-1_42"},{"key":"1203_CR18","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). Springer; 2021 pp. 84\u201399.","DOI":"10.1007\/978-3-030-72904-2_6"},{"key":"1203_CR19","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). IEEE; 2018. pp. 712\u2013719.","DOI":"10.1109\/SSCI.2018.8628785"},{"issue":"4","key":"1203_CR20","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. Combinatorics Probab Comput. 2018;27(4):643\u201366.","journal-title":"Combinatorics Probab Comput"},{"key":"1203_CR21","doi-asserted-by":"crossref","unstructured":"Lengler J, Zou X. Exponential slowdown for larger populations: the ($$\\mu$$+1)-EA on monotone functions. In: Foundations of genetic algorithms (FOGA). ACM; 2019. pp. 87\u2013101.","DOI":"10.1145\/3299904.3340309"},{"issue":"3","key":"1203_CR22","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1007\/s00453-015-9975-z","volume":"75","author":"A Lissovoi","year":"2016","unstructured":"Lissovoi A, Witt C. MMAS versus population-based EA on a family of dynamic fitness functions. Algorithmica. 2016;75(3):554\u201376.","journal-title":"Algorithmica"},{"issue":"2","key":"1203_CR23","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1007\/s00453-016-0262-4","volume":"78","author":"A Lissovoi","year":"2017","unstructured":"Lissovoi A, Witt C. A runtime analysis of parallel evolutionary algorithms in dynamic optimization. Algorithmica. 2017;78(2):641\u201359.","journal-title":"Algorithmica"},{"issue":"5","key":"1203_CR24","doi-asserted-by":"publisher","first-page":"1634","DOI":"10.1007\/s00453-017-0377-2","volume":"80","author":"A Lissovoi","year":"2018","unstructured":"Lissovoi A, Witt C. The impact of a sparse migration topology on the runtime of island models in dynamic optimization. Algorithmica. 2018;80(5):1634\u201357.","journal-title":"Algorithmica"},{"key":"1203_CR25","doi-asserted-by":"crossref","unstructured":"Neumann F, Pourhassan M, Roostapour V. Analysis of evolutionary algorithms in dynamic and stochastic environments. In: Theory of evolutionary computation.  Springer; 2020. pp. 323\u2013357.","DOI":"10.1007\/978-3-030-29414-4_7"},{"key":"1203_CR26","unstructured":"Neumann F, Witt C. On the runtime of randomized local search and simple evolutionary algorithms for dynamic makespan scheduling. In: International Joint Conference on Artificial Intelligence (IJCAI). AAAI Press; 2015 pp. 3742\u20133748."},{"key":"1203_CR27","doi-asserted-by":"crossref","unstructured":"Pourhassan M, Gao W, Neumann F. Maintaining 2-approximations for the dynamic vertex cover problem using evolutionary algorithms. In: Genetic and Evolutionary Computation Conference (GECCO). ACM; 2015. pp. 903\u2013910.","DOI":"10.1145\/2739480.2754700"},{"issue":"2","key":"1203_CR28","doi-asserted-by":"publisher","first-page":"828","DOI":"10.1007\/s00453-018-0451-4","volume":"81","author":"F Shi","year":"2019","unstructured":"Shi F, Schirneck M, Friedrich T, K\u00f6tzing T, Neumann F. Reoptimization time analysis of evolutionary algorithms on linear functions under dynamic uniform constraints. Algorithmica. 2019;81(2):828\u201357.","journal-title":"Algorithmica"}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-022-01203-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-022-01203-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-022-01203-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,23]],"date-time":"2022-06-23T17:05:39Z","timestamp":1656003939000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-022-01203-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,10]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["1203"],"URL":"https:\/\/doi.org\/10.1007\/s42979-022-01203-z","relation":{},"ISSN":["2661-8907"],"issn-type":[{"value":"2661-8907","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,10]]},"assertion":[{"value":"14 July 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 May 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 June 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"On behalf of all authors, the corresponding author states that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}],"article-number":"324"}}