A First Running Time Analysis of the Strength Pareto Evolutionary Algorithm 2 (SPEA2)

进化算法（EAs）已经成为解决多目标优化问题的主要方法。然而，多目标进化算法（MOEAs）的理论基础，特别是像运行时间分析这样的基本方面，仍然大多未被探索。现有的理论研究主要集中在基本的MOEAs上，对实际的MOEAs关注较少。本文首次对Strength Pareto evolutionary algorithm 2（SPEA2）进行了运行时间分析。具体而言，我们证明了SPEA2解决三个常用的多目标问题，即$m$OneMinMax、$m$LeadingOnesTrailingZeroes和$m$-OneJumpZeroJump的期望运行时间分别为$O(\mu n\cdot \min\{m\log n, n\})$，$O(\mu n^2)$和$O(\mu n^k \cdot \min\{mn, 3^{m/2}\})$。其中，$m$表示目标数，人口大小$\mu$至少需要分别为$(2n/m+1)^{m/2}$，$(2n/m+1)^{m-1}$和$(2n/m-2k+3)^{m/2}$。证明是通过一般定理完成的，这些定理也适用于分析其他MOEAs在这些问题上的期望运行时间，因此可以帮助未来对MOEAs进行理论分析。

多目标进化算法的运行时间分析

首次对SPEA2算法进行多目标问题的运行时间分析，提出了一般性定理，可应用于其他MOEA的运行时间分析

论文分析了SPEA2算法在三个常用多目标问题上的运行时间，提供了相应的理论保证，同时提出的定理可应用于其他MOEA算法的运行时间分析

最近的相关研究主要集中在基础MOEA算法上，对实际应用的MOEA算法的理论研究较少，需要进一步深入研究