Hot off the Press: Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives
Pages 67 - 68
Abstract
The NSGA-II is one of the most prominent algorithms to solve multi-objective optimization problems. Despite numerous successful applications, several studies have shown that the NSGA-II is less effective for larger numbers of objectives. In this work, we use mathematical runtime analyses to rigorously demonstrate and quantify this phenomenon. We show that even on the simple m-objective generalization of the discrete OneMinMax benchmark, where every solution is Pareto optimal, the NSGA-II also with large population sizes cannot compute the full Pareto front (objective vectors of all Pareto optima) in sub-exponential time when the number of objectives is at least three. The reason for this unexpected behavior lies in the fact that in the computation of the crowding distance, the different objectives are regarded independently. This is not a problem for two objectives, where any sorting of a pair-wise incomparable set of solutions according to one objective is also such a sorting according to the other objective (in the inverse order).
This paper for the Hot-off-the-Press track at GECCO 2024 summarizes the work Weijie Zheng, Benjamin Doerr: Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives. IEEE Transactions on Evolutionary Computation, in press. https://doi.org/10.1109/TEVC.2023.3320278 [23].
References
[1]
Nicola Beume, Boris Naujoks, and Michael Emmerich. 2007. SMS-EMOA: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research 181 (2007), 1653--1669.
[2]
Chao Bian and Chao Qian. 2022. Better running time of the non-dominated sorting genetic algorithm II (NSGA-II) by using stochastic tournament selection. In Parallel Problem Solving From Nature, PPSN 2022. Springer, 428--441.
[3]
Kalyanmoy Deb and Himanshu Jain. 2014. An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints. IEEE Transactions on Evolutionary Computation 18 (2014), 577--601.
[4]
Kalyanmoy Deb, Manikanth Mohan, and Sikhar Mishra. 2003. A fast multi-objective evolutionary algorithm for finding well-spread Pareto-optimal solutions. KanGAL report 2003002 (2003).
[5]
Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and T. Meyarivan. 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6 (2002), 182--197.
[6]
Benjamin Doerr, Daniel Johannsen, and Carola Winzen. 2012. Multiplicative drift analysis. Algorithmica 64 (2012), 673--697.
[7]
Félix-Antoine Fortin and Marc Parizeau. 2013. Revisiting the NSGA-II crowding-distance computation. In Genetic and Evolutionary Computation Conference, GECCO 2013. ACM, 623--630.
[8]
Christian Igel, Nikolaus Hansen, and Stefan Roth. 2007. Covariance matrix adaptation for multi-objective optimization. Evolutionary Computation 15 (2007), 1--28.
[9]
Hisao Ishibuchi, Noritaka Tsukamoto, and Yusuke Nojima. 2008. Evolutionary many-objective optimization: A short review. In IEEE Congress on Evolutionary Computation, CEC 2008. IEEE, 2419--2426.
[10]
Tudor Ivan, Martin S. Krejca, and Benjamin Doerr. 2024. Speeding Up the NSGA-II With a Simple Tie-Breaking Rule. (2024). Preprint.
[11]
Vineet Khare, Xin Yao, and Kalyanmoy Deb. 2003. Performance scaling of multi-objective evolutionary algorithms. In International Conference on Evolutionary Multi-criterion Optimization, EMO 2003. Springer, 376--390.
[12]
Saku Kukkonen and Kalyanmoy Deb. 2006. Improved pruning of non-dominated solutions based on crowding distance for bi-objective optimization problems. In Conference on Evolutionary Computation, CEC 2006. IEEE, 1179--1186.
[13]
Bingdong Li, Jinlong Li, Ke Tang, and Xin Yao. 2015. Many-objective evolutionary algorithms: A survey. ACM Computing Surveys (CSUR) 48 (2015), 1--35.
[14]
Andre Opris, Due Cuong Dang, Frank Neumann, and Dirk Sudholt. 2024. Runtime analyses of NSGA-III on many-objective problems. In Genetic and Evolutionary Computation Conference, GECCO 2024. ACM. To appear.
[15]
Robin C. Purshouse and Peter J. Fleming. 2007. On the evolutionary optimization of many conflicting objectives. IEEE Transactions on Evolutionary Computation 11 (2007), 770--784.
[16]
Dirk Sudholt. 2013. A new method for lower bounds on the running time of evolutionary algorithms. IEEE Transactions on Evolutionary Computation 17 (2013), 418--435.
[17]
Vimal L. Vachhani, Vipul K. Dabhi, and Harshadkumar B. Prajapati. 2016. Improving NSGA-II for solving multi objective function optimization problems. In International Conference on Computer Communication and Informatics, ICCCI 2016. IEEE, 1--6.
[18]
Yali Wang, Michael Emmerich, André Deutz, and Thomas Bäck. 2019. Diversity-indicator based multi-objective evolutionary algorithm: DI-MOEA. In International Conference on Evolutionary Multi-Criterion Optimization, EMO 2019. Springer, 346--358.
[19]
Simon Wietheger and Benjamin Doerr. 2023. A mathematical runtime analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III). In International joint Conference on Artificial Intelligence, IJCAI 2023. ijcai.org, 5657--5665.
[20]
Carsten Witt. 2013. Tight bounds on the optimization time of a randomized search heuristic on linear functions. Combinatorics, Probability & Computing 22 (2013), 294--318.
[21]
Weijie Zheng and Benjamin Doerr. 2022. Better approximation guarantees for the NSGA-II by using the current crowding distance. In Genetic and Evolutionary Computation Conference, GECCO 2022. ACM, 611--619.
[22]
Weijie Zheng and Benjamin Doerr. 2023. Mathematical runtime analysis for the non-dominated sorting genetic algorithm II (NSGA-II). Artificial Intelligence 325 (2023), 104016.
[23]
Weijie Zheng and Benjamin Doerr. 2023. Runtime analysis for the NSGA-II: proving, quantifying, and explaining the inefficiency for many objectives. IEEE Transactions on Evolutionary Computation (2023). In press
[24]
Weijie Zheng and Benjamin Doerr. 2024. Runtime analysis of the SMS-EMOA for many-objective optimization. In Conference on Artificial Intelligence, AAAI 2024. AAAI Press.
[25]
Weijie Zheng, Yufei Liu, and Benjamin Doerr. 2022. A first mathematical run-time analysis of the Non-Dominated Sorting Genetic Algorithm II (NSGA-II). In Conference on Artificial Intelligence, AAAI 2022. AAAI Press, 10408--10416.
[26]
Eckart Zitzler and Lothar Thiele. 1999. Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation 3 (1999), 257--271.
Index Terms
- Hot off the Press: Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives
Recommendations
Hot off the Press: Runtime Analysis of the SMS-EMOA for Many-Objective Optimization
GECCO '24 Companion: Proceedings of the Genetic and Evolutionary Computation Conference CompanionThe NSGA-II was recently proven to have difficulties in many-objective optimization. In contrast, the literature experimentally shows a good performance of the SMS-EMOA, which can be seen as a steady-state NSGA-II that uses the hypervolume contribution ...
A first mathematical runtime analysis of the non-dominated sorting genetic algorithm II (NSGA-II): (hot-off-the-press track at GECCO 2022)
GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference CompanionThe non-dominated sorting genetic algorithm II (NSGA-II) is the most intensively used multi-objective evolutionary algorithm (MOEA) in real-world applications. However, in contrast to several simple MOEAs analyzed also via mathematical means, no such ...
Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency for Many Objectives
The nondominated sorting genetic algorithm II (NSGA-II) is one of the most prominent algorithms to solve multiobjective optimization problems. Despite numerous successful applications, several studies have shown that the NSGA-II is less effective for ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2024
2187 pages
Copyright © 2024 Copyright held by the owner/author(s).
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s).
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 August 2024
Check for updates
Author Tags
Qualifiers
- Abstract
Funding Sources
- Agence Nationale de la Recherche
- Guangdong Provincial Department of Science and Technology
- Science, Technology and Innovation Commission of Shenzhen Municipality
Conference
GECCO '24 Companion
Sponsor:
GECCO '24 Companion: Genetic and Evolutionary Computation Conference Companion
July 14 - 18, 2024
VIC, Melbourne, Australia
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 15Total Downloads
- Downloads (Last 12 months)15
- Downloads (Last 6 weeks)1
Reflects downloads up to 26 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in