{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T23:19:43Z","timestamp":1769728783828,"version":"3.49.0"},"reference-count":34,"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>The fitness level method is a popular tool for analyzing the hitting time of elitist evolutionary algorithms. Its idea is to divide the search space into multiple fitness levels and estimate lower and upper bounds on the hitting time using transition probabilities between fitness levels. However, the lower bound generated by this method is often loose. An open question regarding the fitness level method is what are the tightest lower and upper time bounds that can be constructed based on transition probabilities between fitness levels. To answer this question, we combine drift analysis with fitness levels and define the tightest bound problem as a constrained multiobjective optimization problem subject to fitness levels. The tightest metric bounds by fitness levels are constructed and proven for the first time. Then linear bounds are derived from metric bounds and a framework is established that can be used to develop different fitness level methods for different types of linear bounds. The framework is generic and promising, as it can be used to draw tight time bounds on both fitness landscapes with and without shortcuts. This is demonstrated in the example of the (1+1) EA maximizing the TwoMax1 function.<\/jats:p>","DOI":"10.1162\/evco_a_00349","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T16:50:11Z","timestamp":1711471811000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":4,"title":["Drift Analysis with Fitness Levels for Elitist Evolutionary Algorithms"],"prefix":"10.1162","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5616-4691","authenticated-orcid":true,"given":"Jun","family":"He","sequence":"first","affiliation":[{"name":"Department of Computer Science, Nottingham Trent University, Nottingham NG11 8NS, United Kingdom jun.he@ntu.ac.uk"}]},{"given":"Yuren","family":"Zhou","sequence":"additional","affiliation":[{"name":"School of Data and Computer Science, Sun Yatsen University, Guangzhou, 510006, China zhouyuren@mail.sysu.edu.cn"}]}],"member":"281","published-online":{"date-parts":[[2025,3,15]]},"reference":[{"key":"2025042916155092300_B1","first-page":"555","article-title":"Runtime analysis of unbalanced block-parallel evolutionary algorithms","author":"Aboutaib","year":"2022","journal-title":"International Conference on Parallel Problem Solving from Nature"},{"key":"2025042916155092300_B2","doi-asserted-by":"crossref","first-page":"1886","DOI":"10.1145\/3205651.3208231","article-title":"Runtime analysis of a population-based evolutionary algorithm with auxiliary objectives selected by reinforcement learning","author":"Antipov","year":"2018","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference Companion"},{"issue":"4","key":"2025042916155092300_B3","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1109\/TEVC.2020.2985450","article-title":"Self-adaptation in nonelitist evolutionary algorithms on discrete problems with unknown structure","volume":"24","author":"Case","year":"2020","journal-title":"IEEE Transactions on Evolutionary Computation"},{"issue":"5","key":"2025042916155092300_B4","doi-asserted-by":"publisher","first-page":"1092","DOI":"10.1109\/TSMCB.2008.2012167","article-title":"A new approach for analyzing average time complexity of population-based evolutionary algorithms on unimodal problems","volume":"39","author":"Chen","year":"2009","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)"},{"issue":"5","key":"2025042916155092300_B5","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1109\/TEVC.2017.2753538","article-title":"Level-based analysis of genetic algorithms and other search processes","volume":"22","author":"Corus","year":"2017","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2025042916155092300_B6","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/j.tcs.2019.03.002","article-title":"When hypermutations and ageing enable artificial immune systems to outperform evolutionary algorithms","volume":"832","author":"Corus","year":"2020","journal-title":"Theoretical Computer Science"},{"key":"2025042916155092300_B7","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.tcs.2018.09.024","article-title":"Analyzing randomized search heuristics via stochastic domination","volume":"773","author":"Doerr","year":"2019","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"2025042916155092300_B8","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"},{"issue":"64","key":"2025042916155092300_B9","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1007\/s00453-012-9622-x","article-title":"Multiplicative drift analysis","volume":"4","author":"Doerr","year":"2012","journal-title":"Algorithmica"},{"key":"2025042916155092300_B10","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-022-00952-w","article-title":"Lower bounds from fitness levels made easy","author":"Doerr","year":"2024","journal-title":"Algorithmica"},{"key":"2025042916155092300_B11","volume-title":"Theory of evolutionary computation: Recent developments in discrete optimization","author":"Doerr","year":"2019"},{"issue":"2","key":"2025042916155092300_B12","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":"2015","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2025042916155092300_B13","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2311.10502","article-title":"Fast estimations of lower bounds on hitting time of elitist evolutionary algorithms","author":"He","year":"2023"},{"issue":"2","key":"2025042916155092300_B14","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1109\/TEVC.2015.2444793","article-title":"Average convergence rate of evolutionary algorithms","volume":"20","author":"He","year":"2016","journal-title":"IEEE Transactions on Evolutionary Computation"},{"issue":"1","key":"2025042916155092300_B15","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/S0004-3702(01)00058-3","article-title":"Drift analysis and average time complexity of evolutionary algorithms","volume":"127","author":"He","year":"2001","journal-title":"Artificial Intelligence"},{"issue":"5","key":"2025042916155092300_B16","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1109\/TEVC.2002.800886","article-title":"From an individual to a population: An analysis of the first hitting time of population-based evolutionary algorithms","volume":"6","author":"He","year":"2002","journal-title":"IEEE Transactions on Evolutionary Computation"},{"issue":"1-2","key":"2025042916155092300_B17","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0004-3702(02)00381-8","article-title":"Towards an analytic framework for analysing the computation time of evolutionary algorithms","volume":"145","author":"He","year":"2003","journal-title":"Artificial Intelligence"},{"issue":"3","key":"2025042916155092300_B18","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1109\/TEVC.2016.2608420","article-title":"Average drift analysis and population scalability","volume":"21","author":"He","year":"2017","journal-title":"IEEE Transactions on Evolutionary Computation"},{"issue":"2","key":"2025042916155092300_B19","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1109\/TEVC.2019.2921547","article-title":"An experimental method to estimate running time of evolutionary algorithms for continuous optimization","volume":"24","author":"Huang","year":"2019","journal-title":"IEEE Transactions on Evolutionary Computation"},{"issue":"2","key":"2025042916155092300_B20","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/1008328.1008329","article-title":"Big omicron and big omega and big theta","volume":"8","author":"Knuth","year":"1976","journal-title":"ACM Sigact News"},{"key":"2025042916155092300_B21","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/j.tcs.2019.08.021","article-title":"First-hitting times under drift","volume":"796","author":"K\u00f6tzing","year":"2019","journal-title":"Theoretical Computer Science"},{"key":"2025042916155092300_B22","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/978-3-030-29414-4_2","article-title":"Drift analysis","volume-title":"Theory of evolutionary computation: Recent developments in discrete optimization","author":"Lengler","year":"2020"},{"key":"2025042916155092300_B23","doi-asserted-by":"publisher","DOI":"10.1016\/j.swevo.2022.101078","article-title":"Runtime analysis of convex evolutionary search algorithm with standard crossover","volume":"71","author":"Malalanirainy","year":"2022","journal-title":"Swarm and Evolutionary Computation"},{"issue":"3","key":"2025042916155092300_B24","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/s11633-007-0281-3","article-title":"Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results","volume":"4","author":"Oliveto","year":"2007","journal-title":"International Journal of Automation and Computing"},{"issue":"6","key":"2025042916155092300_B25","doi-asserted-by":"publisher","first-page":"1603","DOI":"10.1007\/s00453-021-00893-w","article-title":"Tight bounds on the expected runtime of a standard steady state genetic algorithm","volume":"84","author":"Oliveto","year":"2022","journal-title":"Algorithmica"},{"issue":"3","key":"2025042916155092300_B26","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/s00453-010-9387-z","article-title":"Simplified drift analysis for proving lower bounds in evolutionary computation","volume":"59","author":"Oliveto","year":"2011","journal-title":"Algorithmica"},{"issue":"3","key":"2025042916155092300_B27","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/s11047-021-09841-7","article-title":"Evolutionary algorithms and submodular functions: Benefits of heavy-tailed mutations","volume":"20","author":"Quinzan","year":"2021","journal-title":"Natural Computing"},{"key":"2025042916155092300_B28","doi-asserted-by":"crossref","first-page":"1314","DOI":"10.1145\/3377930.3389833","article-title":"Self-adjusting evolutionary algorithms for multimodal optimization","author":"Rajabi","year":"2020","journal-title":"Proceedings of the 2020 Genetic and Evolutionary Computation Conference"},{"issue":"3","key":"2025042916155092300_B29","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"},{"key":"2025042916155092300_B30","first-page":"64","article-title":"Theoretical aspects of evolutionary algorithms","author":"Wegener","year":"2001","journal-title":"International Colloquium on Automata, Languages, and Programming"},{"key":"2025042916155092300_B31","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/0-306-48041-7_14","article-title":"Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions","author":"Wegener","year":"2003","journal-title":"Evolutionary Optimization"},{"issue":"1-2","key":"2025042916155092300_B32","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/j.ipl.2013.09.013","article-title":"Fitness levels with tail bounds for the analysis of randomized search heuristics","volume":"114","author":"Witt","year":"2014","journal-title":"Information Processing Letters"},{"issue":"15","key":"2025042916155092300_B33","doi-asserted-by":"publisher","first-page":"1809","DOI":"10.1016\/j.artint.2008.07.001","article-title":"A new approach to estimating the expected first hitting time of evolutionary algorithms","volume":"172","author":"Yu","year":"2008","journal-title":"Artificial Intelligence"},{"issue":"2","key":"2025042916155092300_B34","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1016\/j.artint.2008.11.002","article-title":"A comparative runtime analysis of heuristic algorithms for satisfiability problems","volume":"173","author":"Zhou","year":"2009","journal-title":"Artificial Intelligence"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/33\/1\/1\/2464261\/evco_a_00349.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/33\/1\/1\/2464261\/evco_a_00349.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T20:15:59Z","timestamp":1745957759000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/33\/1\/1\/120277\/Drift-Analysis-with-Fitness-Levels-for-Elitist"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"references-count":34,"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_00349","relation":{},"ISSN":["1530-9304"],"issn-type":[{"value":"1530-9304","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2025]]},"published":{"date-parts":[[2025]]}}}