Hot off the Press: Proven Runtime Guarantees for How the MOEA/D Computes the Pareto Front From the Subproblem Solutions

The decomposition-based multi-objective evolutionary algorithm (MOEA/D) does not directly optimize a given multi-objective function f but instead optimizes N + 1 single-objective subproblems of f. We analyze for the first time how the MOEA/D with only standard mutation operators computes the whole Pareto front of the OneMinMax benchmark when the g-optima are a strict subset of the Pareto front. For standard bit mutation, we prove an expected runtime of O(nN logn + n^n/(2N)N logn) function evaluations. For the second phase, when the algorithm start with all g-optima, we prove an Ω(n^{(1/2) (n/N+1)√}N2⁻n/^N) expected runtime. For power-law mutation with exponent β ∈ (1, 2), we prove an expected runtime of O(nN logn + n^β logn) function evaluations. The O(n^β logn) term from the second phase is independent of the number of subproblems N, leading to a huge speedup over standard bit mutation. In general, our bound for power-law suggests that the MOEA/D performs best for N = O(n^β−1), resulting in an O(n^β logn) bound.