{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T15:41:38Z","timestamp":1767973298081,"version":"3.49.0"},"reference-count":40,"publisher":"MIT Press","issue":"1","content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,3,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We study the (1:s+1) success rule for controlling the population size of the (1,\u03bb)-EA. It was shown by Hevia Fajardo and Sudholt that this parameter control mechanism can run into problems for large s if the fitness landscape is too easy. They conjectured that this problem is worst for the OneMax benchmark, since in some well-established sense OneMax is known to be the easiest fitness landscape. In this paper, we disprove this conjecture. We show that there exist s and \u025b such that the self-adjusting (1,\u03bb)-EA with the (1:s+1)-rule optimizes OneMax efficiently when started with \u025bn zero-bits, but does not find the optimum in polynomial time on Dynamic BinVal. Hence, we show that there are landscapes where the problem of the (1:s+1)-rule for controlling the population size of the (1,\u03bb)-EA is more severe than for OneMax. The key insight is that, while OneMax is the easiest function for decreasing the distance to the optimum, it is not the easiest fitness landscape with respect to finding fitness-improving steps.<\/jats:p>","DOI":"10.1162\/evco_a_00348","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T16:47:59Z","timestamp":1711471679000},"page":"27-54","update-policy":"https:\/\/doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":3,"title":["OneMax Is Not the Easiest Function for Fitness Improvements"],"prefix":"10.1162","volume":"33","author":[{"given":"Marc","family":"Kaufmann","sequence":"first","affiliation":[{"name":"Department of Computer Science, ETH Z\u00fcrich, Z\u00fcrich, Switzerland marc.kaufmann@inf.ethz.ch"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maxime","family":"Larcher","sequence":"additional","affiliation":[{"name":"Department of Computer Science, ETH Z\u00fcrich, Z\u00fcrich, Switzerland maxime.larcher@inf.ethz.ch"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johannes","family":"Lengler","sequence":"additional","affiliation":[{"name":"Department of Computer Science, ETH Z\u00fcrich, Z\u00fcrich, Switzerland johannes.lengler@inf.ethz.ch"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xun","family":"Zou","sequence":"additional","affiliation":[{"name":"Department of Computer Science, ETH Z\u00fcrich, Z\u00fcrich, Switzerland xun.zou@inf.ethz.ch"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","published-online":{"date-parts":[[2025,3,15]]},"reference":[{"key":"2025042916155139800_B1","doi-asserted-by":"crossref","first-page":"1461","DOI":"10.1145\/3321707.3321838","article-title":"The efficiency threshold for the offspring population size of the (\u03bc,\u03bb) EA","author":"Antipov","year":"2019","journal-title":"Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2025042916155139800_B2","doi-asserted-by":"crossref","first-page":"2447","DOI":"10.1145\/1570256.1570342","article-title":"Benchmarking the (1+ 1) evolution strategy with one-fifth success rule on the bbob-2009 function testbed","author":"Auger","year":"2009","journal-title":"Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2025042916155139800_B3","first-page":"892","article-title":"Unbiased black-box complexity of parallel search","author":"Badkobeh","year":"2014","journal-title":"Parallel Problem Solving from Nature"},{"key":"2025042916155139800_B4","first-page":"1","article-title":"Optimal fixed and adaptive mutation rates for the leadingones problem","author":"B\u00f6ttcher","year":"2010","journal-title":"Parallel Problem Solving from Nature"},{"key":"2025042916155139800_B5","first-page":"753","article-title":"Monotonic functions in EC: Anything but monotone!","author":"Colin","year":"2014","journal-title":"Genetic and Evolutionary Computation Conference (GECCO)"},{"issue":"2","key":"2025042916155139800_B6","doi-asserted-by":"publisher","first-page":"714","DOI":"10.1007\/s00453-016-0201-4","article-title":"On easiest functions for mutation operators in bio-inspired optimisation","volume":"78","author":"Corus","year":"2017","journal-title":"Algorithmica"},{"key":"2025042916155139800_B7","article-title":"The compound random search","author":"Devroye","year":"1972"},{"key":"2025042916155139800_B8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-030-29414-4_1","article-title":"Probabilistic tools for the analysis of randomized optimization heuristics","volume-title":"Theory of Evolutionary Computation","author":"Doerr","year":"2020"},{"issue":"5","key":"2025042916155139800_B9","doi-asserted-by":"publisher","first-page":"1658","DOI":"10.1007\/s00453-017-0354-9","article-title":"Optimal static and self-adjusting parameter choices for the (1+(\u03bb,\u03bb)) genetic algorithm","volume":"80","author":"Doerr","year":"2018","journal-title":"Algorithmica"},{"key":"2025042916155139800_B10","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/978-3-030-29414-4_6","article-title":"Theory of parameter control for discrete black-box optimization: Provable performance gains through dynamic parameter choices","volume-title":"Theory of evolutionary computation: Recent developments in discrete Optimization","author":"Doerr","year":"2020"},{"key":"2025042916155139800_B11","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.tcs.2014.11.028","article-title":"From black-box complexity to designing new genetic algorithms","volume":"567","author":"Doerr","year":"2015","journal-title":"Theoretical Computer Science"},{"issue":"10","key":"2025042916155139800_B12","doi-asserted-by":"publisher","first-page":"3108","DOI":"10.1007\/s00453-021-00854-3","article-title":"Self-adjusting mutation rates with provably optimal success rules","volume":"83","author":"Doerr","year":"2021","journal-title":"Algorithmica"},{"key":"2025042916155139800_B13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2019.06.014","article-title":"Optimal parameter choices via precise black-box analysis","volume":"801","author":"Doerr","year":"2020","journal-title":"Theoretical Computer Science"},{"key":"2025042916155139800_B14","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1007\/s00453-012-9622-x","article-title":"Multiplicative drift analysis","volume":"64","author":"Doerr","year":"2012","journal-title":"Algorithmica"},{"issue":"4","key":"2025042916155139800_B15","doi-asserted-by":"publisher","first-page":"1012","DOI":"10.1007\/s00453-020-00726-2","article-title":"Runtime analysis for self-adaptive mutation rates","volume":"83","author":"Doerr","year":"2021","journal-title":"Algorithmica"},{"key":"2025042916155139800_B16","doi-asserted-by":"crossref","first-page":"943","DOI":"10.1145\/3205455.3205560","article-title":"Simple on-the-fly parameter selection mechanisms for two classical discrete black-box optimization benchmark problems","author":"Doerr","year":"2018","journal-title":"Genetic and Evolutionary Computation Conference (GECCO)"},{"issue":"3","key":"2025042916155139800_B17","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/s11047-006-9001-0","article-title":"A rigorous analysis of the compact genetic algorithm for linear functions","volume":"5","author":"Droste","year":"2006","journal-title":"Natural Computing"},{"key":"2025042916155139800_B18","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1109\/4235.771166","article-title":"Parameter control in evolutionary algorithms","volume":"3","author":"Eiben","year":"1999","journal-title":"IEEE Transactions on Evolutionary Computation"},{"issue":"2","key":"2025042916155139800_B19","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1109\/TEVC.2014.2318025","article-title":"On the easiest and hardest fitness functions","volume":"19","author":"He","year":"2014","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2025042916155139800_B20","first-page":"1","article-title":"Self-adjusting offspring population sizes outperform fixed parameters on the cliff function","author":"Hevia Fajardo","year":"2021","journal-title":"Foundations of Genetic Algorithms"},{"key":"2025042916155139800_B21","article-title":"Self-adjusting population sizes for non-elitist evolutionary algorithms: Why success rates matter","author":"Hevia Fajardo","year":"2021","journal-title":"arXiv preprint arXiv:2104.05624"},{"key":"2025042916155139800_B22","doi-asserted-by":"crossref","first-page":"1151","DOI":"10.1145\/3449639.3459338","article-title":"Self-adjusting population sizes for non-elitist evolutionary algorithms: Why success rates matter","author":"Hevia Fajardo","year":"2021","journal-title":"Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2025042916155139800_B23","doi-asserted-by":"crossref","first-page":"796","DOI":"10.1145\/3512290.3528781","article-title":"Hard problems are easier for success-based parameter control","author":"Hevia Fajardo","year":"2022","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2025042916155139800_B24","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1007\/978-3-540-73482-6_4","article-title":"On the brittleness of evolutionary algorithms","author":"Jansen","year":"2007","journal-title":"Foundations of Genetic Algorithms"},{"key":"2025042916155139800_B25","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1007\/978-3-031-14721-0_40","article-title":"Self-adjusting population sizes for the (1,\u03bb)-EA on monotone functions","author":"Kaufmann","year":"2022","journal-title":"Parallel Problem Solving in Nature"},{"issue":"1","key":"2025042916155139800_B26","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1023\/B:NACO.0000023416.59689.4e","article-title":"Learning probability distributions in continuous evolutionary algorithms\u2014A comparative review","volume":"3","author":"Kern","year":"2004","journal-title":"Natural Computing"},{"issue":"3","key":"2025042916155139800_B27","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1007\/s00453-015-0048-0","article-title":"Concentration of first hitting times under additive drift","volume":"75","author":"K\u00f6tzing","year":"2016","journal-title":"Algorithmica"},{"key":"2025042916155139800_B28","first-page":"1","article-title":"More precise runtime analyses of non-elitist evolutionary algorithms in uncertain environments","author":"Lehre","year":"2022","journal-title":"Algorithmica"},{"issue":"6","key":"2025042916155139800_B29","doi-asserted-by":"publisher","first-page":"995","DOI":"10.1109\/TEVC.2019.2917014","article-title":"A general dichotomy of evolutionary algorithms on monotone functions","volume":"24","author":"Lengler","year":"2019","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2025042916155139800_B30","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/978-3-030-29414-4_2","article-title":"Drift analysis","author":"Lengler","year":"2020","journal-title":"Theory of Evolutionary Computation"},{"key":"2025042916155139800_B31","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1007\/978-3-030-58112-1_42","article-title":"Large population sizes and crossover help in dynamic environments","author":"Lengler","year":"2020","journal-title":"Parallel Problem Solving from Nature"},{"key":"2025042916155139800_B32","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1007\/978-3-030-72904-2_6","article-title":"Runtime analysis of the (\u03bc+1)-EA on the dynamic BinVal function","author":"Lengler","year":"2021","journal-title":"Evolutionary Computation in Combinatorial Optimization"},{"key":"2025042916155139800_B33","first-page":"712","article-title":"The (1+1)-EA on noisy linear functions with random positive weights","author":"Lengler","year":"2018","journal-title":"Symposium Series on Computational Intelligence"},{"issue":"4","key":"2025042916155139800_B34","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1017\/S0963548318000275","article-title":"Drift analysis and evolutionary algorithms revisited","volume":"27","author":"Lengler","year":"2018","journal-title":"Combinatorics, Probability and Computing"},{"key":"2025042916155139800_B35","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.tcs.2015.01.002","article-title":"Improved time complexity analysis of the simple genetic algorithm","volume":"605","author":"Oliveto","year":"2015","journal-title":"Theoretical Computer Science"},{"key":"2025042916155139800_B36","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/978-3-642-81283-5_8","article-title":"Evolutionsstrategien","author":"Rechenberg","year":"1978","journal-title":"Simulationsmethoden in der Medizin und Biologie"},{"key":"2025042916155139800_B37","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.tcs.2013.09.036","article-title":"The choice of the offspring population size in the (1, \u03bb) evolutionary algorithm","volume":"545","author":"Rowe","year":"2014","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"2025042916155139800_B38","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1109\/TAC.1968.1098903","article-title":"Adaptive step size random search","volume":"13","author":"Schumer","year":"1968","journal-title":"IEEE Transactions on Automatic Control"},{"issue":"3","key":"2025042916155139800_B39","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1109\/TEVC.2012.2202241","article-title":"A new method for lower bounds on the running time of evolutionary algorithms","volume":"17","author":"Sudholt","year":"2012","journal-title":"IEEE Transactions on Evolutionary Computation"},{"issue":"2","key":"2025042916155139800_B40","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1017\/S0963548312000600","article-title":"Tight bounds on the optimization time of a randomized search heuristic on linear functions","volume":"22","author":"Witt","year":"2013","journal-title":"Combinatorics, Probability and Computing"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/33\/1\/27\/2464259\/evco_a_00348.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/33\/1\/27\/2464259\/evco_a_00348.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T20:16:04Z","timestamp":1745957764000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/33\/1\/27\/120278\/OneMax-Is-Not-the-Easiest-Function-for-Fitness"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"references-count":40,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,3,15]]},"published-print":{"date-parts":[[2025,3,15]]}},"URL":"https:\/\/doi.org\/10.1162\/evco_a_00348","relation":{},"ISSN":["1530-9304"],"issn-type":[{"value":"1530-9304","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2025]]},"published":{"date-parts":[[2025]]}}}