中文版 | English
Title

Better approximation guarantees for the NSGA-II by using the current crowding distance

Author
Corresponding AuthorDoerr,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 TypeConference paper
Identifierhttp://kc.sustech.edu.cn/handle/2SGJ60CL/365050
DepartmentDepartment 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 AffilicationDepartment of Computer Science and Engineering
First Author's First AffilicationDepartment 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.
Related Services
Fulltext link
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
[Doerr,Benjamin]'s Articles
Baidu Scholar
Similar articles in Baidu Scholar
[Zheng,Weijie]'s Articles
[Doerr,Benjamin]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Zheng,Weijie]'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.