Improved incremental non-dominated sorting for steady-state evolutionary multiobjective optimization

Ilya Yakupov, Maxim Buzdalov

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


We present an algorithm for incremental non-dominated sorting, a procedure to use with steady-state multiobjective algorithms, with the complexity of O(N(log N)^M−2) for a single insertion, where N is the number of points and M is the number of objectives. This result generalizes the previously known O(N) algorithm designed for two objectives.

Our experimental performance study showed that our algorithm demonstrates a superior performance compared to the competitors, including various modifications of the divide-and-conquer non-dominated sorting algorithm (which significantly improve the performance on their own), and the state-of-the-art Efficient Non-domination Level Update algorithm. Only for M = 2 the specialized algorithm for two dimensions outperforms the new algorithm.
Original languageEnglish
Title of host publicationGECCO '17
Subtitle of host publicationProceedings of the Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery
Number of pages8
ISBN (Print)978-1-4503-4920-8
Publication statusPublished - 01 Jul 2017
Externally publishedYes


  • divide-and-conquer
  • non-dominated sorting
  • steady-state algorithms


Dive into the research topics of 'Improved incremental non-dominated sorting for steady-state evolutionary multiobjective optimization'. Together they form a unique fingerprint.

Cite this