A fast and elitist multiobjective genetic algorithm: NSGA-II¶
Why this mattered¶
NSGA-II mattered because it turned multiobjective evolutionary optimization from a promising but awkward research idea into a practical default method. Earlier non-dominated sorting approaches could approximate Pareto fronts, but they were slowed by high computational cost, lacked explicit elitism, and depended on a user-chosen sharing parameter to maintain diversity. Deb, Pratap, Agarwal, and Meyarivan’s key contribution was to make these three pieces work together: faster non-dominated sorting, elitist survival from the combined parent-offspring population, and crowding-distance diversity preservation without a niche-radius parameter. That combination made it feasible to search for a well-spread set of tradeoff solutions in a single run, rather than repeatedly tuning scalarized objectives or relying on fragile diversity heuristics.
The paradigm shift was methodological as much as algorithmic. NSGA-II helped establish the Pareto-front approximation itself as the central output of multiobjective optimization: not one “best” solution, but a structured set of alternatives exposing tradeoffs among competing objectives. Its elitist ranking-and-crowding scheme became a compact template that researchers and practitioners could implement, compare against, and extend. After the paper, NSGA-II became a standard benchmark and baseline across engineering design, scheduling, control, machine learning, operations research, and other domains where objectives conflict and closed-form optimization is impractical.
Subsequent breakthroughs in evolutionary multiobjective optimization often defined themselves in relation to NSGA-II: improving scalability to many objectives, replacing dominance with decomposition or indicator-based selection, hybridizing with local search or surrogate models, or adapting the framework to constrained, dynamic, and expensive black-box problems. Even when later algorithms outperformed it in specialized settings, NSGA-II remained influential because it supplied the field with a clear, reproducible architecture for elitist Pareto search. Its lasting importance is that it made multiobjective evolutionary optimization broadly usable and gave later work a common point of departure.
Abstract¶
Multi-objective evolutionary algorithms (MOEAs) that use non-dominated sorting and sharing have been criticized mainly for: (1) their O(MN/sup 3/) computational complexity (where M is the number of objectives and N is the population size); (2) their non-elitism approach; and (3) the need to specify a sharing parameter. In this paper, we suggest a non-dominated sorting-based MOEA, called NSGA-II (Non-dominated Sorting Genetic Algorithm II), which alleviates all of the above three difficulties. Specifically, a fast non-dominated sorting approach with O(MN/sup 2/) computational complexity is presented. Also, a selection operator is presented that creates a mating pool by combining the parent and offspring populations and selecting the best N solutions (with respect to fitness and spread). Simulation results on difficult test problems show that NSGA-II is able, for most problems, to find a much better spread of solutions and better convergence near the true Pareto-optimal front compared to the Pareto-archived evolution strategy and the strength-Pareto evolutionary algorithm - two other elitist MOEAs that pay special attention to creating a diverse Pareto-optimal front. Moreover, we modify the definition of dominance in order to solve constrained multi-objective problems efficiently. Simulation results of the constrained NSGA-II on a number of test problems, including a five-objective, seven-constraint nonlinear problem, are compared with another constrained multi-objective optimizer, and the much better performance of NSGA-II is observed.