A GPU-Based Algorithm for a Faster Hypervolume Contribution Computation


The hypervolume has become very popular in current multiobjective optimization research. Because of its highly desirable features, it has been used not only as a quality measure for comparing final results of multi-objective evolutionary algorithms (MOEAs), but also as a selection operator (it is, for example, very suitable for many-objective optimization problems). However, it has one serious drawback: computing the exact hypervolume is highly costly. The best known algorithms to compute the hypervolume are polynomial in the number of points, but their cost grows exponentially with the number of objectives. This paper proposes a novel approach which, through the use of Graphics Processing Units (GPUs), computes in a faster way the hypervolume contribution of a point. We develop a highly parallel implementation of our approach and demonstrate its performance when using it within the S-Metric Selection Evolutionary Multi-Objective Algorithm (SMS-EMOA). Our results indicate that our proposed approach is able to achieve a significant speed up (of up to 883x) with respect to its sequential counterpart, which allows us to use SMS-EMOA with exact hypervolume calculations, in problems having up to 9 objective functions.