TY - GEN
T1 - Cone-based hypervolume indicators
T2 - 7th International Conference on Evolutionary Multi-Criterion Optimization, EMO 2013
AU - Emmerich, Michael
AU - Deutz, André
AU - Kruisselbrink, Johannes
AU - Shukla, Pradyumn Kumar
N1 - Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.
PY - 2013
Y1 - 2013
N2 - In this paper we discuss cone-based hypervolume indicators (CHI) that generalize the classical hypervolume indicator (HI) in Pareto optimization. A family of polyhedral cones with scalable opening angle γ is studied. These γ-cones can be efficiently constructed and have a number of favorable properties. It is shown that for γ-cones dominance can be checked efficiently and the CHI computation can be reduced to the computation of the HI in linear time with respect to the number of points μ in an approximation set. Besides, individual contributions to these can be computed using a similar transformation to the case of Pareto dominance cones. Furthermore, we present first results on theoretical properties of optimal μ-distributions of this indicator. It is shown that in two dimensions and for linear Pareto fronts the optimal μ-distribution has uniform gap. For general Pareto curves and γ approaching zero, it is proven that the optimal μ-distribution becomes equidistant in the Manhattan distance. An important implication of this theoretical result is that by replacing the classical hypervolume indicator by CHI with γ-cones in hypervolume-based algorithms, such as the SMS-EMOA, the distribution can be shifted from a distribution that is focussed more on the knee point region to a distribution that is uniformly distributed. This is illustrated by numerical examples in 2-D. Moreover, in 3-D a similar dependency on γ is observed.
AB - In this paper we discuss cone-based hypervolume indicators (CHI) that generalize the classical hypervolume indicator (HI) in Pareto optimization. A family of polyhedral cones with scalable opening angle γ is studied. These γ-cones can be efficiently constructed and have a number of favorable properties. It is shown that for γ-cones dominance can be checked efficiently and the CHI computation can be reduced to the computation of the HI in linear time with respect to the number of points μ in an approximation set. Besides, individual contributions to these can be computed using a similar transformation to the case of Pareto dominance cones. Furthermore, we present first results on theoretical properties of optimal μ-distributions of this indicator. It is shown that in two dimensions and for linear Pareto fronts the optimal μ-distribution has uniform gap. For general Pareto curves and γ approaching zero, it is proven that the optimal μ-distribution becomes equidistant in the Manhattan distance. An important implication of this theoretical result is that by replacing the classical hypervolume indicator by CHI with γ-cones in hypervolume-based algorithms, such as the SMS-EMOA, the distribution can be shifted from a distribution that is focussed more on the knee point region to a distribution that is uniformly distributed. This is illustrated by numerical examples in 2-D. Moreover, in 3-D a similar dependency on γ is observed.
KW - Complexity
KW - Cone-based Hypervolume Indicator
KW - Cone-orders
KW - Hypervolume Indicator
KW - Optimal μ-distribution
KW - SMS-EMOA
UR - http://www.scopus.com/inward/record.url?scp=84875500589&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-37140-0_12
DO - 10.1007/978-3-642-37140-0_12
M3 - Conference contribution
AN - SCOPUS:84875500589
SN - 9783642371394
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 111
EP - 127
BT - Evolutionary Multi-Criterion Optimization - 7th International Conference, EMO 2013, Proceedings
Y2 - 19 March 2013 through 22 March 2013
ER -