Don't be greedy when calculating hypervolume contributions

Most hypervolume indicator based optimization algorithms like SIBEA Zitzler et al. 2007, SMS-EMOA Beume et al. 2007, or MO-CMA-ES Igel et al. 2007 remove the solution with the smallest loss with respect to the dominated hypervolume from the population. This is usually iterated λ times until the size of the population no longer exceeds a fixed size μ. We show that there are populations such that the contributing hypervolume of the λ solutions chosen by this greedy selection scheme can be much smaller than the contributing hypervolume of an optimal set of λ solutions. Selecting the optimal λ-set implies calculating (μ+λ over μ)conventional hypervolume contributions, which is considered computationally too expensive. We present the first hypervolume algorithm which calculates directly the contribution of every set of λ solutions. This gives an additive term of (μ+λ over μ)in the runtime of the calculation instead of a multiplicative factor of binomial(μ+λ over μ). Given a population of size n=μ+λ, our algorithm can calculate a set of λ≥ solutions with minimal d-dimensional hypervolume contribution in time O(nd/2 log + n λ) for d > 2. This improves all previously published algorithms by a factor of order nmin(λ,,d/2 for d >3. Therefore even if we remove the solutions one by one greedily as usual, we gain a speedup factor of n for all d > 3.