The hypervolume indicator is a set measure used in evolutionary multiobjective optimization to evaluate the performance of search algorithms and to guide the search. Multiobjective evolutionary algorithms using the hypervolume indicator transform multiobjective problems into single objective ones by searching for a finite set of solutions maximizing the corresponding hypervolume indicator. In this paper, we theoretically investigate how those optimal μ-distributions-finite sets of μ solutions maximizing the hypervolume indicator-are spread over the Pareto front of biobjective problems. This problem is of high importance for practical applications as these sets characterize the preferences that the hypervolume indicator encodes, i.e., which types of Pareto set approximations are favored. In particular, we tackle the question whether the hypervolume indicator is biased towards certain regions. For linear fronts we prove that the distribution is uniform with constant distance between two consecutive points. For general fronts where it is presumably impossible to characterize exactly the distribution, we derive a limit result when the number of points grows to infinity proving that the empirical density of points converges to a density proportional to the square root of the negative of the derivative of the front. Our analyses show that it is not the shape of the Pareto front but only its slope that determines how the points that maximize the hypervolume indicator are distributed. Experimental results illustrate that the limit density is a good approximation of the empirical density for small μ. Furthermore, we analyze the issue of where to place the reference point of the indicator such that the extremes of the front can be found if the hypervolume indicator is optimized. We derive an explicit lower bound (possibly infinite) ensuring the presence of the extremes in the optimal distribution. This result contradicts the common belief that the reference point has to be chosen close to the nadir point: for certain types of fronts, we show that no finite reference point allows to have the extremes in the optimal μ-distribution. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.  Categories and Subject Descriptors General Terms Theory Hypervolume indicator, multiobjective optimization The field of evolutionary multiobjective optimization is mainly concerned with the issue of approximating the Paretooptimal set, and various algorithms have been proposed for this purpose. In recent years, search algorithms based on the hypervolume indicator [27] , a set measure reflecting the volume enclosed by a Pareto front approximation and a reference set, have become increasingly popular, e.g., [16, 9, 14] . They overcome the problems arising with density-based multiobjective evolutionary algorithms [21] , since the hypervolume indicator guarantees strict monotonicity regarding Pareto dominance [11, 28] . Furthermore, recent extensions [23, 1] have broadened the applicability of this set measure with respect to preference articulation and high-dimensional objectives spaces. Hence, we expect that the scientific interest in the hypervolume indicator for search and performance assessment will grow further. These developments motivate why several researchers have been trying to better understand the hypervolume indicator from a theoretical perspective, e.g., [11, 28, 23] . One key result is that a set of solutions achieving the maximum hypervolume for a specific problem covers the entire Pareto front [11] . However, the corresponding set may contain an infinite number of solutions, while in practice usually bounded solution sets are considered. Limiting the number of points to, let us say μ, changes the situation: in this case, only a portion of the Pareto front can be covered, and how the points are distributed over the front depends on several aspects, in particular on the front characteristics and the choice of the reference set. The resulting placement of points reflects the bias of the hypervolume indicator, and this issue has not been investigated rigourosly so far. For instance, Zitzler and Thiele [27] indicated that, when optimizing the hypervolume in maximization problems, "convex regions may be preferred to concave regions", which is 87 also stated in [18] , whereas Deb et al. [7] argued that "[. . . ] the hyper-volume measure is biased towards the boundary solutions". Knowles and Corne observed that a local optimum of the hypervolume indicator "seems to be 'welldistributed" ' [16] which was also confirmed empirically [17, 9] . Some authors also addressed the choice of the reference set which usually contains just a single reference point. Knowles and Corne [17] demonstrated the impact of the reference point on the outcomes of selected multiobjective evolutionary algorithms based on an experimental study. Furthermore, rules of thumb exist, e.g., many authors recommend to use the corner of a space that is a little bit larger than the actual objective space as the reference point. Examples include the corner of a box 1% larger than the objective space in [15] or a box that is larger by an additive term of 1 than the extremal objective values obtained as in [3] . In various publications, the reference point is chosen as the nadir point of the investigated solution set, e.g., in [20, 19, 13] , while others recommend rescaling of the objective values everytime the hypervolume indicator is computed [25] . The above statements about the bias of the hypervolume indicator seem to be contradictory and up to now no theoretical results are available that could confirm or falsify any of these hypotheses. This paper provides a theory that addresses the bias issue for the biobjective case and thereby contributes to a theoretical understanding of the principles underlying the hypervolume indicator. To this end, we will first formally state the setting considered in this paper (Section 2) and present some fundamental results on the optimal distributions of points on the Pareto front (Section 3). Section 4 investigates the influence of a reference point on the placement of a finite set of points. Afterwards, we will mathematically derive optimal placements of points for Pareto fronts that can be described by a line (Section 5). Later, we extend these results to general front shapes assuming that the number of points of the distributions converges to infinity (Section 6) and provide heuristic methods to determine the optimal distributions of μ points (Section 7). Throughout this study, we consider a bicriterion optimization problem F : R d → R 2 consisting of two objectives (F1(x), F2(x)) = F(x) which are without loss of generality to be minimized. The optimal solutions (Pareto optima) for this problem are given by the minimal elements of the ordered set (R d , ) where stands for the weak Pareto dominance relation : We assume that the overall optimization goal is to approximate the set of Pareto optima-the Pareto set-by means of a solution set and that the hypervolume indicator [27] is used as a measure to quantify the quality of a solution set. The image of the Pareto set under F is called Pareto front or just front for short. The hypervolume indicator IH gives, roughly speaking, the volume of the objective subspace that is dominated by a solution set A ⊂ R d under consideration; it can be defined as follows on the basis of a reference set R ⊂ R 2 : where In the following, the common case of a single reference point r = (r1, r2) ∈ R 2 is considered only, i.e., R = {r}. It is known that the maximum hypervolume value possible is only achievable whenever the solution set A contains for each point z on the Pareto front at least one corresponding solution x ∈ A with F(x) = z, i.e., the image of A under F contains the Pareto front [11] ; however, this theoretical result assumes that A can contain any number of solutions, even infinitely many. In practice, the size of A is usually restricted, e.g., by the population size when an evolutionary algorithm is employed, and therefore the question is how the indicator IH influences the optimal selection of a finite number of μ solutions. For reasons of simplicity, we will consider only the objective vectors in the following and remark that in the biobjective case the Pareto front can be described in terms of a function f mapping the image of the Pareto set under F1 onto the image of the Pareto set under F2. We assume that the image of F1 is a closed interval [xmin, xmax] and define f as the function describing the Pareto front: An example is given in Figure 1 where a front is represented in terms of this function f (x). Since f represents the shape of the trade-off surface, we can conclude that, for minimization problems, f is strictly monotonically decreasing in [xmin, xmax] 1 . Furthermore, we only consider continuous functions f . Now, a set of μ points on the Pareto front is entirely determined by the x-coordinates respectively the F1 values of these points, here denoted as (x μ 1 , . . . , x μ μ ), and f . Without loss of generality, it is assumed that x If f is not strictly monotonically decreasing, we can find Pareto-optimal points (x1, f(x1)) and (x2, f(x2)) with x1, x2 ∈ [xmin, xmax] such that, without loss of generality, x1 < x2 and Figure 2 ). The hypervolume enclosed by these points can be, in analogy to Eq. 1, easily determined: it is the sum of rectangles of width ( Here, the hypervolume indicator Before we can characterize a set of points maximizing the hypervolume (i.e., Eq. 2), we need to be sure that the problem is well-defined, i.e., that there exists at least one set of points maximizing Eq. 2. The existence is proven in the next theorem assuming that f is continuous. 1 {y>f (x)} dydx where we prolong f for x > xmax by setting f (x) to the constant value f (xmax). Therefore, from the Mean Value Theorem there exists a set of μ points maximizing the hypervolume indicator. Note that the previous theorem states the existence but not the uniqueness, which is not true in general but will be for linear fronts (and certain choices of the reference point), as proven later in the paper. A set of points maximizing the hypervolume whose existence is proven in the previous theorem will be called an optimal μ-distribution. The associated value of the hypervolume is denoted as I This issue will be addressed in the following sections. This section presents preliminary results on optimal μ-distributions. The first result is about how the hypervolume associated with optimal μ-distributions increases with μ. This result is in particular useful for the proof of Corollary 1. Lemma 1. Let X ⊆ R and f : X → f (X) describe the Pareto front. Let μ1 and μ2 ∈ N with μ1 < μ2, then holds if X contains at least μ1 + 1 elements xi for which xi < r1 and f (xi) < r2 holds. Proof. To prove the lemma, it suffices to show the inequality for μ2 = μ1 + 1. Assume Dμ 1 = {x H . Since X contains at least μ1 + 1 elements, the set X\Dμ 1 is not empty and we can pick any xnew ∈ X\Dμ 1 that is not contained in the optimal μ1-distribution and for which f (xnew) is defined. Let xr := min{x|x ∈ Dμ 1 ∪ {r1}, x > xnew} be the closest element of Dμ 1 to the right of xnew (or r1 if xnew is larger than all elements of Dμ 1 ). Similarly, let f l := min{r2, {f (x)|x ∈ Dμ 1 , x < xnew}} be the function value of the closest element of Dμ 1 to the left of xnew (or r2 if xnew is smaller than all elements of Dμ 1 ). Then, all objective vectors within f(xnew)) are (weakly) dominated by the new point (xnew, f(xnew)) but are not dominated by any objective vector given by Dμ 1 . Furthermore, Hnew is not a null set (i.e. has a strictly positive measure) since xnew > xr and f l > f(xnew) which gives I μ 1 The next proposition is a central result of the paper stating that the x-coordinates of a set of μ points have to necessarily satisfy a recurrence relation (Eq. 3) in order to be an optimal μ-distribution. The key idea for the derivation is that, given three consecutive points on the Pareto front, moving the middle point will only affect that hypervolume contribution that is solely dedicated to this point (the joint hypervolume contributions remain fixed). Consequently, to belong to an optimal μ-distribution, the hypervolume component solely attributed to the middle point has to be maximal. Proposition 1. (Necessary condition for optimal μ-distributions) If f is continuous, differentiable and where f denotes the derivative of f , f (x For an optimal μ-distribution, each of the hypervolume contributions Hi has to be maximal with respect to x μ i since otherwise one would be able to increase I  Reorganizing the terms and setting H i (x μ i ) to zero, we obtain Eq. 3. The previous proposition implies that the points of optimal μ-distributions are linked with Eq. 3. In particular, the μ points are entirely determined as soon as x μ 1 and x μ 2 are set. Hence, finding the points of an optimal μ-distribution, i.e., maximizing the seemingly μ-dimensional function (2), turns out to be a two dimensional optimization problem. A first corollary from Lemma 1 and Proposition 1 is that an optimal point is either on an extreme of the Pareto front or cannot be a stationary point of f , i.e., a point where the derivative of f equals zero.  Optimal μ-distributions are the solutions of the maximization problem in Eq. 2 that depends on the choice of the reference point. We ask now the question of how the choice of the reference point is influencing optimal μ-distributions and investigate in particular whether there exists a choice of the reference point that implies that the extremes of the Pareto front are included in optimal μ-distributions. We prove in Theorem 2 (resp. Theorem 3) that if the derivative of the Pareto front at the left extreme (resp. right extreme) is infinite (resp. is zero), there is no choice of reference point that will allow that the left (resp. right) extreme of the front is included in optimal μ-distributions. This result contradicts the common belief that it is sufficient to choose the reference point slightly above and to the right to the nadir point to obtain the extremes. Moreover, when the derivative is finite at the left extreme and non-zero at the right extreme we prove an explicit lower bound (possibly infinite) for the choice of the reference point ensuring that any reference point above this lower bound guarantees that the extremes of the front are included in optimal μ-distributions. Recall that r = (r 1, r2) denotes the reference point and y = f (x) with x ∈ [xmin, xmax] represents the Pareto front where therefore (xmin, f(xmin)) and (xmax, f(xmax)) are the left and right extremal points. Since we want that all Paretooptimal solutions have a contribution to the hypervolume of the front in order to be possibly part of optimal μ-distributions, we assume that the reference point is dominated by all Paretooptimal solutions, i.e. r1 ≥ xmax and r2 ≥ f (xmin).  where the supremum in the previous equation is possibly infinite. When R2 is finite, the leftmost extremal point is contained in optimal μ-distributions if the reference point r = (r1, r2) is such that r2 is strictly larger than R2. Moreover, if limx→x min −f (x) = +∞, the left extremal point of the front is never included in optimal μ-distributions. For the sake of readability of the section, the proof of the above theorem, as well as the following proof are in the appendix. In a similar way, we derive the following theorem for including the rightmost Pareto-optimal point (xmax, f(xmax)) into optimal μ-distributions. If f (xmax) = 0, the right extremal point is never included in optimal μ-distributions. In the following example we illustrate how Theorem 2 and 3 can be used on test problems. and therefore According to Theorem 2, the leftmost Pareto-optimal point is never included in optimal μ-distributions. In addition, we have f (x) < 0 for all x ∈]0, 1]. Let us compute R1 defined in Eq. 5: From Theorem 3, we therefore know that the right extreme is included if r1 > 3. Table 1 shows the results also for other test problems. In this section, we have a closer look at linear Pareto fronts, i.e., fronts pictured as straight lines that can be formally defined as f : x ∈ [xmin, xmax] → αx + β where α < 0 and β ∈ R. For linear fronts with slope α = −1, Beume et al. [2] already proved that a set of μ points maximizes the hypervolume if and only if the points are equally spaced. However, their method does not allow to state where the leftmost and rightmost points have to be placed in order to maximize the hypervolume with respect to a certain reference point; furthermore, the approach cannot be generalized to arbitrary linear fronts with other slopes than −1. The same result of equal distances between points that maximize the hypervolume has been shown with a different technique in [10] for the front f (x) = 1 − x. Although the proof technique used in [10] could be generalized to arbitrary linear fronts, the provided result again only holds under the assumption that both the leftmost and rightmost point is fixed. Therefore, the question of where μ points have to be placed on linear fronts to maximize the hypervolume indicator without any assumption on the extreme points is still not answered. Within this section, we show for linear fronts of arbitrary slope, how optimal μ-distributions look like while making no assumptions on the positions of extreme solutions. First of all, we see as a direct consequence of Proposition 1 that the distance between two neighbored solutions is constant for arbitrary linear fronts: Proof. Applying Eq. 3 to f (x) = αx + β implies that . . , μ − 1 and therefore the distance between consecutive points of optimal μ-distributions is constant. Moreover, in case the reference point is not dominated by the extreme points of the Pareto front, i.e., r1 < xmax and r2 is set such that there exists (a unique) , there exists a unique optimal μ-distribution that can be determined exactly, see also the left plot of Fig. 4 : Proof. From Eq. 3 and the previous proof we know that  In the light of Section 4, the next issue we investigate is the choice of the reference point ensuring that optimal μ-distributions contain the extremes of the front. Since f (x) = α with 0 < α < +∞, we see that R2 and R1 defined in Theorems 2 and 3 are finite and thus we now that there exists a choice of reference point ensuring to obtain the extremes. The following theorem states the corresponding lower bounds for the reference point and specifies the optimal μ-distribution associated with such a choice. The right plot in Fig. 4 illustrates the optimal μ-distribution for μ = 4 points. [xmin, xmax] → αx + β with α < 0, β ∈ R and the reference point r = (r1, r2) is such that r1 is strictly larger than 2xmax−xmin and r2 is strictly larger than 2αxmin −αxmax+ β, there exists a unique optimal μ-distribution. This optimal μ-distribution includes the extremes of the front and for all i = 1, . . . , μ Proof. From Eq. 4, r2 strictly larger than i.e., r2 strictly larger than 2αxmin − αxmax + β, ensures the presence of xmin in optimal μ-distributions which yields x μ i = xmin for i = 1. From Eq. 5, r1 strictly larger than sup x∈]x min ,xmax] x + αx+β−αx min −β α , i.e., r1 strictly larger than sup x∈]x min ,xmax] 2x−xmin = 2xmax−xmin, ensures the presence of xmax in optimal μ-distributions and thus x μ i = xmax for i = μ. Using the same argument as in Theorem 5, we prove the uniqueness of optimal μ-distributions, the equal distances between the points and therefore Eq. 7. As pointed out in the beginning, we do not know in general whether optimal μ-distributions are unique or not. Theorem 5 and 6 are two settings where we can ensure the uniqueness. Except for simple fronts like the linear one, it is difficult (presumably impossible) to determine precisely optimal μ-distributions. However, in this section, we determine the distributions of points on arbitrary fronts, when their number goes to infinity. These distributions are going to be characterized in terms of density that can be used to approximate, for a finite μ, the percentage of points in a particular segment of the front. Moreover, it allows to quantify in a rigorous manner the bias of the hypervolume with respect to a given front. Our main result, stated in Theorem 7, is that the density is proportional to the square root of the negative of the derivative of the front. Although the results in this section hold for arbitrary Pareto front shapes that can be described by a continuous function g : x ∈ [xmin, xmax] → g(x) (lefthand plot of Fig. 5 ), we will, without loss of generality, consider only fronts f : x ∈ [0, xmax] → f (x) with f (xmax) = 0. The reason is that an arbitrary front shape g(x) can be easily transformed into the latter type by translating it, i.e., by introducing a new coordinate system x = x − xmin and y = y − g(xmax) with y = f (x ) describing the front in the new coordinate system (righthand plot of Fig. 5) . This translation is not affecting the hypervolume indicator which is computed relatively to the (also translated) reference point r = (r1 − xmin, r2 − g(xmax)). In addition to assuming f to be continuous within the entire domain [0, xmax], we assume that f is differentiable and that its derivative is a continuous function f defined in the interval ]0, xmax[. For a certain number of points μ, which later on will go to infinity, we would like to compute optimal μ-distributions, i.e., the positions of the μ points (x f (x)dx of constant value (lower left plot in Fig. 6 ), we see that minimizing (8) is equivalent to maximizing the hypervolume indicator We assume that the sequence converges-when μ goes to ∞-to a density δ(x) that is regular enough. Formally, the density in x ∈ [0, xmax] is defined as the limit of the number of points contained in a small interval [x, x + h[ normalized by the total number of points μ when both μ goes to ∞ and h to 0, i.e., In the following, we want to characterize the density associated with points x μ 1 , . . . , x μ μ that are maximizing the hypervolume indicator. As discussed above, maximizing the hypervolume is equivalent to minimizing Eq. 8. We here argue that for a fixed number of points μ, minimizing is also equivalent to maximizing the hypervolume such that we conjecture that the equivalence between minimizing Eμ and maximizing the hypervolume also holds for μ going to infinity. We now heuristically deduce 2 that the limit density of Eq. 9 will minimize the limit of Eμ in Eq. 10. Therefore, our proof consists of two steps: (1) compute the limit of Eμ when μ goes to ∞. This limit is going to be a function of a density δ. (2) Find the density δ that minimizes E(δ) := limμ→∞ Eμ. The first step therefore consists in computing the limit of Eμ. Let us first recall some definitions from integration theory. A function g : [0, xmax] → R is said to be integrable if xmax 0 |g(x)|dx is finite (usually denoted xmax 0 |g(x)|dx < +∞). The set of functions g that are integrable is a (Banach) vector space denoted L 1 (0, xmax). Another Banach vector space is the set of functions whose square is in L 1 (0, xmax), this space is denoted L 2 (0, xmax). From the Cauchy-Schwarz inequality, Heuristically deduce" means, we cannot prove it completely rigorously. Doing so would involve functional analysis concepts that are far beyond the scope of this paper. 3 The Cauchy-Schwarz inequality states that ( g 2 ) and therefore setting g = 1, For the sake of readability of the section, the proof of the previous lemma, as well as the following have been sent in the appendix. Note that the assumption in Eq. 11 characterizes the convergence of the μ points to the density and is needed in the proof. As explained before, the limit density of an optimal μ-distribution is minimizing E(δ). It remains therefore to find the density minimizing E(δ). This optimization problem is posed in a functional space, the Banach space L 2 (0, xmax) and is also a constraint problem since the density δ has to satisfy the constraint The constraint optimization problem (P) that needs to be solved is summarized in: Remark 1. In order to get the density δF for points of the front (x, f (x)) x∈ [0,xmax] and not on the projection onto the x-axis, one has to normalize the previous result by the norm of the tangent for points of the front, i.e., 1 + f (x) 2 . Therefore the density on the front is proportional to: As we have seen, the density follows as a limit result from the fact that the area between the attainment function of the solution set with μ points and the front itself (lower right plot of Fig. 6 ) has to be minimized and an optimal μ-distribution for finite points converges to the density when μ increases. It also follows that the number of points of an optimal μ-distribution with x-values in a certain interval [a, b] converges to b a δ(x)dx if μ goes to infinity. In the next section, we will show experimentally that the density can be used as an approximation of optimal μ-distributions not only for a large μ but also for reasonably small numbers of points. Besides plotting the density to understand the bias of the hypervolume indicator for specific fronts, the results above also allow a more general statement on the hypervolume indicator. From Theorem 7, we know that the density of points only depends on the slope of the front and not on whether the front is convex or concave in contrast to prevalent belief [26, 18] . density and the slope of the front. We observe that the density has its maximum for front parts where the tangent has a gradient of -45 • . Therefore, optimizing the hypervolume indicator stresses so-called knee-points-parts of the Pareto front decision makers believe to be interesting regions [5, 4, 6] . Extreme points are not generally preferred as claimed in [7] , since the density of points does not depend on the position on the front but only on the gradient at the respective point. The gradient varies for different locations on the front except for the linear case, so does the spacing between points. Hence, the distributions of points can differ highly from a well-distributed set of points suggested in [16] . Deriving the density of points allowed us to investigate the bias of the hypervolume in general as we have seen in the previous section, but the question remains what happens for a finite, especially small number of points. To answer this question, we carry out an experimental study using two local search strategies for approximating optimal μ-distributions for finite μ. These search strategies serve to (i) investigate optimal μ-distributions for small μ on various well-known test problems and (ii) show that optimal μ-distributions can be approximated accurately enough by the density already for reasonably small μ. Algorithms for finding optimal μ-distributions. To find an approximation of an optimal distribution of μ points, given by their x-values (x μ 1 , . . . , x μ μ ), we propose a simple hill climber (Algorithm 1) based on Eq. 3. It starts with an initial distribution that follows the distribution function of Theorem 7 (Line 2). Such a distribution is obtained by which ensures that the cumulated density between two adjacent points is constant. Additionally, the two points x μ 0 = xmin with f (x μ 0 ) = r2 and x μ μ+1 = r1 are added to simplify end while 12: return (x μ 1 , . . . , x μ μ ) 13: end procedure the handling of the extreme points. The resulting distribution of points follows the density function of Theorem 7 with all points in order from left to right, i.e., x After the points have been initialized, the contribution to the hypervolume is maximized for all points successively by placing each point according to Eq. 3 (Lines 6 to 8). This ensures that either the hypervolume is increased in the current step or the corresponding point is already placed optimally with respect to its neighbors. Since changing the position of one point might change other points that were previously considered as optimally placed to be suboptimally placed, the procedure is repeated as long as the improvement to the hypervolume indicator is larger than a user defined threshold ε (usually the precision of software implementation). Unfortunately, the optimal position of x μ i according to Eq. 3 cannot be determined analytically for some test problems, e.g., DTLZ2 [8] . In those cases, a modified version of the hill climbing procedure is used (see Algorithm 2). After creating an initial distribution of points as in Algorithm 1 (Line 2), the position of each point is again modified separately one after another. But in contrast to Algorithm 1, a new position x μ i is randomly determined by adding a Gaussian distributed value centered around the previous value. Initially, the variance σ 2 of this random variable is set to a large value such that big changes are attempted. For discontinuous front shapes (like DTLZ7 [8]) the position of the point is alternatively set to any value between xmin and xmax. This enables jumps of points to different parts of the front even in the later stage of the algorithms. The x-value x μ i is set to the new position x i μ and the current hypervolume v old is updated to v only if the hypervolume indicator increases; otherwise, the modified position is discarded (Lines 16 to 20). If for no point an improvement of the hypervolume could be realized, the variance σ 2 is decreased by 5%. As soon as the variance is smaller than ε (defined as in Algorithm 1), the current distribution (x μ 1 , . . . , x μ μ ) is returned. Note that both presented algorithms do not guarantee to find optimal μ-distributions. However, the experiments presented in the following show that the point distributions found by the two algorithms are converging to the density if μ goes to infinity like optimal μ-distributions theoretically converges to the density. Testing the algorithms using multiple random initial distributions instead of according to Eq. 14 within the InitialDist(·) function in both algorithms while σ > ε do 6: improvement ← false 7: J ← either 0 or 1 (with prob. 1/2 each) 10: if J is 1 then 11: always lead to the same final distribution, although the convergence turned out to be slower. This is a strong indicator that the distributions found are indeed good approximations of the optimal distributions of μ points. We would also like to mention that every general purpose search heuristic, e.g., an evolution strategy, could be used for approximating optimal μ-distributions. In preliminary experiments for example, we employed the CMA-ES of [12] to derive optimal μ-distributions. It turned out that the problem-specific algorithms are much faster than the CMA-ES. Even when using the representation as a twodimensional problem (see Sec. 3), the CMA-ES needed significantly more time than Algorithms 1 and 2 to derive similar hypervolume values. Nevertheless, the distributions found by CMA-ES where consistent with the distributions found by Algorithm 1 and Algorithm 2. Approximating optimal μ-distributions. With the help of the algorithms proposed above, we now investigate optimal μ-distributions for concrete test problems where the Pareto fronts are known. Figure 8 shows the best found μ-distribution for the test problems of the ZDT [24] and DTLZ [8] test function suites exemplary for μ = 50-more results can be found on the supplementary web page http://www. tik.ee.ethz.ch/sop/muDistributions. Furthermore, Table 2 provides the corresponding front shapes and derived densities. The optimal μ-distributions for ZDT1, ZDT2, and DTLZ1 have been approximated by Algorithm 1 whereas the μ-distributions for ZDT3, DTLZ2 and DTLZ7 have been computed with Algorithm 2 because Eq. 3 cannot be solved analytically or the front is not continuous. The reference point has been set to (15, 15) such that the extreme points are contained in optimal μ-distributions if possible. The experimentally derived optimal μ-distributions for μ = 50 qualitatively show the same results as the theoretically predicted density: more points can be found at front regions that have a gradient of −45 • , front parts that have a very high or very low gradient are less crowded. In addition, the equi-distance results for linear fronts (Theorems 5 and 6) can be observed for the linear DTLZ1 front. Convergence to the density. From Section 6 we know that the empirical density associated with optimal μ-distributions, i.e., the normalized histogram, converges to the density when μ goes to infinity and therefore that the limit density of Theorem 7 approximates the normalized histogram. Here, we investigate experimentally the quality of the approximation. To this end, we compute approximations of the optimal μ-distribution exemplary for the ZDT2 problem for μ = 10, μ = 100, and μ = 1, 000 obtained with Algorithm 1. The reference point has been set to (15, 15) as before. Figure 9 shows both the experimentally observed histogram of the μ points on the front and the comparison between the theoretically derived density and the obtained experimental approximation thereof. By visual inspection, we see that the histogram associated with the found μ-distributions converges quickly to the density and that for μ = 1, 000 points, the theoretically derived density gives already a sufficient description of the finite optimal μ-distribution. This study provides rigorous results on the question of how optimal Pareto front approximations of finite size μ look like when the hypervolume indicator is maximized. Most surprising might be the fact that the hypervolume indicator is insensitive to the way the front is bend (convex or concave) which contradicts previous assumptions [27, 18] . As we show, it is not the front shape itself but only the slope of the front that determines the distribution of points on the front. This implies that when optimizing the standard hypervolume indicator, an evenly distributed solution set can be obtained if and only if the front shape is a straight line. Furthermore, the question of how to choose the reference point in order to obtain extremes of the front, remaining unsolved for several years, can now be answered by our theoretical results. The explicit lower bound provided in our theorems will hopefully help practitioners. Although the results presented here hold for two objectives only, we assume that they generalize to an arbitrary number of objectives. The extension of the proposed mathematical framework is the subject of future research.
In this paper we notice that the most natural way to deal with the multiobjective TCP problem is represented by the hypervolume-based solvers since the AUC metrics used in the related literature for TCP represent a specific simplified version of the hypervolume metric REF .
Theory of the hypervolume indicator: optimal μ-distributions and the choice of the reference point
FOGA '09
Mathematics Computer Science