SCIENCE@home

Computing and Updating Hypervolume Contributions in Up to Four Dimensions

Andreia P. Guerreiro,C. Fonseca

Published 2018 in IEEE Transactions on Evolutionary Computation

ABSTRACT

Arising in connection with multiobjective selection and archiving, the hypervolume subset selection problem (HSSP) consists in finding a subset of size <inline-formula> <tex-math notation="LaTeX">${k\leq n}$ </tex-math></inline-formula> of a set <inline-formula> <tex-math notation="LaTeX">${X\subset \mathbb {R}^{d}}$ </tex-math></inline-formula> of <inline-formula> <tex-math notation="LaTeX">${n}$ </tex-math></inline-formula> nondominated points in <inline-formula> <tex-math notation="LaTeX">${d}$ </tex-math></inline-formula>-dimensional space that maximizes the hypervolume indicator. The incremental greedy approximation to the HSSP has an approximation guarantee of <inline-formula> <tex-math notation="LaTeX">${1-1/e}$ </tex-math></inline-formula>, and is polynomial in <inline-formula> <tex-math notation="LaTeX">${n}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">${k}$ </tex-math></inline-formula>, while no polynomial exact algorithms are known for <inline-formula> <tex-math notation="LaTeX">${d\geq 3}$ </tex-math></inline-formula>. The decremental greedy counterpart has no known approximation guarantee, but is potentially faster for large <inline-formula> <tex-math notation="LaTeX">${k}$ </tex-math></inline-formula>, and still leads to good approximations in practice. The computation and update of individual hypervolume contributions are at the core of the implementation of this greedy strategy. In this paper, new algorithms for the computation and update of hypervolume contributions are developed. In three dimensions, updating the total hypervolume and all individual contributions under single-point changes is performed in linear time, while in the 4-D case all contributions are computed in <inline-formula> <tex-math notation="LaTeX">${O(n^{2})}$ </tex-math></inline-formula> time. As a consequence, the decremental greedy approximation to the HSSP can now be obtained in <inline-formula> <tex-math notation="LaTeX">${O(n(n-k) + n\log n)}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">${O(n^{2}(n-k))}$ </tex-math></inline-formula> time for <inline-formula> <tex-math notation="LaTeX">${d=3}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">${d=4}$ </tex-math></inline-formula>, respectively. Experimental results show that the proposed algorithms significantly outperform existing ones.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-38 of 38 references · Page 1 of 1

CITED BY

Showing 1-44 of 44 citing papers · Page 1 of 1