The Hypervolume Indicator Guerreiro, Andreia P.; Fonseca, Carlos M.; Paquete, Luís
ACM computing surveys,
07/2021, Volume:
54, Issue:
6
Journal Article
Peer reviewed
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 article 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 article 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.
The atom-bond connectivity index (or, for short, ABC index) is a molecular structure descriptor bridging chemistry to graph theory. It is probably the most studied topological index among all ...numerical parameters of a graph that characterize its topology. For a given graph G = (V, E), the ABC index of G is defined as Formula: see text, where di denotes the degree of the vertex i, and ij is the edge incident to the vertices i and j. A combination of physicochemical and the ABC index properties are commonly used to foresee the bioactivity of different chemical composites. Additionally, the applicability of the ABC index in chemical thermodynamics and other areas of chemistry, such as in dendrimer nanostars, benzenoid systems, fluoranthene congeners, and phenylenes is well studied in the literature. While finding of the graphs with the greatest ABC-value is a straightforward assignment, the characterization of the tree(s) with minimal ABC index is a problem largely open and has recently given rise to numerous studies and conjectures. A B1-branch of a graph is a pendent path of order 2. In this paper, we provide an important step forward to the full characterization of these minimal trees. Namely, we show that a minimal-ABC tree contains neither 4 nor 3 B1-branches. The case when the number of B1-branches is 2 is also considered.
We propose a new approach to the computation of the hypervolume indicator, based on partitioning the dominated region into a set of axis-parallel hyperrectangles or boxes. We present a nonincremental ...algorithm and an incremental algorithm, which allows insertions of points, whose time complexities are O(n⌊p−12⌋+1) and O(n⌊p2⌋+1), respectively, where n is the number of points and p is the dimension of the objective space. While the theoretical complexity of such a method is lower bounded by the complexity of the partition, which is, in the worst-case, larger than the best upper bound on the complexity of the hypervolume computation, we show that it is practically efficient. In particular, the nonincremental algorithm competes with the currently most practically efficient algorithms. Finally, we prove an enhanced upper bound of O(np−1) and a lower bound of Ω(n⌊p2⌋logn) for p≥4 on the worst-case complexity of the WFG algorithm.
•We propose a theoretically and practically efficient method to compute hypervolumes.•We partition the dominated region into axis-parallel hyperrectangles or boxes.•We provide a refined analysis of the complexity of the WFG algorithm.
Habitat loss is silently leading numerous insects to extinction. Conservation efforts, however, have not been designed specifically to protect these organisms, despite their ecological and ...evolutionary significance. On the basis of species-host area equations, parameterized with data from the literature and interviews with botanical experts, I estimated the number of specialized plant-feeding insects (i.e., monophages) that live in 34 biodiversity hotspots and the number committed to extinction because of habitat loss. I estimated that 795,971-1,602,423 monophagous insect species live in biodiversity hotspots on 150,371 endemic plant species, which is 5.3-10.6 monophages per plant species. I calculated that 213,830-547,500 monophagous species are committed to extinction in biodiversity hotspots because of reduction of the geographic range size of their endemic hosts. I provided rankings of biodiversity hotspots on the basis of estimated richness of monophagous insects and on estimated number of extinctions of monophagous species. Extinction rates were predicted to be higher in biodiversity hotspots located along strong environmental gradients and on archipelagos, where high spatial turnover of monophagous species along the geographic distribution of their endemic plants is likely. The results strongly support the overall strategy of selecting priority conservation areas worldwide primarily on the basis of richness of endemic plants. To face the global decline of insect herbivores, one must expand the coverage of the network of protected areas and improve the richness of native plants on private lands.
The effect of haemodynamic monitoring of pulmonary artery pressure has predominantly been studied in the USA. There is a clear need for randomised trial data from patients treated with contemporary ...guideline-directed-medical-therapy with long-term follow-up in a different health-care system.
MONITOR-HF was an open-label, randomised trial, done in 25 centres in the Netherlands. Eligible patients had chronic heart failure of New York Heart Association class III and a previous heart failure hospitalisation, irrespective of ejection fraction. Patients were randomly assigned (1:1) to haemodynamic monitoring (CardioMEMS-HF system, Abbott Laboratories, Abbott Park, IL, USA) or standard care. All patients were scheduled to be seen by their clinician at 3 months and 6 months, and every 6 months thereafter, up to 48 months. The primary endpoint was the mean difference in the Kansas City Cardiomyopathy Questionnaire (KCCQ) overall summary score at 12 months. All analyses were by intention-to-treat. This trial was prospectively registered under the clinical trial registration number NTR7673 (NL7430) on the International Clinical Trials Registry Platform.
Between April 1, 2019, and Jan 14, 2022, we randomly assigned 348 patients to either the CardioMEMS-HF group (n=176 51%) or the control group (n=172 49%). The median age was 69 years (IQR 61–75) and median ejection fraction was 30% (23–40). The difference in mean change in KCCQ overall summary score at 12 months was 7·13 (95% CI 1·51–12·75; p=0·013) between groups (+7·05 in the CardioMEMS group, p=0·0014, and –0·08 in the standard care group, p=0·97). In the responder analysis, the odds ratio (OR) of an improvement of at least 5 points in KCCQ overall summary score was OR 1·69 (95% CI 1·01–2·83; p=0·046) and the OR of a deterioration of at least 5 points was 0·45 (0·26–0·77; p=0·0035) in the CardioMEMS-HF group compared with in the standard care group. The freedom of device-related or system-related complications and sensor failure were 97·7% and 98·8%, respectively.
Haemodynamic monitoring substantially improved quality of life and reduced heart failure hospitalisations in patients with moderate-to-severe heart failure treated according to contemporary guidelines. These findings contribute to the aggregate evidence for this technology and might have implications for guideline recommendations and implementation of remote pulmonary artery pressure monitoring.
The Dutch Ministry of Health, Health Care Institute (Zorginstituut), and Abbott Laboratories.
This paper introduces several algorithms for finding a representative subset of the non-dominated point set of a biobjective discrete optimization problem with respect to uniformity, coverage and the ...ϵ-indicator. We consider the representation problem itself as multiobjective, trying to find a good compromise between these quality measures. These representation problems are formulated as particular facility location problems with a special location structure, which allows for polynomial-time algorithms in the biobjective case based on the principles of dynamic programming and threshold approaches. In addition, we show that several multiobjective variants of these representation problems are also solvable in polynomial time. Computational results obtained by these approaches on a wide range of randomly generated point sets are presented and discussed.
•We formulate the representation problem in two dimensions for three different measures: uniformity, coverage, and є-indicator.•We present algorithms that solve the representation problems for the three measures in polynomial time.•We consider multiobjective variants of representation problems, and present polynomial time algorithms to solve them.•We present and discuss experimental results for all the problems.
•A new family of quality indicators for multiobjective optimization is formalized.•The Hypervolume Sharpe-Ratio indicator is presented as an instance of that family.•Theoretical analysis reveals the ...main properties of this indicator.•Experimental results show competitiveness with the hypervolume indicator.
Set-quality indicators have been used in Evolutionary Multiobjective Optimization Algorithms (EMOAs) to guide the search process. Recently, a new class of set-quality indicators combining the selection of solutions with fitness assignment has been proposed. This class is based on a formulation of fitness assignment as a Portfolio Selection Problem, where solutions are seen as assets whose returns are random variables, and fitness represents the investment in such assets/solutions. The Hypervolume Sharpe Ratio (HSR) Indicator is an instance of this class of indicators which has led to promising results as part of an EMOA denominated the Portfolio Optimization Selection Evolutionary Algorithm (POSEA). In this paper, the class of Sharpe-Ratio Indicators is formalized, and the HSR indicator is studied in regard to monotonicity, sensitivity to objective scaling, and dependence on its parameters. In addition, optimal μ-distributions on two-objective linear fronts, and the corresponding fitness assignments, are characterized. Such optimal μ-distributions turn out to be identical to those of the Hypervolume Indicator on the same fronts. Experimental results complement the analysis.
The expenditure benchmark is an indicator for the evolution of public expenditure introduced in 2011 in the already complex European fiscal rules framework, being a very specific application of an ...expenditure rule. However, it is a quite complex indicator and not suitable for the use at national level by the Independent Fiscal Institutions—that monitor compliance with national fiscal rules—as it relies on the European Commission’s data inputs and judgement not available in real time. This paper argues for more transparency and for a simplification of this indicator to reduce the reliance on non-observable variables. Such improvements are essential as most existing proposals to reform the European Union’s fiscal rules aim to use an expenditure rule as the operational fiscal rule, a role the expenditure benchmark as is cannot fulfil.
In this paper, we extend the notion of banded matrices to matrices where two bands are allowed, called double banded matrices. Our main aim is to establish the periodicity of the determinants for
...double banded matrices. As a corollary, we answer to two recent conjectures and other extensions. Several illustrative examples are provided as well.
We provide a very short proof of a Qi-Zhao-Guo closed form for derangements numbers based on the determinants of certain Hessenberg matrices. The proof is grounded on a basic result on finite ...sequences and an inductive argument.
PDF
