| Title | A First Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm II (NSGA-II) |
| Author | |
| Corresponding Author | Doerr, 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]:7
|
| Document Type | Conference paper |
| Identifier | http://kc.sustech.edu.cn/handle/2SGJ60CL/475000 |
| Department | Department 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 Affilication | Department of Computer Science and Engineering |
| First Author's First Affilication | Department 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. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment