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

MOEA/D's foundational mechanism is the decomposition of a multi-objective problem into N single-objective subproblems. This is achieved using scalarization functions, most commonly the Weighted Sum or Tchebycheff approach. Each subproblem is defined by a unique weight vector, directing the search towards a specific region of the Pareto front. For example, a weight vector of [0.9, 0.1] heavily prioritizes the first objective over the second.

• Weighted Sum Method: Aggregates objectives into a single sum, effective for convex Pareto fronts.
• Tchebycheff Approach: Minimizes the maximum weighted deviation from a reference point (like the ideal point), capable of finding solutions on non-convex regions of the Pareto front.
• Penalty-based Boundary Intersection (PBI): A more advanced method that balances convergence and diversity.

Instead of treating the population as a whole for selection, MOEA/D leverages a neighborhood structure for efficient local collaboration. Each subproblem (defined by its weight vector) is assigned a neighborhood of T other closely related subproblems based on the Euclidean distance between their weight vectors.

• When generating a new solution for a subproblem, genetic operators (crossover, mutation) are applied using information only from solutions within its neighborhood.
• This local mating restriction mimics fine-grained parallel optimization, reducing computational cost and promoting the production of solutions in specific, targeted regions of the objective space.
• The neighborhood size T is a critical algorithm parameter, balancing exploration (large T) and exploitation (small T).

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.

Scalarization is the core mathematical technique used by MOEA/D to decompose a multi-objective problem. It transforms a vector of objective values into a single scalar quantity, creating a set of single-objective subproblems.

• Weighted Sum Method: A basic scalarization where objectives are summed with assigned weights. MOEA/D often uses more advanced methods.
• Tchebycheff Approach: A popular scalarization in MOEA/D defined as max_i { λ_i * |f_i(x) - z_i*| }, where λ is a weight vector and z* is a reference point. It can find solutions on non-convex regions of the Pareto front.
• Penalty-Based Boundary Intersection (PBI): Another method used in MOEA/D that incorporates a penalty parameter to control convergence and diversity.

By solving these scalarized subproblems in parallel, MOEA/D collaboratively builds an approximation of the full Pareto optimal set.

Pareto dominance is the fundamental comparison relation in multi-objective optimization. A solution x1 dominates another solution x2 if:

• x1 is no worse than x2 in all objectives.
• x1 is strictly better than x2 in at least one objective.

A solution is Pareto optimal (or non-dominated) if no other feasible solution dominates it. The set of all Pareto optimal solutions forms the Pareto front in objective space.

MOEA/D does not directly use Pareto dominance for selection within each subproblem. Instead, it uses scalarization. However, an external archive is often maintained to store the globally best non-dominated solutions found during the search, ensuring the final output is a valid approximation of the true Pareto front.

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).