Superior Runtime Guarantees for the MOEA/D Multi-Objective Optimizer via Weighted-Sum Decomposition

The MOEA/D is the most popular decomposition-based evolutionary algorithm to solve multi-objective optimization problems. However, among the two common decomposition approaches, weighted-sum and Tchebycheff, the existing theoretical research almost exclusively focuses on the latter one. In this first complete mathematical runtime analysis for the MOEA/D using the original weighted-sum decomposition, we show that this variant of the algorithm solves the classic ONEMINMAX benchmark considerably faster than both the MOEA/D with Tchebycheff decomposition and many other classic algorithms such as the NSGA-II, NSGA-III, SMS-EMOA, and SPEA2. More precisely, we show that already a logarithmic number of subproblems suffices for the algorithm to be efficient, and then typically O(n log² n) function evaluations suffice to compute the full Pareto front. This beats the other algorithms by a factor of Θ(n/ log n). For a second benchmark, the ONEJUMPZEROJUMP problem, we show a speed-up by a factor of Θ(n). Overall, this work shows that a further development of the weighted-sum approach might be fruitful.