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

Abstract Decomposition-based multi-objective evolutionary algorithms (MOEAs) are popular methods utilized to address many-objective optimization problems (MaOPs). These algorithms decompose the original MaOP into several scalar optimization subproblems, and solve them to obtain a set of solutions to approximate the Pareto front (PF). The decomposition approach is an important component in them. This paper presents a runtime analysis of a MOEA based on the classic decomposition framework using the typical weighted sum (WS), Tchebycheff (TCH), and penalty-based boundary intersection (PBI) approaches to obtain an optimal solution for any subproblem of two pseudo-Boolean benchmark MaOPs, namely mLOTZ and mCOCZ. Due to the complexity and limitation of the theoretical analysis techniques, the analyzed algorithm employs one-bit mutation to generate offspring individuals. The results indicate that when using WS, the analyzed algorithm can consistently find an optimal solution for every subproblem, which is located in the PF, in polynomial expected runtime. In contrast, the algorithm requires at least exponential expected runtime (with respect to the number of objectives m) for certain subproblems when using TCH or PBI, even though the landscapes of all objective functions in the two benchmarks are strictly monotone. Moreover, this analysis reveals a drawback of using WS: the optimal solutions obtained by solving subproblems are more easily mapped to the same point in the PF, compared to the case of using TCH. When using PBI, a smaller value of the penalty parameter is a good choice for faster convergence to the PF but may compromise diversity. To further understand the impact of these approaches in practical algorithms, numerical experiments on using bit-wise mutation to generate offspring individuals are conducted. The findings of this study may be helpful for designing more efficient decomposition approaches for MOEAs in future research.