Non-Dominated Sorting Genetic Algorithm (NSGA-II)

NSGA-II employs a steady-state selection mechanism that explicitly preserves elite solutions. The process for each generation is:

• Combine the parent population (size N) and offspring population (size N) to form a combined population of size 2N.
• Perform non-dominated sorting on the combined 2N population.
• Fill the new parent population by adding entire fronts, starting from the best (Front 1).
• If adding a full front would exceed population size N, solutions within that front are selected based on their crowding distance (higher is better). This guarantees that the best non-dominated solutions found are never lost.

A key engineering improvement over its predecessor (NSGA) is a fast, O(MN²) non-dominated sorting procedure, where M is the number of objectives and N is the population size. This is achieved by:

• For each solution, maintaining a count of how many solutions dominate it (domination count) and a list of solutions it dominates.
• Using this data structure to identify and remove Front 1 members in one pass, then updating counts to identify Front 2, and so on. This efficient implementation made NSGA-II practical for real-world problems with larger populations and more objectives.

Unlike many contemporary algorithms, NSGA-II does not require a niche parameter (or sharing parameter) to maintain diversity. Diversity emerges naturally from the interplay of:

• Non-dominated sorting, which spreads solutions across fronts.
• Crowding distance comparison, which promotes spread within a front. This eliminates a sensitive user-defined parameter, making the algorithm more robust and easier to apply out-of-the-box to new optimization problems.

NSGA-II incorporates a simple yet effective method for constrained optimization problems. It uses a constrained-domination principle:

• A solution i is said to constrained-dominate solution j if:
  1. Solution i is feasible and solution j is infeasible, OR
  2. Both are infeasible, but i has a smaller overall constraint violation, OR
  3. Both are feasible, and i dominates j in the usual Pareto sense. This principle pushes the population toward feasibility first, and then toward optimality, without requiring penalty functions.

Crowding distance is a density estimation metric used within NSGA-II to maintain diversity along the Pareto front. After non-dominated sorting, solutions on the same front are compared based on their crowding distance.

• Calculation: Measures the average side-length of the cuboid formed by a solution's nearest neighbors in objective space.
• Selection: When trimming a front to fit the population size, solutions with a larger crowding distance (i.e., in less crowded regions) are preferentially kept, preventing convergence to a single region of the front.

A Multi-Objective Evolutionary Algorithm (MOEA) is a population-based metaheuristic optimization framework designed to solve problems with multiple objectives. NSGA-II is a prominent elitist MOEA. Key characteristics include:

• Population-Based: Maintains a set of candidate solutions.
• Stochastic Operators: Uses selection, crossover, and mutation to explore the search space.
• Pareto-Based Selection: Fitness is based on Pareto dominance and diversity, not a single scalar value.
• Goal: To approximate the true Pareto front with a diverse and well-distributed set of solutions.

Scalarization is an alternative approach to multi-objective optimization that transforms the vector of objectives into a single scalar objective function. Common methods include the Weighted Sum Method and the Epsilon-Constraint Method.

• Contrast with NSGA-II: While scalarization reduces the problem to a single-objective one (solvable with standard optimizers), it requires pre-defining weights or constraints. NSGA-II finds the entire Pareto front in a single run, presenting the full set of trade-offs.

The Hypervolume Indicator (or S-metric) is a Pareto-compliant performance metric used to evaluate the quality of a set of non-dominated solutions. It measures the volume of the objective space dominated by the solution set, bounded by a predefined reference point.

• Use in Evaluation: A larger hypervolume indicates a set that is both closer to the true Pareto front and more diverse.
• Algorithm Comparison: Often used to benchmark the performance of MOEAs like NSGA-II against other algorithms.