A fast incremental BSP tree archive for non-dominated points

DOI10.1007/978-3-319-54157-0_18zbMATH Open1430.90507arXiv1604.01169OpenAlexW2518870586MaRDI QIDQ5215918FDOQ5215918

Authors: Tobias Glasmachers 

Publication date: 13 February 2020

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: Maintaining an archive of all non-dominated points is a standard task in multi-objective optimization. Sometimes it is sufficient to store all evaluated points and to obtain the non-dominated subset in a post-processing step. Alternatively the non-dominated set can be updated on the fly. While keeping track of many non-dominated points efficiently is easy for two objectives, we propose an efficient algorithm based on a binary space partitioning (BSP) tree for the general case of three or more objectives. Our analysis and our empirical results demonstrate the superiority of the method over the brute-force baseline method, as well as graceful scaling to large numbers of objectives.

Full work available at URL: https://arxiv.org/abs/1604.01169

Recommendations

• Very fast non-dominated sorting
• scientific article; zbMATH DE number 1975102
• Quad-Trees and Linear Lists for Identifying Nondominated Criterion Vectors
• On the representation of the search region in multi-objective optimization
• scientific article; zbMATH DE number 2222823

Mathematics Subject Classification ID

Multi-objective and goal programming (90C29) Approximation methods and heuristics in mathematical programming (90C59)

Cited In (1)

• What if we increase the number of objectives? Theoretical and empirical implications for many-objective combinatorial optimization

This page was built for publication: A fast incremental BSP tree archive for non-dominated points

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5215918)