Proven Runtime Guarantees for How the MOEA/D Computes the Pareto Front From the Subproblem Solutions

分解式多目标进化算法（MOEA/D）不直接优化给定的多目标函数$f$，而是以协同进化的方式优化$f$的$N+1$个单目标子问题。它维护所有非支配解的档案，并将其输出作为Pareto前沿的近似值。一旦MOEA/D找到所有子问题的最优解（$g$-optima），它仍可能错过$f$的Pareto最优解。然后，算法的任务是通过变异$g$-optima来直接找到剩余的Pareto最优解。在本研究中，我们首次分析了当$g$-optima是Pareto前沿的严格子集时，仅使用标准变异算子的MOEA/D如何计算OneMinMax基准测试的整个Pareto前沿。对于标准位变异，我们证明了期望运行时间为$O(n N \log n + n^{n/(2N)} N \log n)$函数评估。特别是对于第二个更有趣的阶段，当算法从所有$g$-optima开始时，我们证明了期望运行时间为$\Omega(n^{(1/2)(n/N + 1)} \sqrt{N} 2^{-n/N})$。如果$N=o(n)$，则此运行时间是超多项式的，因为这会在$g$-optima之间留下大的间隙，需要昂贵的变异来覆盖。对于指数为$\beta\in(1,2)$的幂律变异，我们证明了期望运行时间为$O\left(n N \log n + n^{\beta} \log n\right)$函数评估。$O\left(n^{\beta} \log n\right)$项来自于从所有$g$-optima开始的第二阶段，它与子问题数量$N$无关。这相对于标准位变异的下界导致了巨大的加速。总的来说，我们对幂律的整体界限表明，当$N=O(n^{\beta - 1})$时，MOEA/D的表现最佳，导致$O(n^\beta \log n)$的界限。与标准位变异不同，较小的$N$值对于幂律变异更好，因为它能够轻松地创建缺失的解。

研究MOEA/D算法在求解多目标优化问题时可能会错过Pareto最优解的情况，提出了使用标准位变异和幂律变异两种算子来解决该问题。

MOEA/D算法通过协同进化的方式优化多目标函数，维护非支配解集合作为Pareto最优解的近似。使用标准位变异和幂律变异两种算子来寻找可能被错过的Pareto最优解。

论文证明了使用标准位变异的MOEA/D算法在找到所有g-最优解后，寻找剩余的Pareto最优解的期望运行时间为O(nNlogn+n^(n/(2N))Nlogn)，其中N表示子问题的数量，n表示决策变量的数量。此外，论文还证明了使用幂律变异的MOEA/D算法的期望运行时间为O(nNlogn+n^βlogn)，其中β是幂律变异的指数。实验结果表明，幂律变异的MOEA/D算法相比标准位变异的算法具有更快的运行速度。

近期的相关研究主要集中在改进MOEA/D算法的性能和寻找更好的Pareto最优解。例如，一些研究关注如何通过改进算法的权重向量来提高算法的性能。另外，也有研究着眼于如何处理多峰问题和不确定性问题。相关论文包括《A New Weighted Aggregation Approach for Evolutionary Multiobjective Optimization》和《Robust Multiobjective Optimization Using Evolutionary Algorithms》等。