论文标题
使用二进制或随机锦标赛选择的非主导分类遗传算法II（NSGA-II）的运行时间分析
Running Time Analysis of the Non-dominated Sorting Genetic Algorithm II (NSGA-II) using Binary or Stochastic Tournament Selection
论文作者
论文摘要
进化算法（EAS）已被广泛用于解决多目标优化问题，并已成为最受欢迎的工具。但是，多目标EAS（MOEAS）的理论基础，尤其是基本的理论方面，即运行时间分析，仍然在很大程度上欠发达。现有的少数理论作品主要被视为简单的MOEAS，而非主导的分类遗传算法II（NSGA-II）可能是最有影响力的MOEA，除非考虑到没有交叉的简化变体的最新作品，却没有进行分析。在本文中，我们介绍了用于解决Lotz，Oneminmax和Cocz的标准NSGA-II的运行时间分析，这是三个常用的双向目标优化问题。具体而言，我们证明了Lotz的预期运行时间（即健身评估的数量）为$ O（n^3）$，而Oneminmax和Cocz的$ O（N^2 \ log n）$与先前分析的简单Moeas，Gsemo和Semo相同。接下来，我们介绍了一种新的父母选择策略，随机锦标赛选择（即$ k $ tournament Selection，其中$ k $随机采样$ k $），以替换NSGA-II的二进制锦标赛选择策略，将所需的预期运行时间降低至$ O（n^2）$（n^2）$。还进行了实验，这表明派生的运行时间上限对于Lotz来说很紧，而Oneminmax和Cocz几乎紧密。
Evolutionary algorithms (EAs) have been widely used to solve multi-objective optimization problems, and have become the most popular tool. However, the theoretical foundation of multi-objective EAs (MOEAs), especially the essential theoretical aspect, i.e., running time analysis, has been still largely underdeveloped. The few existing theoretical works mainly considered simple MOEAs, while the non-dominated sorting genetic algorithm II (NSGA-II), probably the most influential MOEA, has not been analyzed except for a very recent work considering a simplified variant without crossover. In this paper, we present a running time analysis of the standard NSGA-II for solving LOTZ, OneMinMax and COCZ, the three commonly used bi-objective optimization problems. Specifically, we prove that the expected running time (i.e., number of fitness evaluations) is $O(n^3)$ for LOTZ, and $O(n^2\log n)$ for OneMinMax and COCZ, which is surprisingly as same as that of the previously analyzed simple MOEAs, GSEMO and SEMO. Next, we introduce a new parent selection strategy, stochastic tournament selection (i.e., $k$ tournament selection where $k$ is uniformly sampled at random), to replace the binary tournament selection strategy of NSGA-II, decreasing the required expected running time to $O(n^2)$ for all the three problems. Experiments are also conducted, suggesting that the derived running time upper bounds are tight for LOTZ, and almost tight for OneMinMax and COCZ.
