Computer Science – Computational Geometry
Scientific paper
2007-04-10
Computer Science
Computational Geometry
9 pages, 2 figures. Comments are welcome
Scientific paper
Hypervolume indicator is a commonly accepted quality measure for comparing Pareto approximation set generated by multi-objective optimizers. The best known algorithm to calculate it for $n$ points in $d$-dimensional space has a run time of $O(n^{d/2})$ with special data structures. This paper presents a recursive, vertex-splitting algorithm for calculating the hypervolume indicator of a set of $n$ non-comparable points in $d>2$ dimensions. It splits out multiple child hyper-cuboids which can not be dominated by a splitting reference point. In special, the splitting reference point is carefully chosen to minimize the number of points in the child hyper-cuboids. The complexity analysis shows that the proposed algorithm achieves $O((\frac{d}{2})^n)$ time and $O(dn^2)$ space complexity in the worst case.
Ding Shengchao
Yang Qing
No associations
LandOfFree
Novel algorithm to calculate hypervolume indicator of Pareto approximation set does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Novel algorithm to calculate hypervolume indicator of Pareto approximation set, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Novel algorithm to calculate hypervolume indicator of Pareto approximation set will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-207369