论文标题
从了解NSGA-II的人口动态到第一个经过验证的下限
From Understanding the Population Dynamics of the NSGA-II to the First Proven Lower Bounds
论文作者
论文摘要
由于NSGA-II的种群动态更为复杂，因此该算法的现有运行时保证都没有伴随着非平凡的下限。通过对NSGA-II的人口动态的首次数学理解，也就是说，通过估计具有一定客观价值的个体的预期数量，我们证明，具有合适人口大小的NSGA-II需要$ω（nn \ log n）$函数评估，以找到占地面积的问题和$ω$ J $ k的$ j $ kump $ kump of nnn^$ kump of nnn^$ kump $ kump nnn $ ump。这些界限在渐近上（即，它们匹配先前显示的上限），并表明这里的NSGA-II甚至在平行运行时（迭代次数）（迭代次数）从较大的人口规模中的利润也没有。对于OneJumpZeroJump问题，当使用相同的排序用于计算两个目标的拥挤距离贡献时，我们甚至获得了一个紧张的运行时估计，其中包括领导常数。
Due to the more complicated population dynamics of the NSGA-II, none of the existing runtime guarantees for this algorithm is accompanied by a non-trivial lower bound. Via a first mathematical understanding of the population dynamics of the NSGA-II, that is, by estimating the expected number of individuals having a certain objective value, we prove that the NSGA-II with suitable population size needs $Ω(Nn\log n)$ function evaluations to find the Pareto front of the OneMinMax problem and $Ω(Nn^k)$ evaluations on the OneJumpZeroJump problem with jump size $k$. These bounds are asymptotically tight (that is, they match previously shown upper bounds) and show that the NSGA-II here does not even in terms of the parallel runtime (number of iterations) profit from larger population sizes. For the OneJumpZeroJump problem and when the same sorting is used for the computation of the crowding distance contributions of the two objectives, we even obtain a runtime estimate that is tight including the leading constant.
