Empirical Investigations of Reference Point Based Methods When Facing a Massively Large Number of Objectives: First Results

Ke Li, Kalyanmoy Deb, Okkes Tolga Altinöz, Xin YaoEMO 2017 · DOI

TL;DR

This paper investigates the performance of reference point-based evolutionary multi-objective optimization (EMO) algorithms when dealing with problems that have a "massively large" number of objectives (25-100). The study finds that R-NSGA-II, a specific reference point-based method, demonstrates robust performance, suggesting that appropriate distance measures and population diversity are crucial for tackling such high-dimensional optimization challenges.

What Problem Does This Paper Address?

Multi-objective optimization problems (MOPs) involve finding solutions that simultaneously optimize multiple, often conflicting, objectives. While traditional EMO algorithms have been successful for problems with two or three objectives, they often struggle with "many-objective optimization problems" (MaOPs) that have four or more objectives. This is largely due to the "curse of dimensionality," where standard Pareto dominance-based algorithms like NSGA-II experience a severe performance degradation.

While various strategies have been proposed to address MaOPs, most existing studies have been limited to experiments with up to 15-20 objectives. This paper aims to bridge this gap by empirically investigating the behavior of reference point-based EMO methods when faced with a significantly larger number of objectives (25, 50, 75, and 100). The core challenge is to understand how these methods, which use predefined weight vectors to guide the search, perform and scale in such high-dimensional objective spaces.

Methods

The study focuses on three reference point-based EMO algorithms:

  • MOEA/D (Multi-Objective Evolutionary Algorithm based on Decomposition): This method decomposes the MOP into several subproblems, each optimized collaboratively. It uses a penalty-based boundary intersection (PBI) function as its scalarizing function.
  • NSGA-III (Non-dominated Sorting Genetic Algorithm III): This algorithm defines subproblems to achieve local optima in terms of convergence and diversity, associating solutions with their closest weight vectors. It uses a niching process based on perpendicular distance.
  • R-NSGA-II (Reference point-based NSGA-II): This algorithm was originally designed to approximate a region of interest (ROI) rather than the entire Pareto front (PF). It uses aspiration level vectors (akin to weight vectors) and incorporates a direct Euclidean distance as a secondary selection criterion alongside Pareto dominance.

The researchers also propose a novel two-layer weight vector generation method to address the impracticality of generating a uniform distribution of weight vectors in high-dimensional spaces. This method involves a coordinate transformation to shrink the weight vectors in inner layers, with a non-linear shrinkage factor setting derived from Proposition 1 for DTLZ2-DTLZ4 problems.

Performance is evaluated using two metrics:

  • Convergence Measure (CM): Measures how close the obtained solutions are to the ideal objective values.
  • Inverted Generational Distance (IGD): Assesses both convergence and diversity by measuring the distance between the obtained solution set and a set of uniformly sampled points on the true Pareto front.

Datasets

The experiments were conducted using the widely used DTLZ suite of benchmark problems, specifically DTLZ1, DTLZ2, DTLZ3, and DTLZ4. For each problem, the researchers tested scenarios with 25, 50, 75, and 100 objectives. The number of decision variables was set according to the standard for these problems (m+4 for DTLZ1, m+9 for DTLZ2-DTLZ4, where 'm' is the number of objectives). No new benchmarks were introduced.

Key Insights and Ideas

  • R-NSGA-II Shines in High Dimensions: Surprisingly, R-NSGA-II, which was initially proposed for approximating specific regions of interest, demonstrated the most competitive and robust performance across all tested benchmark problems and objective numbers. This suggests its underlying mechanisms are well-suited for massively many-objective scenarios.
  • Distance Measure Matters: The study highlights that the choice of distance measure is critical for reference point-based methods. R-NSGA-II's use of direct Euclidean distance, in addition to Pareto dominance, appears to be a key factor in its success, outperforming methods that rely solely on perpendicular distance.
  • Diversity is Paramount: The paper emphasizes that maintaining sufficient population diversity is crucial. R-NSGA-II's ability to accommodate multiple solutions per weight vector (or aspiration level) likely contributes to better diversity and selection pressure.
  • MOEA/D and NSGA-III Struggle with Diversity: While MOEA/D showed decent convergence (CM), its diversity (IGD) suffered significantly with increasing objectives. The solutions tended to crowd in narrow regions, failing to approximate the entire Pareto front. NSGA-III also showed a significant performance degradation, particularly in convergence on multi-modal problems.
  • Weight Vector Generation is Challenging: The paper acknowledges the difficulty of generating a uniform distribution of weight vectors in high-dimensional spaces and proposes a two-layer method with non-linear shrinkage factors to improve sample distribution.

Key Results

  • R-NSGA-II Superiority: R-NSGA-II consistently achieved the best IGD metric values across all DTLZ problems and objective counts, indicating superior convergence and diversity.
  • DTLZ1 and DTLZ3 Challenges: For DTLZ1 and DTLZ3 (which have multi-modal properties), NSGA-III's performance deteriorated significantly, struggling to drive solutions to the PF.
  • MOEA/D's Convergence vs. Diversity Trade-off: MOEA/D showed good CM values but poor IGD values, suggesting it converges but lacks diversity in high dimensions.
  • Classical Generative Method Comparison: When compared to a classical generative method (which solves parameterized single-objective problems), R-NSGA-II generally performed better, especially as the number of objectives increased, though the classical method showed promise on DTLZ2 for lower objective counts.

Limitations and Future Work

  • Limited Algorithm Scope: The study primarily focuses on reference point-based EMO methods. Future research should investigate other types of EMO algorithms, such as Pareto- and indicator-based methods, to provide a more comprehensive understanding.
  • Benchmark Simplicity: The benchmark problems used (DTLZ suite) are considered relatively less challenging. Future work should test performance on a wider range of more complex benchmark problems.
  • Parameter Sensitivity: The paper suggests that statistically guided parameter studies are needed to determine optimal parameterizations for different EMO algorithms in high-dimensional settings.
  • Computational Feasibility: The authors note that the computational overhead of metrics like hypervolume can become infeasible for massively many-objective problems, suggesting a need for scalable metric approaches.

Summary updated

BibTeX
@inproceedings{li2017empirical,
  author = {Ke Li and Kalyanmoy Deb and Okkes Tolga Altinöz and Xin Yao},
  title = {{Empirical Investigations of Reference Point Based Methods When Facing a Massively Large Number of Objectives: First Results}},
  booktitle = {EMO},
  year = {2017},
  doi = {10.1007/978-3-319-54157-0\_27},
}
Figure