Improved quick hypervolume algorithm

DOI10.1016/J.COR.2017.09.016MaRDI QIDQ1652507zbMATH OpenOpenAlexFDO

Authors Andrzej Jaszkiewicz

Publication date 11 July 2018

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.03402

zbMATH Keywords

computational complexity analysishypervolume indicatormultiobjective optimization

Mathematics Subject Classification ID

Multi-objective and goal programming (90C29) Approximation methods and heuristics in mathematical programming (90C59) Abstract computational complexity for mathematical programming problems (90C60)

Abstract: In this paper, we present a significant improvement of Quick Hypervolume algorithm, one of the state-of-the-art algorithms for calculating exact hypervolume of the space dominated by a set of d-dimensional points. This value is often used as a quality indicator in multiobjective evolutionary algorithms and other multiobjective metaheuristics and the efficiency of calculating this indicator is of crucial importance especially in the case of large sets or many dimensional objective spaces. We use a similar divide and conquer scheme as in the original Quick Hypervolume algorithm, but in our algorithm we split the problem into smaller sub-problems in a different way. Through both theoretical analysis and computational study we show that our approach improves computational complexity of the algorithm and practical running times.

Recommendations

• A box decomposition algorithm to compute the hypervolume indicator
• Faster hypervolume-based search using Monte Carlo sampling
• Don't be greedy when calculating hypervolume contributions
• Fast hypervolume approximation scheme based on a segmentation strategy
• Evolutionary Multi-Criterion Optimization

Cites work

• A box decomposition algorithm to compute the hypervolume indicator
• Multidimensional divide-and-conquer
• On the solution of linear recurrence equations

Cited in

(12)

• A box decomposition algorithm to compute the hypervolume indicator
• Fast hypervolume approximation scheme based on a segmentation strategy
• Performance indicators in multiobjective optimization
• What if we increase the number of objectives? Theoretical and empirical implications for many-objective combinatorial optimization
• Efficient computation of expected hypervolume improvement using box decomposition algorithms
• Minimum costs paths in intermodal transportation networks with stochastic travel times and overbookings
• Faster hypervolume-based search using Monte Carlo sampling
• Multi-Objective Evolutionary Algorithms: Past, Present, and Future
• Computing 3-D expected hypervolume improvement and related integrals in asymptotically optimal time
• Don't be greedy when calculating hypervolume contributions
• Evolutionary Multi-Criterion Optimization
• Adaptive nested Monte Carlo approach for multi-objective efficient global optimization

This page was built for publication: Improved quick hypervolume algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1652507)