中文版 | English
Title

A First Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm II (NSGA-II)

Author
Corresponding AuthorDoerr, Benjamin
Publication Years
2022
Conference Name
36th AAAI Conference on Artificial Intelligence / 34th Conference on Innovative Applications of Artificial Intelligence / 12th Symposium on Educational Advances in Artificial Intelligence
ISSN
2159-5399
EISSN
2374-3468
Source Title
Conference Date
FEB 22-MAR 01, 2022
Conference Place
null,null,ELECTR NETWORK
Publication Place
2275 E BAYSHORE RD, STE 160, PALO ALTO, CA 94303 USA
Publisher
Abstract
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.
SUSTech Authorship
First
Language
English
URL[Source Record]
Indexed By
Funding Project
Investissement d'avenir project[ANR-11-LABX-0056-LMH] ; Guangdong Basic and Applied Basic Research Foundation[2019A1515110177] ; Guangdong Provincial Key Laboratory[2020B121201001] ; Program for Guangdong Introducing Innovative and Enterpreneurial Teams[2017ZT07X386] ; Shenzhen Science and Technology Program[KQTD2016112514355531]
WOS Research Area
Computer Science
WOS Subject
Computer Science, Artificial Intelligence
WOS Accession No
WOS:000893639103047
Data Source
Web of Science
Citation statistics
Cited Times [WOS]:2
Document TypeConference paper
Identifierhttp://kc.sustech.edu.cn/handle/2SGJ60CL/475000
DepartmentDepartment of Computer Science and Engineering
Affiliation
1.Southern Univ Sci & Technol, Dept Comp Sci & Engn, Guangdong Prov Key Lab Brain Inspired Intelligent, Shenzhen, Peoples R China
2.Ecole Polytech, CNRS, Inst Polytech Paris, Lab Informat LIX, Palaiseau, France
First Author AffilicationDepartment of Computer Science and Engineering
First Author's First AffilicationDepartment of Computer Science and Engineering
Recommended Citation
GB/T 7714
Zheng, Weijie,Liu, Yufei,Doerr, Benjamin. A First Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm II (NSGA-II)[C]. 2275 E BAYSHORE RD, STE 160, PALO ALTO, CA 94303 USA:ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE,2022.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Export to Excel
Export to Csv
Altmetrics Score
Google Scholar
Similar articles in Google Scholar
[Zheng, Weijie]'s Articles
[Liu, Yufei]'s Articles
[Doerr, Benjamin]'s Articles
Baidu Scholar
Similar articles in Baidu Scholar
[Zheng, Weijie]'s Articles
[Liu, Yufei]'s Articles
[Doerr, Benjamin]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Zheng, Weijie]'s Articles
[Liu, Yufei]'s Articles
[Doerr, Benjamin]'s Articles
Terms of Use
No data!
Social Bookmark/Share
No comment.

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.