Symbolic archive representation for a fast nondominance test

Lukasiewycz M, Glaß M, Haubelt C, Teich J (2007)

Publication Status: Published

Publication Type: Conference contribution

Publication year: 2007

Pages Range: 111-125

Event location: Matsushima JP

ISBN: 9783540709275

URI: https://www.scopus.com/inward/record.url?partnerID=HzOxMe3b&scp=37249008208&origin=inward

Abstract

Archives are used in Multi-Objective Evolutionary Algorithms to establish elitism. Depending on the optimization problem, an unconstrained archive may grow to an immense size. With the growing number of nondominated solutions in the archive, testing a new solution for nondominance against this archive becomes the main bottleneck during optimization. As a remedy to this problem, we will propose a new data structure on the basis of Binary Decision Diagrams (BDDs) that permits a nondominance test with a runtime that is independent from the archive size. For this purpose, the region in the objective space weakly dominated by the solutions in the archive is represented by a BDD. We will present the algorithms for constructing the BDD as well as the nondominance test. Moreover, experimental results from using this symbolic data structure will show the efficiency of our approach in test cases where many candidates have to be tested but only few have to be added to the archive. © Springer-Verlag Berlin Heidelberg 2007.

Authors with CRIS profile

Michael Glaß Juniorprofessur für Informatik Christian Haubelt Technische Fakultät Jürgen Teich Lehrstuhl für Informatik 12 (Hardware-Software-Co-Design)

How to cite

APA:

Lukasiewycz, M., Glaß, M., Haubelt, C., & Teich, J. (2007). Symbolic archive representation for a fast nondominance test. In Proceedings of the 4th International Conference on Evolutionary Multi-Criterion Optimization, EMO 2007 (pp. 111-125). Matsushima, JP.

MLA:

Lukasiewycz, Martin, et al. "Symbolic archive representation for a fast nondominance test." Proceedings of the 4th International Conference on Evolutionary Multi-Criterion Optimization, EMO 2007, Matsushima 2007. 111-125.

BibTeX: Download