Improved Quick Hypervolume Algorithm
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Evolutionary AlgorithmsSimilar Papers 제목 키워드 기반
Lazy Greedy Hypervolume Subset Selection from Large Candidate Solution Sets
Subset selection is a popular topic in recent years and a number of subset selection methods have been proposed. Among those methods, hypervolume subset selection is widely used. Greedy hypervolume subset selection algor…
Multiplicative Approximations, Optimal Hypervolume Distributions, and the Choice of the Reference Point
Many optimization problems arising in applications have to consider several objective functions at the same time. Evolutionary algorithms seem to be a very natural choice for dealing with multi-objective problems as the …
Evolutionary AlgorithmsUncrowded Hypervolume-based Multi-objective Optimization with Gene-pool Optimal Mixing
Domination-based multi-objective (MO) evolutionary algorithms (EAs) are today arguably the most frequently used type of MOEA. These methods however stagnate when the majority of the population becomes non-dominated, prev…
Evolutionary AlgorithmsLearning to Approximate: Auto Direction Vector Set Generation for Hypervolume Contribution Approximation
Hypervolume contribution is an important concept in evolutionary multi-objective optimization (EMO). It involves in hypervolume-based EMO algorithms and hypervolume subset selection algorithms. Its main drawback is that …
Optimal Scalarizations for Sublinear Hypervolume Regret
Scalarization is a general, parallizable technique that can be deployed in any multiobjective setting to reduce multiple objectives into one, yet some have dismissed this versatile approach because linear scalarizations …
Bayesian Optimization