Improving the Efficiency of the Distance-Based Hypervolume Estimation Using ND-Tree
[ 1 ] Instytut Informatyki, Wydział Informatyki i Telekomunikacji, Politechnika Poznańska | [ P ] employee
2024
scientific article
english
- multiobjective optimization
- hypervolume
- hypervolume estimation
- algorithms and data structures
- Chebycheff functions
EN Hypervolume is most likely the most often used quality indicator in EMO due to its monotonicity with respect to the dominance relation. Since, however, exact calculation of hypervolume is computationally demanding, many researchers have proposed methods for hypervolume estimation. Many of such methods use numerical integration of the distance from the reference point to the upper boundary of the dominated region along uniformly sampled directions. To find this distance for a given direction, the maximum value of the inverse weighted Chebycheff function needs to be found. For small solution sets this could be done by the exhaustive search which, however, may be very inefficient for large solution sets, e.g. for unbounded external archives of EMO algorithms. In this paper, we adapt the ND-Tree-based algorithm for finding the minimum of the standard weighted Chebycheff function to finding the maximum of the inverse function. Through a computational experiment we show that this ND-Tree-based algorithm may be used either for reduction of the running time of hypervolume estimation by up to two orders of magnitude or for improving the estimation accuracy with the same time budget up to an order of magnitude for data sets with up to 12 objectives and 50000 points.
22.04.2024
200
11,7 [List 2023]