TY - GEN

T1 - Make Evolutionary Multiobjective Algorithms Scale Better with Advanced Data Structures

T2 - Van Emde Boas Tree for Non-dominated Sorting

AU - Buzdalov, Maxim

N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2019.

PY - 2019/2/4

Y1 - 2019/2/4

N2 - 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.

AB - 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.

KW - Large-scale optimization

KW - Non-dominated sorting

KW - vEB tree

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85063035224&origin=resultslist

U2 - 10.1007/978-3-030-12598-1_6

DO - 10.1007/978-3-030-12598-1_6

M3 - Conference Proceeding (Non-Journal item)

SN - 9783030125974

T3 - Lecture Notes in Computer Science

SP - 66

EP - 77

BT - Evolutionary Multi-Criterion Optimization - 10th International Conference, EMO 2019, Proceedings

A2 - Klamroth, Kathrin

A2 - Reed, Patrick

A2 - Deb, Kalyanmoy

A2 - Goodman, Erik

A2 - Coello Coello, Carlos A.

A2 - Miettinen, Kaisa

A2 - Mostaghim, Sanaz

PB - Springer Nature

ER -