Runtime Analysis of Typical Decomposition Approaches in MOEA/D for Many-Objective Optimization Problems.

Area of Science:

• Optimization algorithms
• Computational complexity
• Evolutionary computation

Background:

• Decomposition-based multi-objective evolutionary algorithms (MOEAs) are key for many-objective optimization problems (MaOPs).
• These algorithms decompose MaOPs into scalar subproblems to approximate the Pareto front (PF).
• The decomposition approach significantly impacts algorithm performance.

Purpose of the Study:

• To analyze the runtime complexity of a MOEA using weighted sum (WS), Tchebycheff (TCH), and penalty-based boundary intersection (PBI) decomposition methods.
• To evaluate these methods on pseudo-Boolean benchmark MaOPs (mLOTZ, mCOCZ).
• To understand the trade-offs between decomposition approaches regarding convergence and diversity.

Main Methods:

• Theoretical runtime analysis of a MOEA employing one-bit mutation for subproblem optimization.
• Analysis focused on two benchmark MaOPs: mLOTZ and mCOCZ.
• Numerical experiments using bit-wise mutation to validate theoretical findings.

Main Results:

• The WS approach achieves polynomial expected runtime for finding optimal subproblem solutions on the tested benchmarks.
• TCH and PBI methods require at least exponential expected runtime, even for strictly monotone objective functions.
• WS can lead to solutions converging to a single point on the PF, potentially reducing diversity compared to TCH.
• PBI parameter choice impacts convergence speed and diversity.

Conclusions:

• WS offers a computationally efficient decomposition strategy for certain MaOPs.
• TCH and PBI exhibit higher computational complexity for the analyzed problems.
• The choice of decomposition method critically influences the performance and characteristics of MOEAs.
• Findings guide the design of more efficient decomposition approaches for MOEAs.