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 in a co-evolutionary manner. It maintains an archive of all non-dominated solutions found and outputs it as approximation to the Pareto front. Once the MOEA/D found all optima of the subproblems (the g-optima), it may still miss Pareto optima of f. The algorithm is then tasked to find the remaining Pareto optima directly by mutating the g-optima. In this work, 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(n N \log n + n^{n/(2N)} N \log n)\) function evaluations. Especially for the second, more interesting phase when the algorithm start with all g-optima, we prove an \(\varOmega (n^{(1/2)(n/N + 1)} \sqrt{N} 2^{-n/N})\) expected runtime. This runtime is super-polynomial if \(N = o(n)\) , since this leaves large gaps between the g-optima, which require costly mutations to cover. For power-law mutation with exponent \(\beta \in (1, 2)\) , we prove an expected runtime of \(O\left( n N \log n + n^{\beta } \log n\right) \) function evaluations. The \(O\left( n^{\beta } \log n\right) \) term stems from the second phase of starting with all g-optima, and it is independent of the number of subproblems N. This leads to a huge speedup compared to the lower bound for standard bit mutation. In general, our overall bound for power-law suggests that the MOEA/D performs best for \(N = O(n^{\beta - 1})\) , resulting in an \(O(n^\beta \log n)\) bound. In contrast to standard bit mutation, smaller values of N are better for power-law mutation, as it is capable of easily creating missing solutions.