Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives

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).

Accepted for publication in "IEEE Transactions on Evolutionary Computation"

References in corpus (7)

• A Review of Evolutionary Multi-modal Multi-objective Optimization
• Mathematical Runtime Analysis for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)
• A First Runtime Analysis of the NSGA-II on a Multimodal Problem
• A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)
• Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossover
• The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem
• Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives

Cited by in corpus (4)

• Runtime Analysis of the SMS-EMOA for Many-Objective Optimization
• Approximation Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)
• Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms
• Illustrating the Efficiency of Popular Evolutionary Multi-Objective Algorithms Using Runtime Analysis