Make Evolutionary Multiobjective Algorithms Scale Better with Advanced Data Structures: Van Emde Boas Tree for Non-dominated Sorting

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

Abstract

We improve the worst-case time complexity of non-dominated sorting, an operation frequently used in evolutionary multiobjective algorithms, to O(n·(log n)k-2 log log n), where n is the number of solutions, k is the number of objectives, and the random-access memory computation model is assumed. This improvement was possible thanks to the van Emde Boas tree, an “advanced” data structure which stores a set of non-negative integers less than n and supports many queries in O(log log n). This is not only a theoretical improvement, as we also provide an efficient implementation of the van Emde Boas tree, which resulted in a competitive algorithm that scales better than other algorithms when n grows, at least for small numbers of objectives greater than two.
Original languageEnglish
Title of host publicationEvolutionary Multi-Criterion Optimization - 10th International Conference, EMO 2019, Proceedings
Subtitle of host publication10th International Conference, EMO 2019, East Lansing, MI, USA, March 10-13, 2019, Proceedings
EditorsKathrin Klamroth, Patrick Reed, Kalyanmoy Deb, Erik Goodman, Carlos A. Coello Coello, Kaisa Miettinen, Sanaz Mostaghim
PublisherSpringer Nature
Pages66-77
Number of pages12
ISBN (Electronic)978-3-030-12598-1, 303012598X
ISBN (Print)9783030125974
DOIs
Publication statusPublished - 04 Feb 2019
Externally publishedYes

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Nature
Volume11411
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • Large-scale optimization
  • Non-dominated sorting
  • vEB tree

Fingerprint

Dive into the research topics of 'Make Evolutionary Multiobjective Algorithms Scale Better with Advanced Data Structures: Van Emde Boas Tree for Non-dominated Sorting'. Together they form a unique fingerprint.

Cite this