MOEA/D with uniformly randomly adaptive weights

Lucas R. C. de Farias, Pedro H. M. Braga, Hansenclever de F. Bassani, Aluízio F. R. Araújo

TL;DR

This paper introduces MOEA/D-URAW, a novel multi-objective optimization algorithm that dynamically adapts its weight vectors to the problem's Pareto front shape. This adaptation allows for a flexible population size, crucial for many-objective problems, and leads to improved solution quality compared to existing methods on various benchmark problems.

What Problem Does This Paper Address?

Multi-objective optimization problems (MOOPs) involve finding solutions that simultaneously optimize multiple, often conflicting, objectives. Decomposition-based evolutionary multi-objective optimization (EMO) algorithms, like MOEA/D, tackle this by breaking down the complex multi-objective problem into a set of simpler single-objective subproblems, each guided by a weight vector. A common approach is to use uniformly distributed weights, which works well for simple Pareto front shapes. However, this method faces two significant challenges:

  1. Problem Geometry Sensitivity: Uniform weights can fail to produce well-distributed solutions when the Pareto front has complex geometries (e.g., disconnected, degenerate, or inverted shapes).
  2. Inflexible Population Size: As the number of objectives increases (many-objective optimization problems or MaOPs), the number of required weight vectors grows, leading to a non-linear increase in computational cost and making population size inflexible.

This paper aims to address these limitations by proposing a method that adapts weights during the evolutionary process, allowing for better handling of diverse Pareto front shapes and a flexible population size.

Methods

The proposed algorithm, MOEA/D-URAW, builds upon the MOEA/D framework. Its key innovations lie in:

  • Uniformly Randomly Adaptive Weights (URAW): Instead of fixed weights, MOEA/D-URAW uses a dynamic approach. It starts with weights generated by the Uniformly Randomly (UR) method, which offers flexibility in population size.
  • Sparsity-Based Weight Adaptation: The core of the adaptation mechanism is based on the "sparsity level" of individuals in the population. This level is calculated using the Euclidean distance to an individual's nearest neighbors.
  • Subproblem Removal: Individuals with a low sparsity level (i.e., overcrowded areas of the Pareto front) are identified, and their corresponding subproblems are removed. This process is repeated until a certain threshold is met.
  • Subproblem Addition: The algorithm also monitors an external population (EP) of non-dominated solutions. Individuals in the EP with the highest sparsity levels are used to generate new subproblems. The weight vector for these new subproblems is derived from the objective values of these high-sparsity individuals, effectively adapting to the shape of the Pareto front.
  • Flexible Population Size: By dynamically adding and removing subproblems, the algorithm can maintain a manageable population size, even when dealing with a large number of objectives.

The algorithm's framework is presented in Algorithm 1, detailing the initialization, evolutionary loop, and the adaptation steps that occur during specific generation intervals (e.g., between 5% and 90% of total generations).

Datasets

The paper evaluates MOEA/D-URAW on a suite of eight modified WFG4 test problems (WFG41 to WFG48). These problems are specifically chosen because they exhibit diverse Pareto front characteristics, including:

  • Continuous and discontinuous fronts
  • Convex, concave, strong convex, strong concave, and mixed shapes

The experiments were conducted for 2 to 6 objectives, covering both multi-objective optimization problems (MOOPs) and many-objective optimization problems (MaOPs). The authors note that the population size was set to ensure a fair comparison with other algorithms, as some methods (like Das and Dennis) do not inherently provide a flexible population size for MaOPs.

Key Insights and Ideas

  • Adaptive Weights are Crucial for Complex Fronts: The results strongly suggest that dynamically adapting weights based on population sparsity is more effective than using fixed, uniformly distributed weights, especially for problems with non-trivial Pareto front geometries.
  • Sparsity as a Proxy for Pareto Front Shape: The paper demonstrates that the concept of "sparsity" can be a useful indicator of where the Pareto front is dense or sparse, allowing the algorithm to focus its search efforts more effectively.
  • Balancing Exploration and Exploitation: By removing overcrowded subproblems and adding new ones based on sparse regions, MOEA/D-URAW implicitly balances exploring new areas of the objective space and exploiting promising regions.
  • Flexibility for Many-Objective Problems: The ability to adapt the number of subproblems directly translates to a flexible population size, a significant advantage for MaOPs where fixed population sizes can become computationally prohibitive.

Key Results

The performance of MOEA/D-URAW was compared against three variants of MOEA/D using fixed weight generation methods: Das and Dennis (DD), Uniformly Randomly (UR), and Tchebycheff Scalarizing Function (TSF).

  • Overall Performance: MOEA/D-URAW achieved better or equal results in 77.5% of the evaluated problems across 2 to 6 objectives.
  • MOOPs (2-3 Objectives): The algorithm performed best on most instances, with only a few exceptions where TSF or DD yielded better results (e.g., WFG47 for 2 objectives, WFG43 for 3 objectives).
  • MaOPs (4-6 Objectives): MOEA/D-URAW continued to show strong performance, outperforming other methods in most cases.
  • Specific Problem Challenges: The paper highlights that WFG43 and WFG44 (with strong concave and convex shapes, respectively) presented challenges for MOEA/D-URAW, where DD and UR sometimes performed better. WFG47 also showed an unexpected result for 2 objectives.
  • Visualizations: Figures 1 and 2 show that the final solution sets generated by MOEA/D-URAW are often more evenly distributed, visually confirming the effectiveness of the adaptive weight strategy.

Limitations and Future Work

  • Sensitivity to PF Shape: The authors acknowledge that the sparsity-based adaptation might not be optimal for all PF shapes, particularly those with strong concave or convex formats. This is identified as a key area for future investigation.
  • WFG47 Anomaly: The unexpected performance on WFG47 for 2 objectives is noted as a point for further research.
  • Adaptation Frequency: There is no universal consensus on the optimal frequency for weight adaptation. The paper suggests that investigating the impact of different adaptation frequencies on the algorithm's performance is a promising direction for future work.
  • Other Algorithms: While the paper compares MOEA/D-URAW to other MOEA/D variants, future work could explore its performance against other state-of-the-art multi-objective optimization algorithms.

Summary updated

Abstract

When working with decomposition-based algorithms, an appropriate set of weights might improve quality of the final solution. A set of uniformly distributed weights usually leads to well-distributed solutions on a Pareto front. However, there are two main difficulties with this approach. Firstly, it may fail depending on the problem geometry. Secondly, the population size becomes not flexible as the number of objectives increases. In this paper, we propose the MOEA/D with Uniformly Randomly Adaptive Weights (MOEA/DURAW) which uses the Uniformly Randomly method as an approach to subproblems generation, allowing a flexible population size even when working with many objective problems. During the evolutionary process, MOEA/D-URAW adds and removes subproblems as a function of the sparsity level of the population. Moreover, instead of requiring assumptions about the Pareto front shape, our method adapts its weights to the shape of the problem during the evolutionary process. Experimental results using WFG41-48 problem classes, with different Pareto front shapes, shows that the present method presents better or equal results in 77.5% of the problems evaluated from 2 to 6 objectives when compared with state-of-the-art methods in the literature.
BibTeX
@inproceedings{farias2018moea,
  author = {Lucas R. C. de Farias and Pedro H. M. Braga and Hansenclever de F. Bassani and Aluízio F. R. Araújo},
  title = {{MOEA/D with uniformly randomly adaptive weights}},
  booktitle = {GECCO},
  year = {2018},
  doi = {10.1145/3205455.3205648},
}
Figure