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前方试验的固定部分),从而证实了上述结果。

0
下载
关闭预览

相关内容

数学是关于数量、结构、变化等主题的探索。
专知会员服务
50+阅读 · 2020年12月14日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
开源书:PyTorch深度学习起步
专知会员服务
50+阅读 · 2019年10月11日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
意识是一种数学模式
CreateAMind
3+阅读 · 2019年6月24日
已删除
创业邦杂志
5+阅读 · 2019年3月27日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2022年2月21日
Arxiv
0+阅读 · 2022年2月21日
Arxiv
0+阅读 · 2022年2月21日
VIP会员
相关VIP内容
相关资讯
意识是一种数学模式
CreateAMind
3+阅读 · 2019年6月24日
已删除
创业邦杂志
5+阅读 · 2019年3月27日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员