Efficient removal of points with smallest crowding distance in two-dimensional incremental non-dominated sorting

Niyaz Nigmatullin, Maxim Buzdalov, Andrey Stankevich

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)

2 Citations (SciVal)

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.

Original languageEnglish
Title of host publicationGECCO 2016 Companion
Subtitle of host publicationProceedings of the 2016 Genetic and Evolutionary Computation Conference
EditorsTobias Friedrich, Frank Neumann, Andrew M. Sutton
PublisherAssociation for Computing Machinery, Inc
Pages1121-1128
Number of pages8
ISBN (Electronic)9781450343237
DOIs
Publication statusPublished - 20 Jul 2016
Externally publishedYes
Event2016 Genetic and Evolutionary Computation Conference, GECCO 2016 Companion - Denver, United States of America
Duration: 20 Jul 201624 Jul 2016

Publication series

NameGECCO 2016 Companion - Proceedings of the 2016 Genetic and Evolutionary Computation Conference

Conference

Conference2016 Genetic and Evolutionary Computation Conference, GECCO 2016 Companion
Country/TerritoryUnited States of America
CityDenver
Period20 Jul 201624 Jul 2016

Keywords

  • Crowding distance
  • Multi-objective optimization
  • Non-dominated sorting
  • Performance evaluation
  • Steady-state algorithms

Fingerprint

Dive into the research topics of 'Efficient removal of points with smallest crowding distance in two-dimensional incremental non-dominated sorting'. Together they form a unique fingerprint.

Cite this