A faster algorithm for calculating hypervolume

By Philip Hingston, L. Barone, Simon Huband. IEEE Transactions on Evolutionary Computation, 2006

977 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems

View Paper: https://www.semanticscholar.org/paper/eed426bf6ced711b05376f36a8348e9953037dff

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Information Systems

Citations in the corpus

Quality Assessment of Pareto Set Approximations (2008, background): “This comes at the cost of high computational cost: the best known algorithms for computing the hypervolume have running times which are exponential in the number of objectives (see While, 2005; While et al., 2005, 2006; Fonseca et al., 2006; Beume and Rudolph, 2006).”
A Strengthened Dominance Relation Considering Convergence and Diversity for Evolutionary Many-Objective Optimization (2018, methodology): “6) Performance Metric: The inverted generational distance (IGD) [52] and hypervolume (HV) [53] are employed to evaluate the performance of the algorithms, which are the two most widely used performance metric to measure both the convergence and diversity of the obtained nondominated solution set.”
Transfer Learning-Based Dynamic Multiobjective Optimization Algorithms (2016, background): “At the same time the fast hyper-volume strategy [27] was proposed to achieve a better starting population when changes occur frequently.”
A Reference Vector Guided Evolutionary Algorithm for Many-Objective Optimization (2016, methodology): “Unfortunately, the computational cost for the calculation of the performance become s prohibitively expensive when the number of objectives is large [46].”
A Grid-Based Evolutionary Algorithm for Many-Objective Optimization (2013, positive): “While a large computation cost is required in the exact calculation of the hypervolume indicator in a high-dimensional space, eff orts [7], [68] to address this issue are being made; on the other hand, approximate estimation of the hypervolume indicator has recently been developed by Monte Carlo sam”
An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints (2014, background): “For example, computing hyper-volume metric requires exponentially more computations with the number of objectives [18], [19].”
PlatEMO: A MATLAB Platform for Evolutionary Multi-Objective Optimization [Educational Forum] (2017, background): “In addition, there are a lot of performance indicators pr ovided by PlatEMO for experimental studies, including Coverage [71], generational distance (GD) [85], hypervolume (HV) [86], inverted generational distance (IGD) [87], normalized hypervolume (NHV) [37], pu re diversity (PD) [88], Spacing [89]”
A Fast Way of Calculating Exact Hypervolumes (2012, background): “If a set S has a greater hypervolume than a set S′, S is taken to be a better set of solutions than S′.”
An Evolutionary Many-Objective Optimization Algorithm Based on Dominance and Decomposition (2015, background): “But unfortunately, the exponentially increased computation cost of hypervolume calculation [19],”
Efficient Large-Scale Multiobjective Optimization Based on a Competitive Swarm Optimizer (2020, methodology): “5) Performance Metric: The inverted generational distance (IGD) [61] and hypervolume (HV) [62] are adopted to assess the performance of MOEAs in the experiment.”
HypE: An Algorithm for Fast Hypervolume-Based Many-Objective Optimization (2011, positive): “As to hypervolume calculation, the first algorithms (Zitzler, 2001; Knowles, 2002) operated recursively and in each recursion step the number of objectives was decremented; the underlying principle is known as the hypervolume by slicing objectives approach (While et al., 2006).”
Balancing Objective Optimization and Constraint Satisfaction in Constrained Evolutionary Multiobjective Optimization (2021, methodology): “While the constrained Pareto fronts of all the real-world CMOPs are unknown, the HV [47] metric is employed, where the reference point is set to 1 .”
A Classification-Based Surrogate-Assisted Evolutionary Algorithm for Expensive Many-Objective Optimization (2019, methodology): “In this paper, the HV [73] is not used to assess the performance of the compared algorithms as the obtained solutions of expensive MaOPs are not yet well converged due to the smaller number of FEs allowed, often leading to a zero HV.”
Objective Reduction in Many-Objective Optimization: Linear and Nonlinear Algorithms (2013, background): “However, the utility of such MOEAs is limited by the fact that their running times increase exponentially with M [13]–[15].”
The Hypervolume Indicator Revisited: On the Design of Pareto-compliant Indicators Via Weighted Integration (2007, background): “On the other hand, there are some studies that discuss the usage of this measure for multiobjective search [10, 20, 4] and in particular the issue of fast hypervolume calculation has been a focus of research recently [16, 17, 6, 1].”
Many-Objective Evolutionary Algorithms (2015, methodology): “There has been some recent work on faster computation of the hypervolume indicator, such as hypervolume by slicing objectives (HSO) with worst-case complexity being O( N M − 1 ) [While et al. 2006], the WFG algorithm with worst-case complexity being O(2 N − 1 ) [While et al. 2012], and so forth.”
An Evolutionary Algorithm for Large-Scale Sparse Multiobjective Optimization Problems (2020, background): “Since the Pareto fronts of the MOPs in applications are unknown, the hypervolume (HV) [79] is adopted to measure each obtained solution set.”
A Knee Point-Driven Evolutionary Algorithm for Many-Objective Optimization (2015, methodology): “5) Quality Metrics: Two widely used performance indicators, the HV [50] and the inverted generational”