TY - GEN
T1 - A theoretical analysis of volume based pareto front approximations
AU - Shukla, Pradyumn Kumar
AU - Doll, Nadja
AU - Schmeck, Hartmut
N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.
PY - 2014
Y1 - 2014
N2 - Many multi-objective algorithms use volume based quality indicators to approximate the Pareto front. Amongst these, the hypervolume is the most widely used. The distribution of solution sets of finite size μ that maximize the hypervolume have been investigated theoretically. But nearly all results are limited to the bi-objective case. In this paper, many of these results are extended to higher dimensions and a theoretical analysis and characterization of optimal μ-distributions is done. We investigate monotonic Pareto curves that are embedded in three and higher dimensions that keep the property of the bi-objective case that only few points are determining the hypervolume contribution of a point. For finite μ, we consider the inuence of the choice of the reference point and determine sufficient conditions that assure the extreme points of the Pareto curves to be included in an optimal μ-distribution. We state conditions about the slope of the front that makes it impossible to include the extremes. Furthermore, we prove more specific results for three dimensional linear Pareto fronts. It is shown that the equispaced property of an optimal distribution for a line in two dimensions does not hold in higher dimensions. We additionally investigate hypervolume in general dimensions and problems with cone domination structures.
AB - Many multi-objective algorithms use volume based quality indicators to approximate the Pareto front. Amongst these, the hypervolume is the most widely used. The distribution of solution sets of finite size μ that maximize the hypervolume have been investigated theoretically. But nearly all results are limited to the bi-objective case. In this paper, many of these results are extended to higher dimensions and a theoretical analysis and characterization of optimal μ-distributions is done. We investigate monotonic Pareto curves that are embedded in three and higher dimensions that keep the property of the bi-objective case that only few points are determining the hypervolume contribution of a point. For finite μ, we consider the inuence of the choice of the reference point and determine sufficient conditions that assure the extreme points of the Pareto curves to be included in an optimal μ-distribution. We state conditions about the slope of the front that makes it impossible to include the extremes. Furthermore, we prove more specific results for three dimensional linear Pareto fronts. It is shown that the equispaced property of an optimal distribution for a line in two dimensions does not hold in higher dimensions. We additionally investigate hypervolume in general dimensions and problems with cone domination structures.
KW - Cone domination
KW - Hypervolume indicator
KW - Multi-objective optimization
UR - http://www.scopus.com/inward/record.url?scp=84905675468&partnerID=8YFLogxK
U2 - 10.1145/2576768.2598348
DO - 10.1145/2576768.2598348
M3 - Conference contribution
AN - SCOPUS:84905675468
SN - 9781450326629
T3 - GECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference
SP - 1415
EP - 1422
BT - GECCO 2014
PB - Association for Computing Machinery
T2 - 16th Genetic and Evolutionary Computation Conference, GECCO 2014
Y2 - 12 July 2014 through 16 July 2014
ER -