The non-dominated sorting genetic algorithm II (NSGA-II) is the most intensively used multi-objective evolutionary algorithm (MOEA) in real-world applications. However, in contrast to several simple MOEAs analyzed also via mathematical means, no such study exists for the NSGA-II so far. In this work, we show that mathematical runtime analyses are feasible also for the NSGA-II. As particular results, we prove that with a population size larger than the Pareto front size by a constant factor, the NSGA-II with two classic mutation operators and three different ways to select the parents satisfies the same asymptotic runtime guarantees as the SEMO and GSEMO algorithms on the basic OneMinMax and LOTZ benchmark functions. However, if the population size is only equal to the size of the Pareto front, then the NSGA-II cannot efficiently compute the full Pareto front (for an exponential number of iterations, the population will always miss a constant fraction of the Pareto front). Our experiments confirm the above findings.
翻译:非占主导地位的分类基因算法II(NSGA-II)是现实世界应用中最常用的多客观演进算法(MOEA),然而,与通过数学分析的若干简单的MOEAs相比,迄今为止NSGA-II还不存在这样的研究。在这项工作中,我们表明数学运行时间分析对于NSGA-II也是可行的。 具体结果是,我们证明,如果人口规模大于Pareto前方大小,以恒定系数计算,国家GA-II拥有两个典型的突变操作员,而选择父母的三种不同方式都符合SEMO和GSEMO基本Ox和LOTZ基准函数上的相同等同的静态运行时间保证。然而,如果人口规模只相当于Pareto前方的大小,那么国家基因组II就无法有效地计算整个Pareto前方(对于指数数,人口总是会错过Pareto前方试验的固定部分),从而证实了上述结果。