An Efficient Algorithm for Computing Hypervolume Contributions

The hypervolume indicator serves as a sorting criterion in many recent multi-objective evolutionary algorithms (MOEAs). Typical algorithms remove the solution with the smallest loss with respect to the dominated hypervolume from the population. We present a new algorithm which determines for a population of size n with d objectives, a solution with minimal hypervolume contribution in time O(n(d/2) log n) for d > 2. This improves all previously published algorithms by a factor of n for all d > 3 and by a factor of root n for d = 3. We also analyze hypervolume indicator based optimization algorithms which remove lambda > 1 solutions from a population of size n = mu + lambda. We show that there are populations such that the hypervolume contribution of iteratively chosen lambda solutions is much larger than the hypervolume contribution of an optimal set of lambda solutions. Selecting the optimal set of lambda solutions implies calculating ((n)(mu)) conventional hypervolume contributions, which is considered to be computationally too expensive. We present the first hypervolume algorithm which directly calculates the contribution of every set of lambda solutions. This gives an additive term of ((n)(mu)) in the runtime of the calculation instead of a multiplicative factor of ((n)(mu)). More precisely, for a population of size n with d objectives, our algorithm can calculate a set of A solutions with minimal hypervolume contribution in time O(n(d/2) log n + n(lambda)) for d > 2. This improves all previously published algorithms by a factor of n(min{lambda,d/2}) for d > 3 and by a factor of n for d = 3.