Small solution sharing boosts multi-objective optimization speed
Understanding the Co-evolutionary Solution Exchange of the MOEA/D: Already the Smallest Communication Radius Gives the Best-Possible Speed-Up
Neural and Evolutionary Computing
Summary
Multi-objective optimization tries to find the best trade-offs between different goals at once. A popular method, MOEA/D, breaks these problems into smaller ones and solves them together. The authors studied how sharing solutions between these smaller problems helps speed up the process. They found that even sharing solutions on a very small scale speeds up finding good solutions significantly compared to sharing nothing.
What this means in practice
- •For optimization engineers: Design more efficient multi-objective optimization software by incorporating minimal solution exchanges to reduce computation time.
- •For machine learning modelers: Improve hyperparameter tuning processes with faster multi-objective search by using co-evolutionary algorithms with small communication radii between subproblems.
A theory result. No direct application yet.
Authors
Benjamin Doerr, Moaad Elmoutassim, Martin S. Krejca, Guy Mushiata Kibulu
Abstract
Besides domination-based algorithms such as the NSGA-II, the decomposition-based MOEA/D is one of the most popular and successful optimization heuristic for multi-objective problems. It decomposes the problem into several, single-objective subproblems. By solving these in a co-evolutionary manner and archiving non-dominated solutions, it approximates or computes the Pareto front. Interestingly, so far no advantages from the co-evolutionary communication of subproblem solutions were proven. In this first mathematical runtime analysis addressing this research question, we investigate how the mutation-based MOEA/D solves the classic OneMinMax benchmark when solutions are exchanged among subproblems in different distances $r$. We show, for the first time, that the MOEA/D profits from an exchange of solutions, and that already very small communication radii $r$ are sufficient to maximally profit from this feature of the algorithm. More precisely, for all values $r \ge 1$ we prove a tight runtime guarantee of $Θ(n^2)$, where $n$ is the problem size. This is asymptotically faster than the known bound of $O(n^2 \log n)$ guarantee for $r=0$, which we complement with a matching bound of $Ω(n^2 \log n)$.