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

Abstract

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 log2 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. This paper summarizes the work Danyang Zhang, Zerong Zhong, Weijie Zheng, and Benjamin Doerr. 2026. Superior Runtime Guarantees for the MOEA/D Multi-Objective Optimizer via Weighted-Sum Decomposition. In AAAI Conference on Artificial Intelligence, AAAI 2026. AAAI Press, 37187–37194 [14].