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

Zheng，Weijie1; Doerr，Benjamin2

10.1145/3512290.3528847

2022-07-08

Genetic and Evolutionary Computation Conference (GECCO)

GECCO 2022 - Proceedings of the 2022 Genetic and Evolutionary Computation Conference

611-619

JUL 09-13, 2022

null,Boston,MA

1601 Broadway, 10th Floor, NEW YORK, NY, UNITED STATES

ASSOC COMPUTING MACHINERY

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.

approximation crowding distance multi-objective optimization NSGA-II runtime analysis theory

First

English

CPCI-S ; EI

Basic and Applied Basic Research Foundation of Guangdong Province[2019A1515110177];

Computer Science ; Robotics

Computer Science, Cybernetics ; Computer Science, Theory & Methods ; Robotics

WOS:000847380200071

20223112528639

Computation theory ; Population statistics

Computer Theory, Includes Formal Logic, Automata Theory, Switching Theory, Programming Theory:721.1 ; Optimization Techniques:921.5

2-s2.0-85130367509

Scopus

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

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.