Faster hypervolume-based search using Monte Carlo sampling

Abstract

In recent years, the hypervolume indicator-a set quality measure considering the dominated portion of the objective space-has gained increasing attention in the context of multiobjective search. This is mainly due to the following feature: whenever one Pareto set approximation completely dominates another approximation, the hypervolume of the former will be greater than the hypervolume of the latter. Unfortunately, the calculation of the hypervolume measure is computationally highly demanding, and current algorithms are exponential in the number of objectives. This paper proposes a methodology based on Monte Carlo sampling to estimate the hypervolume contribution of single solutions regarding a specific Pareto set approximation. It is therefore designed to be used in the environmental selection process of an evolutionary algorithm, and allows substantial speedups in hypervolume-based search as the experimental results demonstrate.