Title | Better approximation guarantees for the NSGA-II by using the current crowding distance |
Author | |
Corresponding Author | Doerr,Benjamin |
DOI | |
Publication Years | 2022-07-08
|
Conference Name | Genetic and Evolutionary Computation Conference (GECCO)
|
Source Title | |
Pages | 611-619
|
Conference Date | JUL 09-13, 2022
|
Conference Place | null,Boston,MA
|
Publication Place | 1601 Broadway, 10th Floor, NEW YORK, NY, UNITED STATES
|
Publisher | |
Abstract | A recent runtime analysis (Zheng, Liu, Doerr (2022)) has shown that a variant of the NSGA-II algorithm can efficiently compute the full Pareto front of the OneMinMax problem when the population size is by a constant factor larger than the Pareto front, but that this is not possible when the population size is only equal to the Pareto front size. In this work, we analyze how well the NSGA-II with small population size approximates the Pareto front of One-MinMax. We observe experimentally and by mathematical means that already when the population size is half the Pareto front size, relatively large gaps in the Pareto front remain. The reason for this phenomenon is that the NSGA-II in the selection stage computes the crowding distance once and then repeatedly removes individuals with smallest crowding distance without updating the crowding distance after each removal. We propose an eficient way to implement the NSGA-II using the current crowding distance. In our experiments, this algorithm approximates the Pareto front much better than the previous version. We also prove that the gaps in the Pareto front are at most a constant factor larger than the theoretical minimum. |
Keywords | |
SUSTech Authorship | First
|
Language | English
|
URL | [Source Record] |
Indexed By | |
Funding Project | Basic and Applied Basic Research Foundation of Guangdong Province[2019A1515110177];
|
WOS Research Area | Computer Science
; Robotics
|
WOS Subject | Computer Science, Cybernetics
; Computer Science, Theory & Methods
; Robotics
|
WOS Accession No | WOS:000847380200071
|
EI Accession Number | 20223112528639
|
EI Keywords | Computation theory
; Population statistics
|
ESI Classification Code | Computer Theory, Includes Formal Logic, Automata Theory, Switching Theory, Programming Theory:721.1
; Optimization Techniques:921.5
|
Scopus EID | 2-s2.0-85130367509
|
Data Source | Scopus
|
Citation statistics |
Cited Times [WOS]:3
|
Document Type | Conference paper |
Identifier | http://kc.sustech.edu.cn/handle/2SGJ60CL/365050 |
Department | Department of Computer Science and Engineering |
Affiliation | 1.Guangdong Provincial Key Laboratory of Brain-inspired Intelligent Computation,Department of Computer Science and Engineering,Southern University of Science and Technology,Shenzhen,China 2.Laboratoire D'Informatique (LIX),École Polytechnique,Cnrs,Institut Polytechnique de Paris,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,Doerr,Benjamin. Better approximation guarantees for the NSGA-II by using the current crowding distance[C]. 1601 Broadway, 10th Floor, NEW YORK, NY, UNITED STATES:ASSOC COMPUTING MACHINERY,2022:611-619.
|
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