Non-Dominated Sorting Genetic Algorithm (NSGA-II)

This is the primary ranking mechanism. The algorithm sorts the entire population into successive Pareto fronts (or non-domination ranks).

• Front 1: Contains all solutions not dominated by any other in the population.
• Front 2: Contains solutions dominated only by those in Front 1.
• This process continues until all solutions are ranked. Selection for the next generation prioritizes solutions from better (lower-numbered) fronts, ensuring steady convergence toward the Pareto optimal set.

A density estimation metric used to preserve diversity within a Pareto front. For each front, the algorithm:

1. Sorts solutions based on each objective value.
2. Calculates a crowding distance for each solution as the average side-length of the cuboid formed by its nearest neighbors in the objective space.
3. Solutions at the extremes (with infinite distance) are always preserved. When selecting solutions from the same front, those with a larger crowding distance (i.e., in less crowded regions) are preferred, preventing convergence to a single region of the Pareto front.

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.

The Pareto front is the set of all Pareto optimal solutions plotted in the objective space. It represents the optimal trade-off surface where improving one objective inevitably worsens another. In NSGA-II, the algorithm's goal is to converge its population towards this front.

• Visualization: A curve (for two objectives) or a surface (for three) defining the boundary of achievable performance.
• Decision Support: Provides the complete set of best-possible compromises for a human decision-maker.

Pareto dominance is the fundamental comparison relation in multi-objective optimization. A solution A dominates a solution B if:

• A is at least as good as B in all objectives.
• A is strictly better than B in at least one objective.

NSGA-II uses this relation in its non-dominated sorting procedure to rank the population into successive fronts of non-dominated solutions (Front 1, Front 2, etc.).

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.