{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T21:54:49Z","timestamp":1780610089191,"version":"3.54.1"},"reference-count":75,"publisher":"MIT Press","issue":"4","license":[{"start":{"date-parts":[[2023,4,6]],"date-time":"2023-04-06T00:00:00Z","timestamp":1680739200000},"content-version":"vor","delay-in-days":95,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,12,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Multiobjective evolutionary algorithms are successfully applied in many real-world multiobjective optimization problems. As for many other AI methods, the theoretical understanding of these algorithms is lagging far behind their success in practice. In particular, previous theory work considers mostly easy problems that are composed of unimodal objectives.<\/jats:p>\n               <jats:p>As a first step towards a deeper understanding of how evolutionary algorithms solve multimodal multiobjective problems, we propose the OneJumpZeroJump problem, a bi-objective problem composed of two objectives isomorphic to the classic jump function benchmark. We prove that the simple evolutionary multiobjective optimizer (SEMO) with probability one does not compute the full Pareto front, regardless of the runtime. In contrast, for all problem sizes n and all jump sizes k\u2208[4..n2-1], the global SEMO (GSEMO) covers the Pareto front in an expected number of \u0398((n-2k)nk) iterations. For k=o(n), we also show the tighter bound 32enk+1\u00b1o(nk+1), which might be the first runtime bound for an MOEA that is tight apart from lower-order terms. We also combine the GSEMO with two approaches that showed advantages in single-objective multimodal problems. When using the GSEMO with a heavy-tailed mutation operator, the expected runtime improves by a factor of at least k\u03a9(k). When adapting the recent stagnation-detection strategy of Rajabi and Witt (2022) to the GSEMO, the expected runtime also improves by a factor of at least k\u03a9(k) and surpasses the heavy-tailed GSEMO by a small polynomial factor in k. Via an experimental analysis, we show that these asymptotic differences are visible already for small problem sizes: A factor-5 speed-up from heavy-tailed mutation and a factor-10 speed-up from stagnation detection can be observed already for jump size 4 and problem sizes between 10 and 50. Overall, our results show that the ideas recently developed to aid single-objective evolutionary algorithms to cope with local optima can be effectively employed also in multiobjective optimization.<\/jats:p>","DOI":"10.1162\/evco_a_00328","type":"journal-article","created":{"date-parts":[[2023,4,6]],"date-time":"2023-04-06T19:40:30Z","timestamp":1680810030000},"page":"337-373","update-policy":"https:\/\/doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":15,"title":["Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives*"],"prefix":"10.1162","volume":"31","author":[{"given":"Weijie","family":"Zheng","sequence":"first","affiliation":[{"name":"School of Computer Science and Technology, International Research Institute for Artificial Intelligence, Harbin Institute of Technology, Shenzhen, China zhengweijie@hit.edu.cn"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benjamin","family":"Doerr","sequence":"additional","affiliation":[{"name":"Laboratoire d'Informatique (LIX), \u00c9cole Polytechnique, CNRS, Institut Polytechnique de Paris, Palaiseau, France doerr@lix.polytechnique.fr"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"281","published-online":{"date-parts":[[2023,12,1]]},"reference":[{"key":"2024030120030356100_B1","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/3449639.3459377","article-title":"Lazy parameter tuning and control: choosing all parameters randomly from a power-law distribution","author":"Antipov","year":"2021","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2024030120030356100_B2","doi-asserted-by":"publisher","first-page":"1724","DOI":"10.1007\/s00453-022-00957-5","article-title":"Fast mutation in crossover-based algorithms","volume":"84","author":"Antipov","year":"2022","journal-title":"Algorithmica"},{"key":"2024030120030356100_B3","first-page":"545","article-title":"Runtime analysis of a heavy-tailed (1+(\u03bb,\u03bb)) genetic algorithm on jump functions","author":"Antipov","year":"2020","journal-title":"Proceedings of the International Conference on Parallel Problem Solving from Nature, Part II"},{"key":"2024030120030356100_B4","doi-asserted-by":"publisher","first-page":"1573","DOI":"10.1007\/s00453-021-00907-7","article-title":"A rigorous runtime analysis of the (1+(\u03bb,\u03bb)) GA on jump functions","volume":"84","author":"Antipov","year":"2022","journal-title":"Algorithmica"},{"key":"2024030120030356100_B5","first-page":"2","article-title":"Optimal mutation rates in genetic search","author":"B\u00e4ck","year":"1993","journal-title":"Proceedings of the International Conference on Genetic Algorithms"},{"key":"2024030120030356100_B6","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/3449639.3459350","article-title":"A rigorous runtime analysis of the 2-MMAS ib  on jump functions: Ant colony optimizers can cope well with local optima","author":"Benbaki","year":"2021","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2024030120030356100_B7","first-page":"428","article-title":"Better running time of the non-dominated sorting genetic algorithm II (NSGA-II) by using stochastic tournament selection","author":"Bian","year":"2022","journal-title":"Proceedings of the International Conference on Parallel Problem Solving from Nature"},{"key":"2024030120030356100_B8","first-page":"1405","article-title":"A general approach to running time analysis of multi-objective evolutionary algorithms","author":"Bian","year":"2018","journal-title":"Proceedings of the International Joint Conference on Artificial Intelligence"},{"key":"2024030120030356100_B9","doi-asserted-by":"crossref","first-page":"765","DOI":"10.1145\/1276958.1277114","article-title":"Do additional objectives make a problem harder?","author":"Brockhoff","year":"2007","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2024030120030356100_B10","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1007\/978-3-540-87700-4_65","article-title":"Analyzing hypervolume indicator based algorithms","author":"Brockhoff","year":"2008","journal-title":"Proceedings of the International Conference on Parallel Problem Solving from Nature"},{"key":"2024030120030356100_B11","first-page":"4:1","article-title":"Automatic adaptation of hypermutation rates for multimodal optimisation","author":"Corus","year":"2021","journal-title":"Proceedings of Foundations of Genetic Algorithms"},{"key":"2024030120030356100_B12","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/j.tcs.2018.06.009","article-title":"Design and analysis of diversity-based parent selection schemes for speeding up evolutionary multi-objective optimisation","volume":"832","author":"Covantes Osuna","year":"2020","journal-title":"Theoretical Computer Science"},{"key":"2024030120030356100_B13","doi-asserted-by":"crossref","first-page":"1372","DOI":"10.1145\/3512290.3528873","article-title":"Fast non-elitist evolutionary algorithms with power-law ranking selection","author":"Dang","year":"2022","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2024030120030356100_B14","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1109\/TEVC.2017.2724201","article-title":"Escaping local optima using crossover with emergent diversity","volume":"22","author":"Dang","year":"2018","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2024030120030356100_B15","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1109\/4235.996017","article-title":"A fast and elitist multiobjective genetic algorithm: NSGA-II","volume":"6","author":"Deb","year":"2002","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2024030120030356100_B16","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: Recent developments in discrete optimization","author":"Doerr","year":"2020"},{"key":"2024030120030356100_B17","doi-asserted-by":"publisher","first-page":"3059","DOI":"10.1007\/s00453-020-00780-w","article-title":"The runtime of the compact genetic algorithm on Jump functions","volume":"83","author":"Doerr","year":"2021","journal-title":"Algorithmica"},{"key":"2024030120030356100_B18","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":"2024030120030356100_B19","first-page":"557","article-title":"Runtime analysis of evolutionary diversity maximization for OneMinMax","author":"Doerr","year":"2016","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2024030120030356100_B20","doi-asserted-by":"crossref","first-page":"520","DOI":"10.1145\/3512290.3528868","article-title":"The (1+(\u03bb,\u03bb)) global SEMO algorithm","author":"Doerr","year":"2022","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2024030120030356100_B21","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":"2024030120030356100_B22","first-page":"432","article-title":"Lower bounds for the runtime of a global multi-objective evolutionary algorithm","author":"Doerr","year":"2013","journal-title":"Proceedings of the Congress on Evolutionary Computation"},{"key":"2024030120030356100_B23","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":"2024030120030356100_B24","first-page":"399","article-title":"A first runtime analysis of the NSGA-II on a multimodal problem","author":"Doerr","year":"2022","journal-title":"Proceedings of the International Conference on Parallel Problem Solving from Nature"},{"key":"2024030120030356100_B25","article-title":"The first mathematical proof that crossover gives super-constant performance gains for the NSGA-II","volume-title":"Proceedings of the Conference on Artificial Intelligence","author":"Doerr","year":"2023"},{"key":"2024030120030356100_B26","doi-asserted-by":"crossref","DOI":"10.1609\/aaai.v37i10.26462","article-title":"From understanding the population dynamics of the NSGA-II to the first proven lower bounds","volume-title":"Proceedings of the Conference on Artificial Intelligence","author":"Doerr","year":"2023"},{"key":"2024030120030356100_B27","doi-asserted-by":"crossref","first-page":"12293","DOI":"10.1609\/aaai.v35i14.17459","article-title":"Theoretical analyses of multi-objective evolutionary algorithms on multi-modal objectives","author":"Doerr","year":"2021","journal-title":"Proceedings of the Conference on Artificial Intelligence"},{"key":"2024030120030356100_B28","first-page":"1088","article-title":"Analysis of the (1+1) EA for a noisy OneMax","author":"Droste","year":"2004","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2024030120030356100_B29","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"},{"key":"2024030120030356100_B30","doi-asserted-by":"crossref","first-page":"3534","DOI":"10.1609\/aaai.v33i01.33013534","article-title":"Unsupervised feature selection by Pareto optimization","author":"Feng","year":"2019","journal-title":"Proceedings of the AAAI Conference on Artificial Intelligence"},{"key":"2024030120030356100_B31","doi-asserted-by":"publisher","first-page":"854","DOI":"10.1016\/j.tcs.2009.06.020","article-title":"Plateaus can be harder in multi-objective optimization","volume":"411","author":"Friedrich","year":"2010","journal-title":"Theoretical Computer Science"},{"key":"2024030120030356100_B32","doi-asserted-by":"publisher","first-page":"1546","DOI":"10.1016\/j.tcs.2010.09.023","article-title":"Illustration of fairness in evolutionary multi-objective optimization","volume":"412","author":"Friedrich","year":"2011","journal-title":"Theoretical Computer Science"},{"key":"2024030120030356100_B33","first-page":"1918","article-title":"Expected runtimes of a simple multi-objective evolutionary algorithm","author":"Giel","year":"2003","journal-title":"Proceedings of the Congress on Evolutionary Computation"},{"key":"2024030120030356100_B34","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1162\/EVCO_a_00013","article-title":"On the effect of populations in evolutionary multi-objective optimisation","volume":"18","author":"Giel","year":"2010","journal-title":"Evolutionary Computation"},{"key":"2024030120030356100_B35","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1145\/1527125.1527131","article-title":"Single- and multi-objective evolutionary algorithms for graph bisectioning","author":"Greiner","year":"2009","journal-title":"Proceedings of Foundations of Genetic Algorithms"},{"key":"2024030120030356100_B36","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1162\/EVCO_a_00050","article-title":"Runtime analysis of an evolutionary algorithm for stochastic multi-objective combinatorial optimization","volume":"20","author":"Gutjahr","year":"2012","journal-title":"Evolutionary Computation"},{"key":"2024030120030356100_B37","doi-asserted-by":"crossref","first-page":"967","DOI":"10.1145\/3205455.3205608","article-title":"On the runtime dynamics of the compact genetic algorithm on jump functions","author":"Hasen\u00f6hrl","year":"2018","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2024030120030356100_B38","first-page":"113","article-title":"Analysis of a simple evolutionary algorithm for the multiobjective shortest path problem","author":"Horoba","year":"2009","journal-title":"Proceedings of the International Workshop on Foundations of Genetic Algorithms"},{"key":"2024030120030356100_B39","doi-asserted-by":"crossref","first-page":"2359","DOI":"10.1609\/aaai.v34i03.5615","article-title":"Runtime analysis of somatic contiguous hypermutation operators in MOEA\/D framework","author":"Huang","year":"2020","journal-title":"Proceedings of the Conference on Artificial Intelligence"},{"key":"2024030120030356100_B40","doi-asserted-by":"crossref","first-page":"2296","DOI":"10.1609\/aaai.v33i01.33012296","article-title":"Running time analysis of MOEA\/D with crossover on discrete optimization problem","author":"Huang","year":"2019","journal-title":"Proceedings of the Conference on Artificial Intelligence"},{"key":"2024030120030356100_B41","first-page":"1682","article-title":"A runtime analysis of typical decomposition approaches in MOEA\/D framework for many-objective optimization problems","author":"Huang","year":"2021","journal-title":"Proceedings of the International Joint Conference on Artificial Intelligence"},{"key":"2024030120030356100_B42","first-page":"25","article-title":"When the plus strategy outperforms the comma strategy and when not","author":"J\u00e4gersk\u00fcpper","year":"2007","journal-title":"Proceedings of Foundations of Computational Intelligence"},{"key":"2024030120030356100_B43","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1109\/4235.974841","article-title":"Evolutionary algorithms\u2014How to cope with plateaus of constant fitness and when to reject strings of the same fitness","volume":"5","author":"Jansen","year":"2001","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2024030120030356100_B44","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/s00453-002-0940-2","article-title":"The analysis of evolutionary algorithms\u2014A proof that crossover really can help","volume":"34","author":"Jansen","year":"2002","journal-title":"Algorithmica"},{"key":"2024030120030356100_B45","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.dam.2004.02.019","article-title":"Real royal road functions\u2014Where crossover provably is essential","volume":"149","author":"Jansen","year":"2005","journal-title":"Discrete Applied Mathematics"},{"key":"2024030120030356100_B46","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1016\/j.tcs.2006.03.007","article-title":"Analysis of a multiobjective evolutionary algorithm on the 0\u20131 knapsack problem","volume":"358","author":"Kumar","year":"2006","journal-title":"Theoretical Computer Science"},{"key":"2024030120030356100_B47","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1023\/B:NACO.0000023415.22052.55","article-title":"Running time analysis of evolutionary algorithms on a simplified multiobjective knapsack problem","volume":"3","author":"Laumanns","year":"2004","journal-title":"Natural Computing"},{"key":"2024030120030356100_B48","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1109\/TEVC.2004.823470","article-title":"Running time analysis of multiobjective evolutionary algorithms on pseudo-Boolean functions","volume":"8","author":"Laumanns","year":"2004","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2024030120030356100_B49","first-page":"44","article-title":"Running time analysis of multi-objective evolutionary algorithms on a simple discrete optimization problem","author":"Laumanns","year":"2002","journal-title":"Proceedings of the International Conference on Parallel Problem Solving from Nature"},{"key":"2024030120030356100_B50","first-page":"154","article-title":"On the limitations of the univariate marginal distribution algorithm to deception and where bivariate EDAs might help","author":"Lehre","year":"2019","journal-title":"Proceedings of the International Workshop on Foundations of Genetic Algorithms"},{"key":"2024030120030356100_B51","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1109\/TEVC.2015.2501315","article-title":"A primary theoretical study on decomposition-based multiobjective evolutionary algorithms","volume":"20","author":"Li","year":"2016","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2024030120030356100_B52","first-page":"2454","article-title":"Multimodal multi-objective optimization: A preliminary study","author":"Liang","year":"2016","journal-title":"Proceedings of the Congress on Evolutionary Computation"},{"key":"2024030120030356100_B53","first-page":"15","article-title":"How genetic algorithms really work: mutation and hillclimbing","author":"M\u00fchlenbein","year":"1992","journal-title":"Proceedings of the International Conference on Parallel Problem Solving from Nature"},{"key":"2024030120030356100_B54","doi-asserted-by":"publisher","first-page":"1620","DOI":"10.1016\/j.ejor.2006.08.005","article-title":"Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem","volume":"181","author":"Neumann","year":"2007","journal-title":"European Journal of Operational Research"},{"key":"2024030120030356100_B55","first-page":"72","article-title":"Approximating minimum multicuts by evolutionary multi-objective algorithms","author":"Neumann","year":"2008","journal-title":"Proceedings of Parallel Problem Solving from Nature"},{"key":"2024030120030356100_B56","first-page":"667","article-title":"How crossover speeds up evolutionary algorithms for the multi-criteria all-pairs-shortest-path problem","author":"Neumann","year":"2010","journal-title":"Proceedings of Parallel Problem Solving from Nature, Part I"},{"key":"2024030120030356100_B57","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-07407-8","volume-title":"Multimodal optimization by means of evolutionary algorithms","author":"Preuss","year":"2015"},{"key":"2024030120030356100_B58","doi-asserted-by":"crossref","first-page":"2408","DOI":"10.1609\/aaai.v34i03.5621","article-title":"Subset selection by Pareto optimization with recombination","author":"Qian","year":"2020","journal-title":"Proceedings of the AAAI Conference on Artificial Intelligence"},{"key":"2024030120030356100_B59","doi-asserted-by":"crossref","first-page":"835","DOI":"10.1007\/978-3-319-45823-6_78","article-title":"Selection hyper-heuristics can provably be helpful in evolutionary multi-objective optimization","author":"Qian","year":"2016","journal-title":"Proceedings of the International Conference on Parallel Problem Solving from Nature"},{"key":"2024030120030356100_B60","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.artint.2013.09.002","article-title":"An analysis on recombination in multi-objective evolutionary optimization","volume":"204","author":"Qian","year":"2013","journal-title":"Artificial Intelligence"},{"key":"2024030120030356100_B61","first-page":"389","article-title":"On constrained Boolean Pareto optimization","author":"Qian","year":"2015","journal-title":"Proceedings of the International Joint Conference on Artificial Intelligence"},{"key":"2024030120030356100_B62","first-page":"1395","article-title":"On multiset selection with size constraints","author":"Qian","year":"2018","journal-title":"Proceedings of the AAAI Conference on Artificial Intelligence"},{"key":"2024030120030356100_B63","first-page":"1314","article-title":"Self-adjusting evolutionary algorithms for multimodal optimization","author":"Rajabi","year":"2020","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2024030120030356100_B64","doi-asserted-by":"publisher","first-page":"1694","DOI":"10.1007\/s00453-022-00933-z","article-title":"Self-adjusting evolutionary algorithms for multimodal optimization","volume":"84","author":"Rajabi","year":"2022","journal-title":"Algorithmica"},{"key":"2024030120030356100_B65","first-page":"551","article-title":"Runtime analysis of evolutionary algorithms with biased mutation for the multi-objective minimum spanning tree problem","author":"Roostapour","year":"2020","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2024030120030356100_B66","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2021.103597","article-title":"Pareto optimization for subset selection with dynamic cost constraints","volume":"302","author":"Roostapour","year":"2022","journal-title":"Artificial Intelligence"},{"key":"2024030120030356100_B67","volume-title":"Convergence properties of evolutionary algorithms","author":"Rudolph","year":"1997"},{"key":"2024030120030356100_B68","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1109\/TEVC.2019.2909744","article-title":"A review of evolutionary multimodal multiobjective optimization","volume":"24","author":"Tanabe","year":"2020","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2024030120030356100_B69","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/3-540-36970-8_25","article-title":"Convergence time analysis for the multi-objective counting ones problem","author":"Thierens","year":"2003","journal-title":"Proceedings of the International Conference on Evolutionary Multi-Criterion Optimization"},{"key":"2024030120030356100_B70","first-page":"64","article-title":"Theoretical aspects of evolutionary algorithms","author":"Wegener","year":"2001","journal-title":"Proceedings of the International Colloquium on Automata, Languages and Programming"},{"key":"2024030120030356100_B71","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.tcs.2022.08.014","article-title":"How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys","volume":"940","author":"Witt","year":"2023","journal-title":"Theoretical Computer Science"},{"key":"2024030120030356100_B72","doi-asserted-by":"publisher","first-page":"712","DOI":"10.1109\/TEVC.2007.892759","article-title":"MOEA\/D: A multiobjective evolutionary algorithm based on decomposition","volume":"11","author":"Zhang","year":"2007","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2024030120030356100_B73","doi-asserted-by":"crossref","first-page":"611","DOI":"10.1145\/3512290.3528847","article-title":"Better approximation guarantees for the NSGA-II by using the current crowding distance","author":"Zheng","year":"2022","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2024030120030356100_B74","doi-asserted-by":"crossref","first-page":"10408","DOI":"10.1609\/aaai.v36i9.21283","article-title":"A first mathematical runtime analysis of the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)","author":"Zheng","year":"2022","journal-title":"Proceedings of the Conference on Artificial Intelligence"},{"key":"2024030120030356100_B75","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.swevo.2011.03.001","article-title":"Multiobjective evolutionary algorithms: A survey of the state of the art","volume":"1","author":"Zhou","year":"2011","journal-title":"Swarm and Evolutionary Computation"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/31\/4\/337\/2342348\/evco_a_00328.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/31\/4\/337\/2342348\/evco_a_00328.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,1]],"date-time":"2024-03-01T20:03:44Z","timestamp":1709323424000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/31\/4\/337\/115603\/Theoretical-Analyses-of-Multiobjective"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"references-count":75,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2023,12,1]]},"published-print":{"date-parts":[[2023,12,1]]}},"URL":"https:\/\/doi.org\/10.1162\/evco_a_00328","relation":{},"ISSN":["1530-9304"],"issn-type":[{"value":"1530-9304","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023]]},"published":{"date-parts":[[2023]]}}}