Understanding the Co-evolutionary Solution Exchange of the MOEA/D: Already the Smallest Communication Radius Gives the Best-Possible Speed-Up

概要

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)$.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
Understanding the Co-evolutionary Solution Exchange of the MOEA/D: Already the Smallest Communication Radius Gives the Best-Possible Speed-Up

# 概要
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…

# 原典
https://arxiv.org/abs/2610.35373

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。