Novel algorithm to calculate hypervolume indicator of Pareto approximation set
| dc.creator | Yang, Qing | |
| dc.creator | Ding, Shengchao | |
| dc.date | 2007-04-10 | |
| dc.date.accessioned | 2026-07-07T07:55:54Z | |
| dc.date.available | 2026-07-07T07:55:54Z | |
| dc.description | 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. | |
| dc.description | 9 pages, 2 figures. Comments are welcome | |
| dc.identifier | https://arxiv.org/abs/0704.1196 | |
| dc.identifier | http://arxiv.org/abs/0704.1196 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/127123 | |
| dc.subject | Computational Geometry | |
| dc.subject | Neural and Evolutionary Computing | |
| dc.title | Novel algorithm to calculate hypervolume indicator of Pareto approximation set | |
| dc.type | text |