A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)
Simon Wietheger, Benjamin Doerr
2024Proceedings of the Genetic and Evolutionary Computation Conference Companion12 citationsDOIOpen Access PDF
Abstract
The Non-dominated Sorting Genetic Algorithm II (NSGA-II) is the most prominent multi-objective evolutionary algorithm for real-world applications. While it performs evidently well on bi-objective optimization problems, empirical studies suggest that it is less effective when applied to problems with more than two objectives. A recent mathematical runtime analysis confirmed this observation by proving that the NGSA-II for an exponential number of iterations misses a constant factor of the Pareto front of the simple m-objective OneMinMax problem when m ≥ 3.
Topics & Concepts
SortingBenchmark (surveying)Multi-objective optimizationPareto principleAlgorithmGenetic algorithmMathematical optimizationComputer scienceConstant (computer programming)PopulationEvolutionary algorithmExponential functionMathematicsGeodesyGeographyProgramming languageDemographyMathematical analysisSociologyAdvanced Multi-Objective Optimization AlgorithmsMetaheuristic Optimization Algorithms ResearchEvolutionary Algorithms and Applications