MOEA/D (Multi-Objective EA Based on Decomposition)

MOEA/D maintains a diverse approximation of the Pareto front through a predefined, uniformly distributed set of weight vectors. These vectors are generated at initialization (e.g., using Das and Dennis's systematic approach) and remain fixed throughout the run.

• Each weight vector corresponds to a unique search direction and an associated solution in the population.
• The uniform spread of weight vectors across the simplex inherently encourages a uniform spread of solutions along the Pareto front.
• This method provides a more systematic and stable approach to diversity maintenance compared to density estimators like crowding distance, which can be less effective in high-dimensional objective spaces.

While each subproblem maintains a current solution, MOEA/D typically employs an external archive (or elite population) to store all non-dominated solutions discovered during the search.

• After each generation, newly generated offspring are checked for Pareto dominance against the current archive.
• Non-dominated offspring are added, and any archive members they dominate are removed.
• This archive provides the final output of the algorithm: a set of Pareto optimal or near-optimal trade-off solutions.
• The archive also helps prevent the loss of good solutions that might be replaced in their specific subproblem during the update step.

A key step in MOEA/D is the update of neighboring solutions. After creating a new offspring solution y for a subproblem i, y is evaluated not just against subproblem i's current solution, but against the current solutions of all subproblems within i's neighborhood.

• If y yields a better scalarized value (for that subproblem's specific weight vector and aggregation function) than the current holder, it replaces that solution.
• This allows a single good solution to propagate through and improve multiple neighboring subproblems simultaneously.
• This greedy replacement strategy drives rapid convergence but requires careful scalarization function design to ensure improvements align with Pareto optimality.

MOEA/D offers distinct advantages compared to Pareto dominance-based algorithms like NSGA-II, particularly for problems with many objectives (MaOPs).

• Scalability: By decomposing the problem, MOEA/D's selection pressure is based on scalar values, avoiding the severe loss of selection pressure (dominance resistance) that plagues Pareto-based methods in high-dimensional objective spaces.
• Computational Efficiency: The neighborhood-based reproduction and update often have lower complexity per generation than the non-dominated sorting used in NSGA-II.
• Preference Integration: Decision-maker preferences (e.g., reference points, aspiration levels) can be naturally incorporated by adjusting the distribution of weight vectors, focusing computational effort on regions of interest.

Decomposition is MOEA/D's defining strategy. Instead of treating the problem as a whole, it breaks it down into N single-objective subproblems using different scalarization weight vectors (λ^1, λ^2, ..., λ^N).

Crucially, MOEA/D introduces a neighborhood concept. Each subproblem i has a set of neighboring subproblems (typically those with the closest weight vectors). The algorithm only allows information exchange (e.g., mating and replacement) between a subproblem and its neighbors.

• Benefits: This local interaction model promotes cooperative optimization, maintains diversity across the Pareto front, and significantly improves computational efficiency compared to global competition models used in algorithms like NSGA-II.

The set of weight vectors is a critical hyperparameter for MOEA/D. They determine the distribution of the subproblems and, consequently, the spread of solutions on the approximated Pareto front.

• Simplex-Lattice Design: A standard method for generating a set of evenly distributed weight vectors for M objectives. For a population size N and a parameter H, weights are generated from all combinations of non-negative integers that sum to H, then normalized. The number of vectors is N = C(H+M-1, M-1).
• Adaptation: Advanced versions of MOEA/D may adapt weight vectors during the search to focus on regions of interest or to improve the distribution of solutions, especially in problems with irregular Pareto front geometries.

MOEA/D is a specific instance within the broader class of Multi-Objective Evolutionary Algorithms (MOEAs). MOEAs are population-based metaheuristics inspired by biological evolution, designed to find a diverse set of Pareto optimal solutions.

Key contrasting MOEA paradigms:

• Dominance-Based MOEAs: Algorithms like NSGA-II and SPEA2 use Pareto dominance and density estimators (e.g., crowding distance) for selection and diversity maintenance.
• Decomposition-Based MOEAs: MOEA/D is the canonical example. It uses scalarization and a neighborhood structure.
• Indicator-Based MOEAs: Algorithms like IBEA use a performance indicator (e.g., the Hypervolume indicator) directly in the selection process.

MOEA/D is often favored for its efficiency and strong theoretical grounding in decomposition methods.

Reference points are crucial components in MOEA/D's scalarization functions, particularly the Tchebycheff approach.

• *Ideal Point (z)**: A vector where each component is the best achievable value for each individual objective (often estimated during the run). It serves as an anchor for measuring solution quality.
• Nadir Point: The vector of the worst objective values among Pareto optimal solutions. Used less frequently in basic MOEA/D but important for normalization.

These points connect to preference articulation. By adjusting weight vectors (λ) relative to a reference point, MOEA/D can be guided to search specific regions of the Pareto front that align with a decision-maker's utility function or goals, bridging optimization and Multi-Criteria Decision Making (MCDM).