On the Convergence of Typical Decomposition Approaches in MOEA/D for Many-objective Optimization Problems

Decomposition approach is an important strategy in multi-objective evolutionary algorithm based on decomposition (MOEA/D), which is a popular method for handing many-objective optimization problems (MaOPs). This paper presents a theoretical analysis on the convergence ability of using the typical weighted sum (WS), Tchebycheff (TCH) or penalty-based boundary intersection (PBI) approach in a basic MOEA/D for solving two benchmark MaOPs. The results show that using WS is the most efficient case, and the algorithm can find an optimal solution for any subproblem in polynomial expected runtime. In contrast, the algorithm needs at least exponential expected runtime for some subproblems if using TCH or PBI. Meanwhile, our analyses reveal an obvious shortcoming of using WS, i.e., the optimal solutions of different subproblems are easily corresponding to the same solution. Moreover, this analysis suggests that if using PBI, a small value of the penalty parameter is a good choice for faster converging to the Pareto front. This study reveals some optimization behaviors of using the three typical decomposition approaches in the well-known MOEA/D framework.