Runtime Analysis of Typical Decomposition Approaches in MOEA/D for Many-Objective Optimization Problems
分析了基于加权和、切比雪夫和惩罚边界交叉三种分解方法的MOEA/D算法在两类多目标基准问题上的期望运行时间，发现加权和能在多项式时间内找到所有子问题的最优解，而其他两种方法在某些子问题上需要指数时间。
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.