{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,25]],"date-time":"2026-08-25T10:08:17Z","timestamp":1787652497198,"version":"build-2736575974"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,8,11]],"date-time":"2022-08-11T00:00:00Z","timestamp":1660176000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,11]],"date-time":"2022-08-11T00:00:00Z","timestamp":1660176000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2024,3]]},"abstract":"Abstract<\/jats:title>Dynamic linear functions on the boolean hypercube are functions which assign to each bit a positive weight, but the weights change over time. Throughout optimization, these functions maintain the same global optimum, and never have defecting local optima. Nevertheless, it was recently shown [Lengler, Schaller, FOCI 2019] that the $$(1+1)$$<\/jats:tex-math>\n \n (<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-Evolutionary Algorithm needs exponential time to find or approximate the optimum for some algorithm configurations. In this experimental paper, we study the effect of larger population sizes for dynamic binval<\/jats:italic>, the extreme form of dynamic linear functions. We find that moderately increased population sizes extend the range of efficient algorithm configurations, and that crossover boosts this positive effect substantially. Remarkably, similar to the static setting of monotone functions in [Lengler, Zou, FOGA 2019], the hardest region of optimization for $$(\\mu +1)$$<\/jats:tex-math>\n \n (<\/mml:mo>\n \u03bc<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-EA is not close the optimum, but far away from it. In contrast, for the $$(\\mu +1)$$<\/jats:tex-math>\n \n (<\/mml:mo>\n \u03bc<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-GA, the region around the optimum is the hardest region in all studied cases.Kindly check and confirm the inserted city name is correctly identified.Correct.<\/jats:p>","DOI":"10.1007\/s11047-022-09915-0","type":"journal-article","created":{"date-parts":[[2022,8,11]],"date-time":"2022-08-11T18:02:33Z","timestamp":1660240953000},"page":"115-129","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Large population sizes and crossover help in dynamic environments"],"prefix":"10.1007","volume":"23","author":[{"given":"Johannes","family":"Lengler","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0004-7629","authenticated-orcid":false,"given":"Jonas","family":"Meier","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,8,11]]},"reference":[{"key":"9915_CR1","doi-asserted-by":"crossref","unstructured":"Antipov D, Doerr B, Fang J, Hetet T (2018) A tight runtime analysis for the ($$\\mu$$+ $$\\lambda$$) EA. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO). pp 1459\u20131466","DOI":"10.1145\/3205455.3205627"},{"issue":"3","key":"9915_CR2","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1109\/TEVC.2017.2724201","volume":"22","author":"DC Dang","year":"2017","unstructured":"Dang DC, Friedrich T, K\u00f6tzing T, Krejca MS, Lehre PK, Oliveto PS, Sudholt D, Sutton AM (2017) Escaping local optima using crossover with emergent diversity. IEEE Trans Evol Comput 22(3):484\u2013497","journal-title":"IEEE Trans Evol Comput"},{"issue":"2","key":"9915_CR3","doi-asserted-by":"publisher","first-page":"660","DOI":"10.1007\/s00453-016-0187-y","volume":"78","author":"DC Dang","year":"2017","unstructured":"Dang DC, Jansen T, Lehre PK (2017) Populations can be essential in tracking dynamic optima. Algorithmica 78(2):660\u2013680","journal-title":"Algorithmica"},{"key":"9915_CR4","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 (2012) Crossover can provably be useful in evolutionary computation. Theo Comput Sci 425:17\u201333","journal-title":"Theo Comput Sci"},{"issue":"1","key":"9915_CR5","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 (2013) Mutation rate matters even when optimizing monotonic functions. Evol Comput 21(1):1\u201327","journal-title":"Evol Comput"},{"key":"9915_CR6","unstructured":"Doerr C, Wang H, Ye F, van Rijn S, B\u00e4ck T (2018) IOHprofiler: A benchmarking and profiling tool for iterative optimization heuristics. arXiv preprint arXiv:1810.05281 , https:\/\/iohprofiler.github.io\/"},{"issue":"2","key":"9915_CR7","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1162\/evco_a_00212","volume":"26","author":"HK Hwang","year":"2018","unstructured":"Hwang HK, Panholzer A, Rolin N, Tsai TH, Chen WM (2018) Probabilistic analysis of the (1+1)-evolutionary algorithm. Evol Comput 26(2):299\u2013345","journal-title":"Evol Comput"},{"issue":"1","key":"9915_CR8","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 (2002) The analysis of evolutionary algorithms-a proof that crossover really can help. Algorithmica 34(1):47\u201366","journal-title":"Algorithmica"},{"key":"9915_CR9","doi-asserted-by":"publisher","first-page":"995","DOI":"10.1109\/TEVC.2019.2917014","volume":"24","author":"J Lengler","year":"2019","unstructured":"Lengler J (2019) A general dichotomy of evolutionary algorithms on monotone functions. IEEE Trans Evol Comput 24:995","journal-title":"IEEE Trans Evol Comput"},{"key":"9915_CR10","doi-asserted-by":"crossref","unstructured":"Lengler J, Martinsson A, Steger A (2019) When does hillclimbing fail on monotone functions: an entropy compression argument. In: Proceedings of the Sixteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). pp 94\u2013102","DOI":"10.1137\/1.9781611975505.10"},{"key":"9915_CR11","unstructured":"Lengler J, Meier J (2020) Evolutionary algorithms in dynamic environments, source code. https:\/\/github.com\/JomeierFL\/BachelorThesis"},{"key":"9915_CR12","doi-asserted-by":"crossref","unstructured":"Lengler J, Schaller U (2018) The (1+1)-EA on noisy linear functions with random positive weights. In: Proceedings of the Symposium Series on Computational Intelligence (SSCI). pp 712\u2013719","DOI":"10.1109\/SSCI.2018.8628785"},{"issue":"4","key":"9915_CR13","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1017\/S0963548318000275","volume":"27","author":"J Lengler","year":"2018","unstructured":"Lengler J, Steger A (2018) Drift analysis and evolutionary algorithms revisited. Comb Probab Comput 27(4):643\u2013666","journal-title":"Comb Probab Comput"},{"key":"9915_CR14","doi-asserted-by":"crossref","unstructured":"Lengler J, Zou X (2019) Exponential slowdown for larger populations: the ($$\\mu$$+1)-EA on monotone functions. In: Proceedings of the 15th ACM\/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA). pp 87\u2013101","DOI":"10.1145\/3299904.3340309"},{"issue":"3","key":"9915_CR15","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 (2016) MMAS versus population-based EA on a family of dynamic fitness functions. Algorithmica 75(3):554\u2013576","journal-title":"Algorithmica"},{"key":"9915_CR16","doi-asserted-by":"crossref","unstructured":"Pinto E.C, Doerr C (2018) A simple proof for the usefulness of crossover in black-box optimization. In: Proceedings of the International Conference on Parallel Problem Solving from Nature (PPSN). pp 29\u201341","DOI":"10.1007\/978-3-319-99259-4_3"},{"key":"9915_CR17","unstructured":"R Core Team (2020) R: A language and environment for statistical computing. R Foundation for Statistical Computing, Vienna, Austria, https:\/\/www.R-project.org\/"},{"key":"9915_CR18","doi-asserted-by":"crossref","unstructured":"Rohlfshagen P, Lehre PK, Yao X (2009) Dynamic evolutionary optimisation: an analysis of frequency and magnitude of change. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO). pp 1713\u20131720","DOI":"10.1145\/1569901.1570131"},{"issue":"2","key":"9915_CR19","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1162\/EVCO_a_00171","volume":"25","author":"D Sudholt","year":"2017","unstructured":"Sudholt D (2017) How crossover speeds up building block assembly in genetic algorithms. Evol Comput 25(2):237\u2013274","journal-title":"Evol Comput"},{"key":"9915_CR20","doi-asserted-by":"crossref","unstructured":"Sudholt D (2020) The benefits of population diversity in evolutionary algorithms: a survey of rigorous runtime analyses. In: Theory of Evolutionary Computation, pp 359\u2013404","DOI":"10.1007\/978-3-030-29414-4_8"},{"issue":"1","key":"9915_CR21","first-page":"65","volume":"14","author":"C Witt","year":"2006","unstructured":"Witt C (2006) Runtime analysis of the ($$\\mu$$+1)-EA on simple pseudo-Boolean functions. Evol Comput 14(1):65\u201386","journal-title":"Evol Comput"},{"issue":"2","key":"9915_CR22","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1017\/S0963548312000600","volume":"22","author":"C Witt","year":"2013","unstructured":"Witt C (2013) Tight bounds on the optimization time of a randomized search heuristic on linear functions. Comb Probab Comput 22(2):294\u2013318","journal-title":"Comb Probab Comput"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-022-09915-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11047-022-09915-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-022-09915-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,27]],"date-time":"2024-03-27T07:17:42Z","timestamp":1711523862000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11047-022-09915-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,11]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["9915"],"URL":"https:\/\/doi.org\/10.1007\/s11047-022-09915-0","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"value":"1567-7818","type":"print"},{"value":"1572-9796","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,11]]},"assertion":[{"value":"27 July 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 August 2022","order":2,"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 that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}