PaperlayerView exact revision on arXiv

Source-linked AI summary

The Hypervolume Indicator: Problems and Algorithms

Andreia P. Guerreiro, Carlos M. Fonseca, Luís Paquete

arXiv:2005.00515v1cs.DScs.CG

TL;DR

Hypervolume-based problems are computationally challenging, despite the indicator’s importance in multiobjective optimization and evolutionary algorithm selection. This paper surveys their relationships, algorithms, complexities, runtimes, and implementations. It provides a reference for developing new algorithms and choosing appropriate methods, while available results remain limited for some settings.

  • Problem

    Hypervolume-related problems include #P-hard and NP-hard cases, making their relationships and subproblem structure important for developing efficient exact or approximate algorithms.

  • Method

    The paper reviews computational approaches, intrinsic relations, major algorithms, asymptotic and runtime performance, and available implementations for hypervolume-related problems.

  • Results

    The review identifies algorithms that are fastest in particular settings, including WFG for hypervolume computation in many dimensions, particularly d > 7.

  • Takeaways & Limitations

    The paper serves as a starting point for new algorithm development and a reference for selecting suitable implementations in benchmarking and hypervolume-based problem solving.

  • Takeaways & Limitations

    For optimal µ-distributions, exact point locations are known only for continuous linear fronts in two dimensions, and results do not generalize easily to three objectives.

Abstract

from arXiv · show

The hypervolume indicator is one of the most used set-quality indicators for the assessment of stochastic multiobjective optimizers, as well as for selection in evolutionary multiobjective optimization algorithms. Its theoretical properties justify its wide acceptance, particularly the strict monotonicity with respect to set dominance which is still unique of hypervolume-based indicators. This paper discusses the computation of hypervolume-related problems, highlighting the relations between them, providing an overview of the paradigms and techniques used, a description of the main algorithms for each problem, and a rundown of the fastest algorithms regarding asymptotic complexity and runtime. By providing a complete overview of the computational problems associated to the hypervolume indicator, this paper serves as the starting point for the development of new algorithms, and supports users in the identification of the most appropriate implementations available for each problem.

1 INTRODUCTION

Multiobjective optimization typically requires selecting a finite, representative subset of a potentially large Pareto front, while set-quality indicators evaluate such approximations through a single value. The paper introduces the hypervolume indicator and reviews its computational challenges, algorithms, and practical uses.

  • Conflicting objectives usually produce a Pareto front rather than a single optimal solution, so optimizers seek a finite representative subset for decision makers.
  • Set-quality indicators combine characteristics such as proximity, diversity, and spread into a single real-valued assessment of Pareto-front approximations.
  • The hypervolume indicator measures the region dominated by a point set and bounded by a reference point in d-dimensional objective space.
  • Hypervolume evaluates optimizer outcomes using proximity to the Pareto front, diversity, and spread, and has been integrated into several evolutionary multiobjective optimization roles.
  • Its computational cost limits the objectives and evolutionary parameters that can be handled, motivating approximation algorithms and objective-reduction methods.
  • The paper surveys computational approaches, relates hypervolume-based problems, and identifies fast algorithms and implementations for applications and benchmarking.

2 HYPERVOLUME-RELATED PROBLEMS

This section defines the hypervolume indicator and related contribution problems, then explains their computational relationships, complexity barriers, numerical considerations, and theoretical properties.

  • Definitions: The hypervolume indicator measures the region weakly dominated by S and bounded above by reference point r in d-dimensional objective space.It can equivalently be viewed through Lebesgue measure or as the union of boxes [p,r].
  • Definitions: A point’s hypervolume contribution is H(p,S) = H(S ∪ {p}) − H(S \ {p}), representing lost volume when removing p or gained volume when adding p.When p is already in S, the addition interpretation requires checking for this special case because the gained volume is zero.
  • Definitions: Joint hypervolume contribution captures the region dominated simultaneously and exclusively by two points, including overlap between their individual contributions.This quantity is useful for measuring how one point’s contribution decreases after another point is added.
  • Computational problems: Hypervolume-related problems are generally difficult in arbitrary dimension: Hypervolume and OneContribution are #P-hard, while HSSP is NP-hard for d ≥3.Efficient exact algorithms for fixed, small d therefore depend on understanding relationships among the problems and their subproblems.
  • Computational considerations: Subtracting two large hypervolumes to compute a contribution can create precision problems, so coordinate-level subtraction and dedicated OneContribution algorithms are preferred.The paper recommends avoiding hypervolume subtraction whenever possible for numerical stability.
  • Properties: The indicator is scaling independent and strictly ≺-monotonic, making it maximal for the Pareto front and preserving point-set order under objective scaling.Its non-decreasing submodularity also gives greedy approximation guarantees for HSSP, although guarantees do not extend to HSSPComplement.
  • Properties: Exact optimal µ-distributions are known only for continuous linear fronts in two dimensions, while general fronts and three-dimensional cases remain substantially less characterized.For continuous linear fronts, the unique optimal subset lies on the Pareto front and is uniformly spaced between two outer points whose positions depend on the reference point and extreme points.

3 PARADIGMS AND TECHNIQUES

This section introduces the techniques and paradigms used in state-of-the-art algorithms for hypervolume-related problems, followed by overviews of algorithms for hypervolume, contributions, and HSSP.

  • The section surveys techniques and paradigms used by algorithms for hypervolume-related problems.
  • It then reviews existing algorithms for computing the hypervolume indicator and hypervolume contributions.
  • The section also covers exact and approximation algorithms for the Hypervolume Subset Selection Problem.
  • Remarks sections summarize algorithms with respect to runtime and asymptotic complexity, while Appendix A provides implementation links.

3.1 Paradigms

The section presents inclusion-exclusion, dimension sweep, and divide-and-conquer paradigms for hypervolume-related computation, including their decompositions, subproblems, and representative algorithms.

  • Inclusion-Exclusion Principle: Inclusion-exclusion alternates inclusion and exclusion over combinations of points, but can require Θ(2^n) computation.For the hypervolume problem, it sums single-point hypervolumes, subtracts pairwise terms, and continues over larger subsets.
  • Dimension Sweep: Dimension sweep orders points by one coordinate, solves a (d−1)-dimensional subproblem for each point, and combines the resulting solutions.For hypervolume, axis-parallel cuts partition the dominated region into slices whose hypervolumes are summed.
  • Dimension Sweep: The three-dimensional example divides the volume into n = 6 horizontal slices and further splits the topmost slice’s base area.
  • Dimension Sweep: Dimension-sweep algorithms may recompute each slice base from scratch or update it from the preceding slice.
  • Spatial Divide-and-Conquer: Spatial divide-and-conquer recursively splits the hypervolume into parts using axis-parallel hyperplanes until simpler subproblems remain.A median point in one coordinate can define the split; one subproblem projects points and the reference point onto the splitting hyperplane.
  • Multidimensional Divide-and-Conquer: Multidimensional divide-and-conquer creates two d-dimensional subproblems of size n/2 and one (d−1)-dimensional merge subproblem.HVDC3D is identified as an algorithm using this paradigm for d = 3, with O(n log n) complexity.

3.2 Techniques

The paper presents bounding, objective reordering, and dominated-point handling as techniques for computing hypervolume contributions. These techniques simplify geometric representations or preserve useful structure while affecting computational efficiency.

  • Bounding Technique.: Bounding projects points onto the surface of the axis-parallel box dominated by the target point, then filters dominated projections.The remaining nondominated projections form the auxiliary delimiter set used to bound the contribution.
  • Bounding Technique.: The bounding technique discards projected points that cannot delimit the target point’s contribution without changing that contribution.The absolute positions of the delimiters produced by projection are irrelevant to the contribution value.
  • Objective Reordering.: Objective reordering leaves the hypervolume result unchanged but can affect implementation runtime.The paper illustrates equivalent coordinate rotations and notes that reordering objectives matters for computational performance.
  • Dealing With Dominated Points.: For dominated points, contribution computation can preserve the point-set structure by splitting the target contribution into slices.In the example, the contribution of p5 is divided into three horizontal or vertical slices and their areas are summed.
  • Dealing With Dominated Points.: A structure-destructive alternative removes dominated points sequentially and subtracts their contributions from the target contribution.This approach solves t + 1 OneContribution problems when p dominates t points and loses inner-delimiter information.

4 HYPERVOLUME INDICATOR

The section surveys conceptually distinct and fast algorithms for computing the hypervolume indicator, spanning dimension sweep, spatial divide-and-conquer, and related techniques. It compares asymptotic complexity, runtime performance, dimensional applicability, and implementation availability.

  • Other paradigms: LebMeasure computes hypervolume by accumulating exclusive hypercubes, projecting points onto coordinate hyperplanes, and removing dominated points.Its time complexity is exponential in dimension: O(nd).
  • Runtime performance: WFG is among the fastest practical algorithms for many dimensions, particularly d > 7, although it is not asymptotically fastest.Its tightened upper bound is O(nd−1), with a lower bound of Ω(nd/2 logn).
  • Spatial divide-and-conquer: Chan’s algorithm has the best known time complexity for d ≥4, achieving O(nd/3 polylog n) through spatial divide-and-conquer and partition simplification.Despite this asymptotic advantage, no implementation is available online.
  • Practical recommendations: HBDA-NI can be competitive in d ≥4, but its memory requirements limit its use as dimensionality grows.Its exponential memory growth is why it is not recommended for d ≥7.
  • Practical recommendations: Algorithm choice depends strongly on dimensionality, runtime evidence, data characteristics, memory, and implementation availability.HV3D+ is recommended for d = 3, HV4D+ for d = 4, HBDA-NI for d = 5, 6, and WFG or QHV/QHV-II generally for d ≥7.

5 HYPERVOLUME CONTRIBUTIONS

Hypervolume contributions support selection and several related computational problems, with algorithms tailored to dimensionality and update structure. The section emphasizes dimension sweep, incremental computation, and best-first search as central techniques.

  • Problem relations: Hypervolume-based selection commonly uses AllContributions or HSSP, while contribution calculations also appear inside other hypervolume algorithms.Contributions may be required directly for selection or ranking and indirectly by approximation procedures.
  • AllContributions: exQHV extends QHV to compute all contributions by retaining contribution values, changing pivot selection, and excluding only multiply dominated points.Points dominated by a single point remain necessary for computing the dominating point’s contribution.
  • Dimension sweep: EF2D and EF provide Θ(n logn) dimension-sweep algorithms for AllContributions in d = 2 and d = 3, respectively.EF uses O(n) space in three dimensions.
  • Dimension sweep: HVC3D computes all contributions in O(n logn) time using linear-time amortized updates after preprocessing.It replaces the tree used by EF with a doubly linked list based on HV3D+ data structures.
  • Dimension sweep: HVC4D is currently the asymptotically and empirically fastest AllContributions algorithm for d = 4, with O(n^2) time and O(n) space.It solves a sequence of three-dimensional incremental-update cases.
  • LeastContributor: IHSO* and IWFG search for the least contributor through progressively refined partial contributions and best-first queueing.IWFG combines WFG with IHSO*; IHSO* stops when a fully computed contribution is identified as least.
  • Recommendations: For d = 3 and d = 4, HVC3D and HVC4D were up to 456 times faster than IWFG for LeastContributor; IWFG is recommended for d > 5.The reported update complexities assume preconfigured data structures, and some update procedures require nondominated input sets.

6 HYPERVOLUME SUBSET SELECTION

The HSSP asks for a fixed-size subset with maximum hypervolume, but exact computation becomes difficult as dimensions and subset sizes grow. The section compares exact, dynamic, branch-and-bound, greedy, and approximation approaches.

  • 6 HYPERVOLUME SUBSET SELECTION: HSSP is NP-hard, and no general exact algorithm for d > 3 avoids checking every combination of k points.Algorithms that avoid exhaustive combination checks are limited mainly to d = 2, d = 3, small k, or k close to n.
  • Exact algorithms: BF solves the general d-dimensional exact HSSP by checking every combination of n − k points to discard, with O(n^d/2 logn + n^(n−k)) time.Its space complexity is O(min(n^d/2,n^(n−k))).
  • 6.1 Two dimensions: In two dimensions, extreme2d and k-LSP are currently the fastest exact HSSP algorithms.Their runtimes, like B&B, slow as k approaches n/2 and accelerate as k approaches n.
  • 6.1 Three dimensions: For three dimensions, the best exact algorithm depends on n and k; BCE3D and B&B suit small k, while BF, B&B, and GM-sc suit k close to n.Only B&B and GM-sc have online implementations among the listed three-dimensional exact methods.
  • Approximation algorithms: Greedy HSSP approximations provide an alternative for computationally expensive cases, using decremental, incremental, local-search, or evolutionary approaches.Their runtime depends on the hypervolume algorithms used within the generic approach.
  • Approximation algorithms: The EPTAS approximates HSSP for any constant d with an O(1 − ϵ) guarantee and O(n(k + logn)) time for fixed d and ϵ.Its underlying bound is stated for constant dimensions and approximation parameter.

7 CONCLUDING REMARKS

The paper reviews the hypervolume indicator’s theoretical properties and computational algorithms, emphasizing both its continued value and its remaining cost in higher dimensions. It recommends exploiting algorithmic relations and fast approximations where exact selection is limited.

  • Theoretical properties: The reviewed properties include strict monotonicity, scaling independence, optimal µ-distributions, and submodularity.These properties characterize which sets the indicator prefers, including proximity and spread depending on the Pareto-front slope.
  • Computational trade-offs: Hypervolume computation has become more affordable, especially for low-dimensional cases and small problem sizes, but selection remains limited for d ≥ 3.Fast greedy algorithms with known approximation ratios are identified as alternatives.
  • Algorithmic principles: Dimension sweep underlies faster low-dimensional algorithms and remains useful in general-purpose methods when combined with bounding.Spatial divide-and-conquer and local upper bounds are more competitive in higher-dimensional cases.
  • Practical contribution: The paper aims to motivate new hypervolume algorithms and help users choose the fastest available implementations for benchmarking and optimization.It also provides source-code links and recommendations for each problem.

A LINKS TO SOURCE CODE

The appendix points readers to source-code implementations for the algorithms covered in the paper. Table 5 organizes these implementation links.

  • A LINKS TO SOURCE CODE: Table 5 summarizes links to source-code implementations for algorithms described in Sections 4 through 6.The table is presented as a list of links to source codes.
Loading 2005.00515v1…