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

Maxim Buzdalov

doi:10.1007/978-3-030-12598-1_6

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

Maxim Buzdalov

ITMO University

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

9 Citations (Scopus)

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 language	English
Title of host publication	Evolutionary Multi-Criterion Optimization - 10th International Conference, EMO 2019, Proceedings
Subtitle of host publication	10th International Conference, EMO 2019, East Lansing, MI, USA, March 10-13, 2019, Proceedings
Editors	Kathrin Klamroth, Patrick Reed, Kalyanmoy Deb, Erik Goodman, Carlos A. Coello Coello, Kaisa Miettinen, Sanaz Mostaghim
Publisher	Springer Nature
Pages	66-77
Number of pages	12
ISBN (Electronic)	978-3-030-12598-1, 303012598X
ISBN (Print)	9783030125974
DOIs	https://doi.org/10.1007/978-3-030-12598-1_6
Publication status	Published - 04 Feb 2019
Externally published	Yes

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Nature
Volume	11411
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Keywords

Large-scale optimization
Non-dominated sorting
vEB tree

Access to Document

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

Permanent link

Persistent link

Cite this

Buzdalov, M. (2019). Make Evolutionary Multiobjective Algorithms Scale Better with Advanced Data Structures: Van Emde Boas Tree for Non-dominated Sorting. In K. Klamroth, P. Reed, K. Deb, E. Goodman, C. A. Coello Coello, K. Miettinen, & S. Mostaghim (Eds.), Evolutionary Multi-Criterion Optimization - 10th International Conference, EMO 2019, Proceedings: 10th International Conference, EMO 2019, East Lansing, MI, USA, March 10-13, 2019, Proceedings (pp. 66-77). (Lecture Notes in Computer Science; Vol. 11411). Springer Nature. https://doi.org/10.1007/978-3-030-12598-1_6

Buzdalov, Maxim. / Make Evolutionary Multiobjective Algorithms Scale Better with Advanced Data Structures : Van Emde Boas Tree for Non-dominated Sorting. Evolutionary Multi-Criterion Optimization - 10th International Conference, EMO 2019, Proceedings: 10th International Conference, EMO 2019, East Lansing, MI, USA, March 10-13, 2019, Proceedings. editor / Kathrin Klamroth ; Patrick Reed ; Kalyanmoy Deb ; Erik Goodman ; Carlos A. Coello Coello ; Kaisa Miettinen ; Sanaz Mostaghim. Springer Nature, 2019. pp. 66-77 (Lecture Notes in Computer Science).

@inproceedings{ffa6ea18c9e34c83ab80cd3ff91f97a1,

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

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.",

keywords = "Large-scale optimization, Non-dominated sorting, vEB tree",

author = "Maxim Buzdalov",

note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2019.",

year = "2019",

month = feb,

day = "4",

doi = "10.1007/978-3-030-12598-1_6",

language = "English",

isbn = "9783030125974",

series = "Lecture Notes in Computer Science",

publisher = "Springer Nature",

pages = "66--77",

editor = "Kathrin Klamroth and Patrick Reed and Kalyanmoy Deb and Erik Goodman and {Coello Coello}, {Carlos A.} and Kaisa Miettinen and Sanaz Mostaghim",

booktitle = "Evolutionary Multi-Criterion Optimization - 10th International Conference, EMO 2019, Proceedings",

address = "Switzerland",

}

Buzdalov, M 2019, Make Evolutionary Multiobjective Algorithms Scale Better with Advanced Data Structures: Van Emde Boas Tree for Non-dominated Sorting. in K Klamroth, P Reed, K Deb, E Goodman, CA Coello Coello, K Miettinen & S Mostaghim (eds), Evolutionary Multi-Criterion Optimization - 10th International Conference, EMO 2019, Proceedings: 10th International Conference, EMO 2019, East Lansing, MI, USA, March 10-13, 2019, Proceedings. Lecture Notes in Computer Science, vol. 11411, Springer Nature, pp. 66-77. https://doi.org/10.1007/978-3-030-12598-1_6

Make Evolutionary Multiobjective Algorithms Scale Better with Advanced Data Structures: Van Emde Boas Tree for Non-dominated Sorting. / Buzdalov, Maxim.
Evolutionary Multi-Criterion Optimization - 10th International Conference, EMO 2019, Proceedings: 10th International Conference, EMO 2019, East Lansing, MI, USA, March 10-13, 2019, Proceedings. ed. / Kathrin Klamroth; Patrick Reed; Kalyanmoy Deb; Erik Goodman; Carlos A. Coello Coello; Kaisa Miettinen; Sanaz Mostaghim. Springer Nature, 2019. p. 66-77 (Lecture Notes in Computer Science; Vol. 11411).

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

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 -

Buzdalov M. Make Evolutionary Multiobjective Algorithms Scale Better with Advanced Data Structures: Van Emde Boas Tree for Non-dominated Sorting. In Klamroth K, Reed P, Deb K, Goodman E, Coello Coello CA, Miettinen K, Mostaghim S, editors, Evolutionary Multi-Criterion Optimization - 10th International Conference, EMO 2019, Proceedings: 10th International Conference, EMO 2019, East Lansing, MI, USA, March 10-13, 2019, Proceedings. Springer Nature. 2019. p. 66-77. (Lecture Notes in Computer Science). doi: 10.1007/978-3-030-12598-1_6

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

Abstract

Publication series

Keywords

Access to Document

Permanent link

Other files and links

Fingerprint

Cite this