{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T00:06:52Z","timestamp":1774397212317,"version":"3.50.1"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,10,13]],"date-time":"2021-10-13T00:00:00Z","timestamp":1634083200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Center for Cognitive Research of ITMO University"},{"name":"Investissements d\u2019avenir project","award":["ANR-11-LABX-0056-LMH, LabEx LMH"],"award-info":[{"award-number":["ANR-11-LABX-0056-LMH, LabEx LMH"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Evol. Learn. Optim."],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>\n            To gain a better theoretical understanding of how evolutionary algorithms (EAs) cope with plateaus of constant fitness, we propose the\n            <jats:italic>n<\/jats:italic>\n            -dimensional\n            <jats:sc>Plateau<\/jats:sc>\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            function as natural benchmark and analyze how different variants of the (1 + 1)\u00a0EA optimize it. The\n            <jats:sc>Plateau<\/jats:sc>\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            function has a plateau of second-best fitness in a ball of radius\n            <jats:italic>k<\/jats:italic>\n            around the optimum. As evolutionary algorithm, we regard the (1 + 1)\u00a0EA using an arbitrary unbiased mutation operator. Denoting by \u03b1 the random number of bits flipped in an application of this operator and assuming that\n            <jats:italic>Pr<\/jats:italic>\n            [\u03b1 = 1] has at least some small sub-constant value, we show the surprising result that for all constant\n            <jats:italic>k<\/jats:italic>\n            \u2265 2, the runtime\u00a0\n            <jats:italic>T<\/jats:italic>\n            follows a distribution close to the geometric one with success probability equal to the probability to flip between 1 and\n            <jats:italic>k<\/jats:italic>\n            bits divided by the size of the plateau. Consequently, the expected runtime is the inverse of this number, and thus only depends on the probability to flip between 1 and\n            <jats:italic>k<\/jats:italic>\n            bits, but not on other characteristics of the mutation operator. Our result also implies that the optimal mutation rate for standard bit mutation here is approximately\u00a0\n            <jats:italic>k\/(en)<\/jats:italic>\n            . Our main analysis tool is a combined analysis of the Markov chains on the search point space and on the Hamming level space, an approach that promises to be useful also for other plateau problems.\n          <\/jats:p>","DOI":"10.1145\/3469800","type":"journal-article","created":{"date-parts":[[2021,10,13]],"date-time":"2021-10-13T22:05:35Z","timestamp":1634162735000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Precise Runtime Analysis for Plateau Functions"],"prefix":"10.1145","volume":"1","author":[{"given":"Denis","family":"Antipov","sequence":"first","affiliation":[{"name":"ITMO University, St. Petersburg, Russia and \u00c9cole Polytechnique, CNRS, France"}]},{"given":"Benjamin","family":"Doerr","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique, CNRS, France"}]}],"member":"320","published-online":{"date-parts":[[2021,10,13]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"2515","volume-title":"Congress on Evolutionary Computation","author":"Alanazi Fawaz","year":"2014","unstructured":"Fawaz Alanazi and Per Kristian Lehre. 2014. Runtime analysis of selection hyper-heuristics with classical learning mechanisms. In Congress on Evolutionary Computation. IEEE, 2515\u20132523."},{"key":"e_1_3_2_3_2","first-page":"117","volume-title":"Parallel Problem Solving from Nature, PPSN XV, Part II","author":"Antipov Denis","year":"2018","unstructured":"Denis Antipov and Benjamin Doerr. 2018. Precise runtime analysis for plateaus. In Parallel Problem Solving from Nature, PPSN XV, Part II. Springer, 117\u2013128."},{"key":"e_1_3_2_4_2","doi-asserted-by":"crossref","first-page":"1459","DOI":"10.1145\/3205455.3205627","volume-title":"Genetic and Evolutionary Computation Conference","author":"Antipov Denis","year":"2018","unstructured":"Denis Antipov, Benjamin Doerr, Jiefeng Fang, and Tangi Hetet. 2018. Runtime analysis for the (\\mu +\\lambda) EA optimizing OneMax. In Genetic and Evolutionary Computation Conference. ACM, 1459\u20131466."},{"key":"e_1_3_2_5_2","doi-asserted-by":"crossref","first-page":"1461","DOI":"10.1145\/3321707.3321838","volume-title":"Genetic and Evolutionary Computation Conference","author":"Antipov Denis","year":"2019","unstructured":"Denis Antipov, Benjamin Doerr, and Quentin Yang. 2019. The efficiency threshold for the offspring population size of the ( \\mathrm{\\mu } , \\lambda ) EA. In Genetic and Evolutionary Computation Conference. ACM, 1461\u20131469."},{"key":"e_1_3_2_6_2","first-page":"1","volume-title":"Parallel Problem Solving from Nature, PPSN XI","author":"B\u00f6ttcher S\u00fcntje","year":"2010","unstructured":"S\u00fcntje B\u00f6ttcher, Benjamin Doerr, and Frank Neumann. 2010. Optimal fixed and adaptive mutation rates for the leading ones problem. In Parallel Problem Solving from Nature, PPSN XI. Springer, 1\u201310."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2008.2009064"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1162\/EVCO_a_00185"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCB.2008.2012167"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2017.2753538"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3071178.3079194"},{"key":"e_1_3_2_12_2","first-page":"16","volume-title":"Parallel Problem Solving from Nature, PPSN XV, Part II","author":"Corus Dogan","year":"2018","unstructured":"Dogan Corus, Pietro S. Oliveto, and Donya Yazdani. 2018. Artificial immune systems can find arbitrarily good approximations for the NP-hard partition problem. In Parallel Problem Solving from Nature, PPSN XV, Part II. Springer, 16\u201328."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2017.2724201"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0103-x"},{"key":"e_1_3_2_15_2","doi-asserted-by":"crossref","first-page":"890","DOI":"10.1007\/978-3-319-45823-6_83","volume-title":"Parallel Problem Solving from Nature, PPSN XIV","author":"Dang Duc-Cuong","year":"2016","unstructured":"Duc-Cuong Dang, Tobias Friedrich, Timo K\u00f6tzing, Martin S. Krejca, Per Kristian Lehre, Pietro S. Oliveto, Dirk Sudholt, and Andrew M. Sutton. 2016. Emergence of diversity and its benefits for crossover in genetic algorithms. In Parallel Problem Solving from Nature, PPSN XIV. Springer, 890\u2013900."},{"key":"e_1_3_2_16_2","first-page":"25","volume-title":"Foundations of Genetic Algorithms","author":"Doerr Benjamin","year":"2019","unstructured":"Benjamin Doerr. 2019. An exponential lower bound for the runtime of the compact genetic algorithm on jump functions. In Foundations of Genetic Algorithms. ACM, 25\u201333."},{"key":"e_1_3_2_17_2","doi-asserted-by":"crossref","first-page":"1488","DOI":"10.1145\/3321707.3321747","volume-title":"Genetic and Evolutionary Computation Conference","author":"Doerr Benjamin","year":"2019","unstructured":"Benjamin Doerr. 2019. A tight runtime analysis for the CGA on jump functions: EDAs can cross fitness valleys at no extra cost. In Genetic and Evolutionary Computation Conference. ACM, 1488\u20131496."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0354-9"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-29414-4_6"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.11.028"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2014.07.009"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1162\/EVCO_a_00158"},{"key":"e_1_3_2_23_2","doi-asserted-by":"crossref","first-page":"1479","DOI":"10.1145\/3321707.3321733","volume-title":"Genetic and Evolutionary Computation Conference","author":"Doerr Benjamin","year":"2019","unstructured":"Benjamin Doerr, Carola Doerr, and Johannes Lengler. 2019. Self-adjusting mutation rates with provably optimal success rules. In Genetic and Evolutionary Computation Conference. ACM, 1479\u20131487."},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.06.014"},{"key":"e_1_3_2_25_2","first-page":"2083","volume-title":"Genetic and Evolutionary Computation Conference","author":"Doerr Benjamin","year":"2011","unstructured":"Benjamin Doerr, Mahmoud Fouz, and Carsten Witt. 2011. Sharp bounds by probability-generating functions and variable drift. In Genetic and Evolutionary Computation Conference. ACM, 2083\u20132090."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1162\/evco.2007.15.4.401"},{"key":"e_1_3_2_27_2","first-page":"929","volume-title":"Genetic and Evolutionary Computation Conference","author":"Doerr Benjamin","year":"2008","unstructured":"Benjamin Doerr, Tomas Jansen, and Christian Klein. 2008. Comparing global and local mutations on bit strings. In Genetic and Evolutionary Computation Conference. ACM, 929\u2013936."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1162\/EVCO_a_00055"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9622-x"},{"key":"e_1_3_2_30_2","doi-asserted-by":"crossref","first-page":"1470","DOI":"10.1145\/3321707.3321819","volume-title":"Genetic and Evolutionary Computation Conference","author":"Doerr Benjamin","year":"2019","unstructured":"Benjamin Doerr and Timo K\u00f6tzing. 2019. Multiplicative up-drift. In Genetic and Evolutionary Computation Conference. ACM, 1470\u20131478."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.10.039"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.03.015"},{"key":"e_1_3_2_33_2","doi-asserted-by":"crossref","first-page":"777","DOI":"10.1145\/3071178.3071301","volume-title":"Genetic and Evolutionary Computation Conference","author":"Doerr Benjamin","year":"2017","unstructured":"Benjamin Doerr, Huu Phuoc Le, R\u00e9gis Makhmara, and Ta Duy Nguyen. 2017. Fast genetic algorithms. In Genetic and Evolutionary Computation Conference. ACM, 777\u2013784."},{"key":"e_1_3_2_34_2","doi-asserted-by":"crossref","first-page":"1015","DOI":"10.1145\/3205455.3205611","volume-title":"Genetic and Evolutionary Computation Conference","author":"Doerr Benjamin","year":"2018","unstructured":"Benjamin Doerr, Andrei Lissovoi, Pietro S. Oliveto, and John A. Warwicker. 2018. On the runtime analysis of selection hyper-heuristics with adaptive learning periods. In Genetic and Evolutionary Computation Conference. ACM, 1015\u20131022."},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00182-7"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.08.021"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.06.020"},{"key":"e_1_3_2_38_2","first-page":"661","volume-title":"Genetic and Evolutionary Computation Conference","author":"Friedrich Tobias","year":"2016","unstructured":"Tobias Friedrich, Timo K\u00f6tzing, Martin S. Krejca, Samadhi Nallaperuma, Frank Neumann, and Martin Schirneck. 2016. Fast building block assembly by majority vote crossover. In Genetic and Evolutionary Computation Conference. ACM, 661\u2013668."},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1162\/evco.1999.7.2.173"},{"key":"e_1_3_2_40_2","first-page":"415","volume-title":"Symposium on Theoretical Aspects of Computer Science","author":"Giel Oliver","year":"2003","unstructured":"Oliver Giel and Ingo Wegener. 2003. Evolutionary algorithms and the maximum matching problem. In Symposium on Theoretical Aspects of Computer Science. Springer, 415\u2013426."},{"key":"e_1_3_2_41_2","doi-asserted-by":"crossref","first-page":"967","DOI":"10.1145\/3205455.3205608","volume-title":"Genetic and Evolutionary Computation Conference","author":"Hasen\u00f6hrl V\u00e1clav","year":"2018","unstructured":"V\u00e1clav Hasen\u00f6hrl and Andrew M. Sutton. 2018. On the runtime dynamics of the compact genetic algorithm on jump functions. In Genetic and Evolutionary Computation Conference. ACM, 967\u2013974."},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(01)00058-3"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1023\/B:NACO.0000023417.31393.c7"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1162\/evco_a_00212"},{"key":"e_1_3_2_45_2","first-page":"1","volume-title":"Foundations of Genetic Algorithms","author":"Hwang Hsien-Kuei","year":"2019","unstructured":"Hsien-Kuei Hwang and Carsten Witt. 2019. Sharp bounds on the runtime of the (1+1) EA via drift analysis and analytic combinatorial tools. In Foundations of Genetic Algorithms. ACM, 1\u201312."},{"key":"e_1_3_2_46_2","first-page":"25","volume-title":"Foundations of Computational Intelligence","author":"J\u00e4gersk\u00fcpper Jens","year":"2007","unstructured":"Jens J\u00e4gersk\u00fcpper and Tobias Storch. 2007. When the plus strategy outperforms the comma strategy and when not. In Foundations of Computational Intelligence. IEEE, 25\u201332."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1162\/106365605774666921"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/4235.974841"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-002-0940-2"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9616-8"},{"key":"e_1_3_2_51_2","doi-asserted-by":"crossref","first-page":"686","DOI":"10.1007\/978-3-319-13075-0_54","volume-title":"International Symposium on Algorithms and Computation","author":"Lehre Per Kristian","year":"2014","unstructured":"Per Kristian Lehre and Carsten Witt. 2014. Concentrated hitting times of randomized search heuristics with variable drift. In International Symposium on Algorithms and Computation. Springer, 686\u2013697."},{"key":"e_1_3_2_52_2","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1145\/3071178.3071288","volume-title":"Genetic and Evolutionary Computation Conference","author":"Lissovoi Andrei","year":"2017","unstructured":"Andrei Lissovoi, Pietro S. Oliveto, and John A. Warwicker. 2017. On the runtime analysis of generalised selection hyper-heuristics for pseudo-Boolean optimisation. In Genetic and Evolutionary Computation Conference. ACM, 849\u2013856."},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719512"},{"key":"e_1_3_2_54_2","doi-asserted-by":"crossref","first-page":"1423","DOI":"10.1145\/3067695.3082507","volume-title":"Genetic and Evolutionary Computation Conference Companion","author":"Mironovich Vladimir","year":"2017","unstructured":"Vladimir Mironovich and Maxim Buzdalov. 2017. Evaluation of heavy-tailed mutation operator on maximum flow test generation problem. In Genetic and Evolutionary Computation Conference Companion. ACM, 1423\u20131426."},{"key":"e_1_3_2_55_2","volume-title":"Local Search in Combinatorial Optimization","author":"M\u00fchlenbein Heinz","year":"1993","unstructured":"Heinz M\u00fchlenbein. 1993. Evolutionary algorithms: Theory and applications. In Local Search in Combinatorial Optimization. Wiley."},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11721-008-0023-3"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.11.002"},{"key":"e_1_3_2_58_2","volume-title":"An Introduction to Partial Differential Equations","author":"Renardy Michael","year":"2004","unstructured":"Michael Renardy and Robert C. Rogers. 2004. An Introduction to Partial Differential Equations. Springer."},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.09.036"},{"key":"e_1_3_2_60_2","first-page":"50","volume-title":"International Conference on Evolutionary Computation","author":"Rudolph G\u00fcnter","year":"1996","unstructured":"G\u00fcnter Rudolph. 1996. Convergence of evolutionary algorithms in general search spaces. In International Conference on Evolutionary Computation. IEEE, 50\u201354."},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2012.2202241"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00671-0"},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1109\/21.370197"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00263-7"},{"key":"e_1_3_2_65_2","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1007\/3-540-48224-5_6","volume-title":"Automata, Languages and Programming","author":"Wegener Ingo","year":"2001","unstructured":"Ingo Wegener. 2001. Theoretical aspects of evolutionary algorithms. In Automata, Languages and Programming. Springer, 64\u201378."},{"key":"e_1_3_2_66_2","first-page":"55","volume-title":"Parallel Problem Solving from Nature, PPSN XV, Part II","author":"Whitley Darrell","year":"2018","unstructured":"Darrell Whitley, Swetha Varadarajan, Rachel Hirsch, and Anirban Mukhopadhyay. 2018. Exploration and exploitation without mutation: Solving the jump function in \\Theta (n) time. In Parallel Problem Solving from Nature, PPSN XV, Part II. Springer, 55\u201366."},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1162\/106365606776022751"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000600"}],"container-title":["ACM Transactions on Evolutionary Learning and Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3469800","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3469800","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:15Z","timestamp":1750188615000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3469800"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,13]]},"references-count":67,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3469800"],"URL":"https:\/\/doi.org\/10.1145\/3469800","relation":{},"ISSN":["2688-299X","2688-3007"],"issn-type":[{"value":"2688-299X","type":"print"},{"value":"2688-3007","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,13]]},"assertion":[{"value":"2019-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}