Non-Dominated Solution

A solution is non-dominated if no other solution in the set is at least as good in all objectives and strictly better in at least one objective. This binary relation, called Pareto dominance, is the fundamental criterion for filtering suboptimal candidates.

• Example: For a car design minimizing cost and maximizing safety, Solution A ($20k, 4-star) is dominated by Solution B ($18k, 5-star) because B is better in both objectives. Solution A ($20k, 5-star) and Solution C ($18k, 4-star) are likely non-dominated relative to each other.

The collection of all non-dominated solutions in the decision space (the space of input parameters) is called the Pareto set. When these solutions are plotted according to their objective function values, they form the Pareto front (or trade-off surface) in the objective space.

• This set represents the best possible compromises; improving one objective inevitably worsens another.
• Algorithms like NSGA-II and MOEA/D are explicitly designed to discover and approximate this set.

A key property is that for any non-dominated solution, there exists at least one set of positive weights for which that solution is optimal under the weighted sum method of scalarization. However, the converse is not always true for non-convex Pareto fronts.

• This makes non-dominated solutions the primary targets for preference articulation, where a decision-maker's weights or goals are applied after the Pareto set is found to select a final solution.

In Multi-Objective Evolutionary Algorithms (MOEAs), identifying and preserving non-dominated solutions is central. Algorithms perform non-dominated sorting to rank the population.

• First Front: Contains all currently non-dominated solutions.
• Crowding Distance: Used within a front to promote diversity, favoring solutions in less crowded regions of the objective space.
• Archive: Often used to store the best non-dominated solutions found throughout the run, ensuring elitism.

The quality of a set of non-dominated solutions is measured using Pareto-compliant indicators. These metrics respect the dominance relation.

• Hypervolume Indicator: Measures the volume of objective space dominated by the solution set relative to a reference point. A larger hypervolume indicates a better approximation of the Pareto front.
• Other metrics, like generational distance, measure convergence to the true Pareto front.

In single-objective optimization, there is typically a single global optimum (or several with equal value). In multi-objective problems, there is usually a set of non-dominated solutions (the Pareto set).

• The ideal point (the vector of individual objective optima) is often unattainable.
• The final choice from the non-dominated set requires multi-criteria decision making (MCDM), incorporating human preference, business rules, or risk tolerance to select a single implementable solution.

Pareto dominance is the fundamental binary relation that defines a non-dominated solution. A solution X dominates another solution Y if it is at least as good as Y in all objectives and strictly better in at least one objective. A solution is non-dominated if no other solution in the considered set Pareto-dominates it. This relation is the core mechanism for comparing solutions in a multi-objective space.

The Pareto front (or Pareto frontier) is the set of all Pareto optimal solutions plotted in the objective space. It represents the complete spectrum of optimal trade-offs between competing goals. A non-dominated solution from the decision space maps directly to a point on this front. Visualizing the front helps decision-makers understand the inherent compromises, such as the trade-off between a model's accuracy and its inference latency.

Pareto optimality describes the state of a solution that cannot be improved in any objective without degrading another. A Pareto optimal solution is globally non-dominated with respect to the entire feasible search space. In practice, algorithms aim to approximate the Pareto set (in decision space) and the Pareto front (in objective space). This concept is central to economics and engineering, defining an efficient allocation of resources.

A Multi-Objective Evolutionary Algorithm (MOEA) is a population-based metaheuristic designed to find a diverse approximation of the Pareto front. Unlike single-objective optimizers, MOEAs use Pareto dominance for selection. Key strategies include:

• Non-dominated sorting to rank solutions.
• Density estimation (e.g., crowding distance) to preserve spread.
• Maintaining an archive of best-found non-dominated solutions. Examples include NSGA-II and MOEA/D.

Scalarization is a technique to transform a multi-objective problem into a single-objective one, creating a scalar objective function. Common methods include:

• Weighted Sum Method: Aggregates objectives into a sum, f_scalar = w1*f1 + w2*f2.
• Epsilon-Constraint Method: Optimizes one primary objective while constraining others. While effective, a key limitation is that a single scalarization can only find one point on the Pareto front per run, requiring multiple runs with different weights to map the front.

The Hypervolume Indicator (or S-metric) is a Pareto-compliant performance metric that quantifies the quality of a set of non-dominated solutions. It measures the volume of the objective space dominated by the solution set relative to a predefined reference point. A larger hypervolume indicates a set that is both closer to the true Pareto front (convergence) and more spread out (diversity). It is a gold standard for benchmarking MOEAs.