{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T11:37:05Z","timestamp":1778931425789,"version":"3.51.4"},"reference-count":37,"publisher":"MIT Press","issue":"1","content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,3,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Recently a mechanism called stagnation detection was proposed that automatically adjusts the mutation rate of evolutionary algorithms when they encounter local optima. The so-called SD-(1+1) EA introduced by Rajabi and Witt (2022) adds stagnation detection to the classical (1+1) EA with standard bit mutation. This algorithm flips each bit independently with some mutation rate, and stagnation detection raises the rate when the algorithm is likely to have encountered a local optimum. In this article, we investigate stagnation detection in the context of the k-bit flip operator of randomized local search that flips k bits chosen uniformly at random and let stagnation detection adjust the parameter k. We obtain improved runtime results compared with the SD-(1+1) EA amounting to a speedup of at least (1-o(1))2\u03c0m, where m is the so-called gap size, that is, the distance to the next improvement. Moreover, we propose additional schemes that prevent infinite optimization times even if the algorithm misses a working choice of k due to unlucky events. Finally, we present an example where standard bit mutation still outperforms the k-bit flip operator with stagnation detection.<\/jats:p>","DOI":"10.1162\/evco_a_00313","type":"journal-article","created":{"date-parts":[[2022,7,20]],"date-time":"2022-07-20T18:23:51Z","timestamp":1658341431000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":18,"title":["Stagnation Detection with Randomized Local Search*"],"prefix":"10.1162","volume":"31","author":[{"given":"Amirhossein","family":"Rajabi","sequence":"first","affiliation":[{"name":"DTU Compute, Technical University of Denmark, Kgs. Lyngby, Denmark amraj@dtu.dk"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carsten","family":"Witt","sequence":"additional","affiliation":[{"name":"DTU Compute, Technical University of Denmark, Kgs. Lyngby, Denmark cawi@dtu.dk"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","published-online":{"date-parts":[[2023,3,1]]},"reference":[{"issue":"7","key":"2023030103554620000_","doi-asserted-by":"publisher","first-page":"885","DOI":"10.3103\/S0146411621070208","article-title":"The \u201cone-fifth rule\u201d with rollbacks for self-adjustment of the population size in the (1+(\u03bb, \u03bb)) genetic algorithm","volume":"55","author":"Bassin","year":"2021","journal-title":"Automatic Control and Computer Sciences"},{"key":"2023030103554620000_","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-3-319-99259-4_6","article-title":"Fast artificial immune systems","volume":"11102","author":"Corus","year":"2018","journal-title":"Parallel Problem Solving from Nature"},{"key":"2023030103554620000_","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1007\/978-3-319-45823-6_75","article-title":"Self-adaptation of mutation rates in non-elitist populations","author":"Dang","year":"2016","journal-title":"Parallel Problem Solving from Nature"},{"key":"2023030103554620000_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-030-29414-4","volume-title":"Theory of evolutionary computation\u2014Recent developments in discrete optimization","author":"Doerr","year":"2020"},{"issue":"5","key":"2023030103554620000_","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":"2023030103554620000_","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/978-3-030-29414-4_6","volume-title":"Theory of evolutionary computation\u2014Recent developments in discrete optimization","author":"Doerr","year":"2020"},{"issue":"10","key":"2023030103554620000_","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":"2023030103554620000_","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1007\/978-3-319-45823-6_77","article-title":"k-bit mutation with self-adjusting k outperforms standard bit mutation.","volume":"9921","author":"Doerr","year":"2016","journal-title":"Parallel Problem Solving from Nature"},{"key":"2023030103554620000_","first-page":"1457","article-title":"Quasirandom evolutionary algorithms","author":"Doerr","year":"2010","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"issue":"2","key":"2023030103554620000_","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1007\/s00453-018-0502-x","article-title":"The (1 + \u03bb) evolutionary algorithm with self-adjusting mutation rate","volume":"81","author":"Doerr","year":"2019","journal-title":"Algorithmica"},{"issue":"1","key":"2023030103554620000_","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/s00453-011-9585-3","article-title":"Adaptive drift analysis","volume":"65","author":"Doerr","year":"2013","journal-title":"Algorithmica"},{"key":"2023030103554620000_","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/1389095.1389274","article-title":"Comparing global and local mutations on bit strings","author":"Doerr","year":"2008","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2023030103554620000_","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"},{"key":"2023030103554620000_","doi-asserted-by":"crossref","first-page":"777","DOI":"10.1145\/3071178.3071301","article-title":"Fast genetic algorithms","author":"Doerr","year":"2017","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2023030103554620000_","doi-asserted-by":"crossref","first-page":"1015","DOI":"10.1145\/3205455.3205611","article-title":"On the runtime analysis of selection hyper-heuristics with adaptive learning periods","author":"Doerr","year":"2018","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2023030103554620000_","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/978-3-031-04148-8_13","article-title":"Stagnation detection meets fast mutation","author":"Doerr","year":"2022","journal-title":"Proceedings of the 22nd European Conference on Evolutionary Computation in Combinatorial Optimization"},{"key":"2023030103554620000_","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0304-3975(01)00182-7","article-title":"On the analysis of the (1+1) evolutionary algorithm","volume":"276","author":"Droste","year":"2002","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"2023030103554620000_","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u0151s","year":"1960","journal-title":"Publications of the Mathematical Institute of the Hungarian Academy of Sciences"},{"key":"2023030103554620000_","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1007\/978-3-319-07124-4_19","volume-title":"Handbook of heuristics","author":"Hansen","year":"2018"},{"issue":"4","key":"2023030103554620000_","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1162\/1063656043138905","article-title":"The cooperative coevolutionary (1+1) EA","volume":"12","author":"Jansen","year":"2004","journal-title":"Evolutionary Computation"},{"key":"2023030103554620000_","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1145\/1967654.1967671","article-title":"Adaptive population models for offspring populations and parallel evolutionary algorithms","author":"L\u00e4ssig","year":"2011","journal-title":"Proceedings of Foundations of Genetic Algorithms"},{"key":"2023030103554620000_","doi-asserted-by":"crossref","first-page":"2322","DOI":"10.1609\/aaai.v33i01.33012322","article-title":"On the time complexity of algorithm selection hyper-heuristics for multimodal optimisation","author":"Lissovoi","year":"2019","journal-title":"Proceedings of the AAAI Conference on Artificial Intelligence"},{"issue":"3","key":"2023030103554620000_","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1162\/evco_a_00258","article-title":"Simple hyper-heuristics control the neighbourhood size of randomised local search optimally for LeadingOnes","volume":"28","author":"Lissovoi","year":"2020","journal-title":"Evolutionary Computation"},{"key":"2023030103554620000_","article-title":"Sum of \u201cthe first k\u201d binomial coefficients for fixed n","author":"Lugo","year":"2017"},{"key":"2023030103554620000_","first-page":"51","article-title":"When will a genetic algorithm outperform hill climbing?","volume":"6","author":"Mitchell","year":"1993","journal-title":"Advances in Neural Information Processing Systems"},{"key":"2023030103554620000_","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.tcs.2006.11.002","article-title":"Randomized local search, evolutionary algorithms, and the minimum spanning tree problem","volume":"378","author":"Neumann","year":"2007","journal-title":"Theoretical Computer Science"},{"key":"2023030103554620000_","volume-title":"Bioinspired computation in combinatorial optimization\u2014Algorithms and their computational complexity","author":"Neumann","year":"2010"},{"issue":"2","key":"2023030103554620000_","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1109\/TEVC.2006.871251","article-title":"Biased mutation operators for subgraph-selection problems","volume":"10","author":"Raidl","year":"2006","journal-title":"IEEE Transaction on Evolutionary Computation"},{"key":"2023030103554620000_","doi-asserted-by":"crossref","first-page":"1178","DOI":"10.1145\/3449639.3459336","article-title":"Stagnation detection in highly multimodal fitness landscapes","author":"Rajabi","year":"2021","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2023030103554620000_","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1007\/978-3-030-72904-2_10","article-title":"Stagnation detection with randomized local search","author":"Rajabi","year":"2021","journal-title":"Proceedings of the 21st European Conference on Evolutionary Computation in Combinatorial Optimization"},{"key":"2023030103554620000_","first-page":"1","article-title":"Self-adjusting evolutionary algorithms for multimodal optimization","author":"Rajabi","year":"2022","journal-title":"Algorithmica"},{"key":"2023030103554620000_","doi-asserted-by":"crossref","first-page":"1713","DOI":"10.1145\/1569901.1570131","article-title":"Dynamic evolutionary optimisation: An analysis of frequency and magnitude of change","author":"Rohlfshagen","year":"2009","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2023030103554620000_","author":"Warwicker","year":"2019","journal-title":"On the runtime analysis of selection hyper-heuristics for pseudo-Boolean optimisation"},{"key":"2023030103554620000_","article-title":"Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions","volume-title":"Evolutionary optimization","author":"Wegener","year":"2001"},{"issue":"1\u20132","key":"2023030103554620000_","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1017\/S0963548304006650","article-title":"On the optimization of monotone polynomials by simple randomized search heuristics","volume":"14","author":"Wegener","year":"2005","journal-title":"Combinatorics, Probability and Computing"},{"key":"2023030103554620000_","first-page":"1996","article-title":"Population size vs. runtime of a simple EA","author":"Witt","year":"2003","journal-title":"Proceedings of the Congress on Evolutionary Computation"},{"issue":"1","key":"2023030103554620000_","first-page":"65","article-title":"Runtime analysis of the (\u03bc+1) EA on simple pseudo-Boolean functions","volume":"14","author":"Witt","year":"2006","journal-title":"Evolutionary Computation"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/31\/1\/1\/2071956\/evco_a_00313.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/31\/1\/1\/2071956\/evco_a_00313.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,24]],"date-time":"2023-11-24T20:12:36Z","timestamp":1700856756000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/31\/1\/1\/112389\/Stagnation-Detection-with-Randomized-Local-Search"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"references-count":37,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,3,1]]},"published-print":{"date-parts":[[2023,3,1]]}},"URL":"https:\/\/doi.org\/10.1162\/evco_a_00313","relation":{},"ISSN":["1530-9304"],"issn-type":[{"value":"1530-9304","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023]]},"published":{"date-parts":[[2023]]}}}