How to compare Pareto sets lies at the heart of research in multi-objective optimization. A measure that has been the subject of much recent study in evolutionary multi-objective optimization is the hypervolume indicator. It measures the volume of the dominated portion of the objective space and is of exceptional interest as it possesses the highly desirable feature of strict Pareto compliance. We have shown in [1] that not only the hypervolume indicator is #P-hard, but also most measures of unions of high-dimensional geometric objects. Assuming the exponential time hypothesis, the hypervolume can only be calculated in time nΩ(d) [6]. [1] also presents an efficient FPRAS (fully polynomial-time randomized approximation scheme) for computing the volume of the unions of objects where one can (a) test whether a given point lies inside the object, (b) sample a point uniformly, and (c) calculate the volume of the object in polynomial time. The algorithm is incorporated in the Shark library, which can be found here, and in the PyGMO library, which can be found here.
Most hypervolume indicator based optimization algorithms like SIBEA, SMS-EMOA or MO-CMA-ES remove the solution with the smallest contribution 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 in [2] that this greedy selection scheme can perform arbitrarily bad and present the first hypervolume algorithm which calculates directly the contribution of every set of λ solutions. Given a population of size n=μ+λ, our algorithm can calculate a set of λ≥1 solutions with minimal d-dimensional hypervolume contribution in time O(nd/2logn+nλ) for d>2. This improves all previously published algorithms by a factor of order n min(λ,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.
The #P-hardness result of [1] for the calculation of the hypervolume does not consider hypervolume contributions. In [3] it is shown that this problem is #P-hard to solve exactly and NP-hard to approximate by a factor of and 2d1-ε for any ε>0. It is also shown that even finding the solution with contribution at most (1+ε) times the minimal contribution of any solution is NP-hard. Though this dashes the hope for a provable efficient approximation algorithm, [3] also presents a very fast approximation algorithm for this problem. We prove that for arbitrarily given ε,δ>0 it calculates a solution with contribution at most (1+ε) times the minimal contribution with probability at least (1-δ). The algorithm solves very large problem instances which are intractable for all previous algorithms (e.g., 10000 solutions in 100 dimensions) within a few seconds. Our implementation can be found here. The algorithm is also incorporated in the Shark library, which can be found here, and in the PyGMO library, which can be found here. A preliminary version of our code can be found here.
We have also examined the approximation quality achieved by sets which maximize the hypervolume indicator. In [4] we compare the optimal approximation factor with the approximation factor achieved by sets maximizing the hypervolume indicator. There we bound the optimal multiplicative approximation factor of n points by 1+Θ(1/n) for arbitrary Pareto fronts. Furthermore, we prove that the same asymptotic approximation ratio is achieved by sets of n points that maximize the hypervolume indicator. On the other hand, it is proven in [4] that both can still deviate significantly. This provable gap is even exponential in the ratio between the largest and the smallest value of the front. [4] also examines the additive approximation ratio of the hypervolume indicator and proves that it achieves the optimal additive approximation ratio apart from a small factor ≤n/(n-2). Hence the hypervolume indicator can be used to achieve a very good additive but not a good multiplicative approximation of a Pareto front. This observation also motivates the definition of a new "logarithmic hypervolume indicator" which achieves a close-to-optimal multiplicative approximation ratio [4,5].
For two dimensions it is possible to select k solutions from a set of n solutions such that the hypervolume is maximized in time O(n (k+log n)) [7]. This can be used as a fast and generic postprocessing method which chooses the best k solutions from the archive of all non-dominated solutions seen during the search of any bi-objective optimizer. The source code is available here.
