@inproceedings{975a095967e6450b8afffe0d240e0591,
title = "Efficient removal of points with smallest crowding distance in two-dimensional incremental non-dominated sorting",
abstract = "Many evolutionary multi-objective algorithms rely heavily on non-dominated sorting, the procedure of assigning ranks to individuals according to Pareto domination relation. The steady-state versions of these algorithms need efficient implementations of incremental non-dominated sorting, an algorithm or data structure which supports efficient addition of a new individual and deletion of the worst individual. Recent research brought new advanced algorithms, but none of them can be cheaply adapted to sublinear location of the point having the smallest crowding distance, a measure used in the NSGA-II algorithm. In this paper we address this issue by reducing it to a series of extreme point queries to certain convex polygons. We present theoretical estimation of the worst-case running time, as well as experimental results which show that the proposed modifications reduce the running time significantly on benchmark problems for large population sizes.",
keywords = "Crowding distance, Multi-objective optimization, Non-dominated sorting, Performance evaluation, Steady-state algorithms",
author = "Niyaz Nigmatullin and Maxim Buzdalov and Andrey Stankevich",
note = "Publisher Copyright: {\textcopyright} 2016 ACM.; 2016 Genetic and Evolutionary Computation Conference, GECCO 2016 Companion ; Conference date: 20-07-2016 Through 24-07-2016",
year = "2016",
month = jul,
day = "20",
doi = "10.1145/2908961.2931685",
language = "English",
series = "GECCO 2016 Companion - Proceedings of the 2016 Genetic and Evolutionary Computation Conference",
publisher = "Association for Computing Machinery",
pages = "1121--1128",
editor = "Tobias Friedrich and Frank Neumann and Sutton, {Andrew M.}",
booktitle = "GECCO 2016 Companion",
address = "United States of America",
}