The Averaged Hausdorff Distances in Multi-Objective Optimization: A Review

Abstract

A brief but comprehensive review of the averaged Hausdorff distances that have recently been introduced as quality indicators in multi-objective optimization problems (MOPs) is presented. First, we introduce all the necessary preliminaries, definitions, and known properties of these distances in order to provide a stat-of-the-art overview of their behavior from a theoretical point of view. The presentation treats separately the definitions of the $(p,q)$-distances ${GD}_{p,q}$, ${IGD}_{p,q}$, and ${\Delta }_{p,q}$ for finite sets and their generalization for arbitrary measurable sets that covers as an important example the case of continuous sets. Among the presented results, we highlight the rigorous consideration of metric properties of these definitions, including a proof of the triangle inequality for distances between disjoint subsets when $p,q⩾1$, and the study of the behavior of associated indicators with respect to the notion of compliance to Pareto optimality. Illustration of these results in particular situations are also provided. Finally, we discuss a collection of examples and numerical results obtained for the discrete and continuous incarnations of these distances that allow for an evaluation of their usefulness in concrete situations and for some interesting conclusions at the end, justifying their use and further study.

1. Introduction

In many real-world applications, the problem of concurrent or simultaneous optimization of several objectives is an essential task known as a multi-objective optimization problem (MOP). One important problem in multi-objective optimization is to compute a suitable finite size approximation of the solution set of a given MOP, the so-called Pareto set and its image, the Pareto front.

The Hausdorff distance $d_H$ (e.g., Reference [1]) measures how far two subsets of a metric space are from each other. Due to its properties, it is frequently used in many research areas such as computer vision [2,3,4], fractal geometry [5], the numerical computation of attractors in dynamical systems [6,7,8], or convergence of multi-objective algorithms to the Pareto set/front of a given multi-objective optimization problem [9,10,11,12,13,14,15]. One possible drawback of the classical Hausdorff distance, however, is that it punishes single outliers which leads to inequitable performance evaluations in some cases. As one example, we mention here multi-objective evolutionary algorithms. On the one hand, such algorithms are known to be very effective in the (global) approximation of the Pareto set/front. On the other hand, it is also known that the final approximations (populations) may contain some outliers (e.g., Reference [16]). For such cases, the Hausdorff distance may indicate a “bad” match of population and Pareto set/front, while the approximation quality may be indeed “good”. To avoid exactly this problem, Schütze et al. introduced the averaged Hausdorff distance ${\Delta }_p$ in Reference [16], but the initial definition only works for finite approximations of the solution set and does not behave as a proper metric in the formal mathematical sense. In Reference [17], the indicator ${\Delta }_{p,q}$ has been proposed by the first two authors of this paper. ${\Delta }_{p,q}$ is an averaged Hausdorff distance that fixes the metric behavior of ${\Delta }_p$. Later, in Reference [18], a broader definition was given on metric measure spaces, suitable for the consideration of continuous approximations of the solution set. Moreover, this generalized indicator ${\Delta }_{p,q}$ preserves the nice metric properties of the initial finite case and reduces to it when using the standard discrete measure.

While the averaged Hausdorff distance has so far mostly been used for performance assessment of multi-objective evolutionary algorithms (using benchmark functions), it has also been used on MOPs coming from real-world problems including the multi-objective software next release problem [19], arc routing problems [20], power flow problems [21], engineering design problems [22], foreground detection [23], and contract design [24]. Several other indicators have also been proposed in the literature, like the hypervolume indicator or R indicators, each one with its own advantages and drawbacks, but their consideration is beyond the scope of this work. Information concerning other indicators can be found, e.g., in References [25,26,27].

The material reviewed in this work is based on recently published works [17,18,28]. The remainder of the document is organized as follows: in Section 2, we will briefly state the required background for MOPs and power means. In Section 3, we review the p-averaged Hausdorff distance ${\Delta }_p$. In Section 4, we will discuss its generalization, the $(p,q)$-averaged Hausdorff distance ${\Delta }_{p,q}$, explaining individually the finite and continuous cases. In Section 5, we will consider some aspects of the metric properties of ${\Delta }_p$ and ${\Delta }_{p,q}$. In Section 6, we study the Pareto compliance of the performance indicators related to ${\Delta }_p$ and ${\Delta }_{p,q}$. In Section 7, we will present some examples and numerical experiments. Finally, in Section 8, we will draw our conclusions and will discuss possible paths for future research in this direction.

2. Preliminaries

In this review, we introduce tools from a metric perspective that deal with two related contexts: distances between finite subsets of a metric space and distances between general measurable subsets of a metric measure space. The second context actually contains the first, but we deal separately with both of them, starting with the simpler setting of finite subsets before passing to the more general situation of arbitrary measurable sets that also contains the important special case of continuous sets. To emphasize each context, we use the convention that general sets will be denoted by X, Y, and Z, but when they are finite, the labels A, B, and C will be used.

2.1. Multi-Objective Optimization

First, we briefly present some basic aspects of multi-objective optimization problems (MOPs) required for the understanding of this paper. For a more thorough discussion, we refer the interested reader, e.g., to References [12,29,30].

A continuous MOP is rigorously formalized as the minimization of an appropriate function:

$$\underset{x\in Q}{min}F\left(x\right),$$

where F denotes a vector-valued function with components $f_i:Q\to \mathbb{R}$, for $i=1,\dots k$, called objective functions. Explicitly,

$$\begin{array}{cc}\hfill F:Q& ⟶{\mathbb{R}}^k,\hfill \\ \hfill x& ⟼F\left(x\right):=(f_1\left(x\right),\dots ,f_k\left(x\right)).\hfill \end{array}$$

The optimality of a candidate solution to a MOP depends on a dominance relation [31] given in terms of the partial order introduced below.

Definition 1.

For $x,y\in Q$, the partial Pareto ordering ⪯ associated with the MOP determined by F is defined as

$$x⪯yifandonlyif{f}_i\left(x\right)⩽f_i\left(y\right),foralli=1,\dots ,k.$$

For $x,y,z\in Q$ and $X,Y\subset Q$, the following notions of dominance (≺) and non-dominance (⊀) are standard in this context:

$$\begin{array}{cc}\hfill & x\mathit{is}\mathit{dominated}\mathit{by}y,\mathit{written}y\prec x\mathit{if}y⪯x\mathit{and}\mathit{F}\left(x\right)\ne F\left(y\right).\hfill \\ \hfill & z\mathit{is}\mathit{dominated}\mathit{by}X,\mathit{written}X⪯z\mathit{if}x⪯z\mathit{for}\mathit{some}x\in X,\mathit{otherwise}X⋠z.\hfill \\ \hfill & X\mathrm{is}\mathit{dominated}\mathit{by}Y,\mathit{written}Y⪯X\mathit{if}\forall x\in X\exists y\in Y\mathit{such}\mathit{that}y⪯x,\mathit{otherwise}Y⋠X.\hfill \end{array}$$

In addition, $x\in Q$ is called a Pareto-optimal point if it is nondominated, i.e., $\nexists y\in Q$ with $y\prec x$. Finally, the Pareto set $P\subset Q$ consists of all Pareto-optimal points and the Pareto front is defined as its image $F\left(P\right)\subset {\mathbb{R}}^k$.

MOPs commonly possess the important characteristic that, when mild smoothness conditions are fulfilled, the solution (or Pareto) set P and its image the Pareto front $F\left(P\right)\subset {\mathbb{R}}^k$ consist of d dimensional subsets for $d=k-1$ (or even less) when the problem involves k objective functions ([32]).

As an example, let us describe a simple unconstrained MOP [33,34] given by

$$\begin{array}{cc}\hfill f_1,\dots ,f_k& :{\mathbb{R}}^n⟶\mathbb{R}\hfill \\ \hfill f_i\left(x\right)& =\sum _{j=1}^n{(x_j-a_j^i)}^2,\hfill \end{array}$$

where $a^i=(a_1^i,\dots ,a_n^i)\in {\mathbb{R}}^n$ and $i=1,\dots ,k$. The $a^i$’s correspond to the minimizers of each quadratic objective $f_i$, and the Pareto set of this problem consists of a $(k-1)$ simplex containing all the $a^i$’s as vertices, i.e.,

$${\mathrm{simp}}_{k-1}:=simp(a^1,\dots ,a^k)=\left\{\sum _{i=1}^k{\mu }_i{a}^i:{\mu }_1,\dots ,{\mu }_k⩾0\mathrm{and}\sum _{i=1}^k{\mu }_i=1\right\}.$$

In the particular case when $n=1$, $k=2$, $a^1=0$, and $a^2=2$, the problem becomes

$$\begin{array}{cc}\hfill F& :\mathbb{R}⟶{\mathbb{R}}^2\hfill \\ \hfill F\left(x\right)& =(x^2,{(x-2)}^2).\hfill \end{array}$$

(1)

This is the so-called Schaffers problem [35]. Figure 1 illustrates the objectives $f_1$ and $f_2$, and the Pareto front $F\left(P\right)$ for this MOP. In this case, the Pareto set corresponds to $P=[0,2]$ and the Pareto front is a continuous convex curve in ${\mathbb{R}}^2$ joining $(0,4)$ with $(4,0)$.

In many real-world applications, MOPs arise naturally. As one example, in almost all scheduling problems (e.g., References [36,37,38,39,40,41]), the total execution time (make-span) is of primary interest. However, the consideration of this objective is in many cases not enough since other quantities such as the tardiness or the energy consumption also play an important role and can consequently, according to the given problem, also add objectives to the resulting multi-objective problem.

For the numerical treatment of MOPs, there exist already many established approaches. For instance, there are mathematical programming techniques [29,42], point-wise iterative methods that are capable of detecting single local solutions of a given MOP. Via use of a clever sequence of these resulting scalar objective optimization problems, a suitable finite size approximation of the entire Pareto front can be computed in certain cases [43,44,45,46]. Multi-objective continuation methods take advantage of the fact that the Pareto set at least locally forms a manifold [47,48,49,50,51,52]. Starting with an initial (local) solution, further candidates are computed along the Pareto set of the given MOP. All of these methods typically yield high convergence rates but are, in turn, of local nature. A possible alternative is given by set oriented methods such as subdivision and cell mapping techniques [53,54] and evolutionary algorithms [55,56,57,58,59] that are of global nature and are capable of computing a finite size approximation of the Pareto front in one single run.

2.2. Finite Power Means

A comprehensive reference on the theory and properties of means is given in Reference [60], where proofs of the statements presented here for finite power means and for integral power means in the following subsection can be found (see also Reference [18] for integral means).

For a finite set $A\subset [0,\infty )$ and a nonzero real p, the p-average or the p power mean of A is given by

$$\underset{a\in A}{{\mathcal{M}}^p}\left(a\right):={\left(\frac{1}{\left|A\right|}\sum _{a\in A}{a}^p\right)}^{\frac{1}{p}},$$

where $\left|A\right|$ denotes the cardinality of A. The simpler notation $\underset{}{{\mathcal{M}}^p}\left(A\right):=\underset{a\in A}{{\mathcal{M}}^p}\left(a\right)$ will also be employed. Moreover, in order to simplify the forthcoming expressions, we introduce the abbreviation

$$\overline{)\sum }_{a\in A}a\frac{1}{\left|A\right|}\sum _{a\in A}a$$

to denote the arithmetic mean of the elements of a finite set $A\subset {\mathbb{R}}_{⩾0}$.

It is well known that limit cases of power means recover familiar quantities, for example,

$$\underset{q\to 0}{lim}\underset{}{{\mathcal{M}}^p}\left(A\right)={\left(\prod _{a\in A}a\right)}^{\frac{1}{\left|A\right|\phantom{{}^2}}},$$

is the standard geometric mean of the elements of A. The special case $p=-1$ corresponds to the harmonic mean,

$$harm\left(A\right):=\underset{}{{\mathcal{M}}^{-1}}\left(A\right).$$

Moreover, the p-average of any finite set can also be defined for any p in the extended real line $\overline{\mathbb{R}}:=[-\infty ,\infty ]$ by taking appropriate limits.

$$\underset{q\to \infty }{lim}\underset{}{{\mathcal{M}}^p}\left(A\right)=max\left(A\right),\mathrm{and}\underset{q\to -\infty }{lim}\underset{}{{\mathcal{M}}^p}\left(A\right)=min\left(A\right).$$

Proposition 1.

Let A and B be finite subsets of $[0,\infty )$ and $p,q\in \overline{\mathbb{R}}$ be arbitrary constants. Then, the following properties hold for finite power means:

1.

$\underset{}{{\mathcal{M}}^p}\left(A\right)⩽\underset{}{{\mathcal{M}}^p}\left(B\right)$.

2.

For $p⩽q$: $\underset{}{{\mathcal{M}}^p}\left(A\right)⩽\underset{}{{\mathcal{M}}^q}\left(A\right)$.

3.

For a matrix of nonnegative elements $D=\left(d_{a,b}\right)$ with $a\in A$ and $b\in B$:

$$\underset{}{{\mathcal{M}}^p}\left(D\right):=\underset{a\in A}{{\mathcal{M}}^p}\left(\underset{b\in B}{{\mathcal{M}}^p}\left(d_{a,b}\right)\right)=\underset{b\in B}{{\mathcal{M}}^p}\left(\underset{a\in A}{{\mathcal{M}}^p}\left(d_{a,b}\right)\right).$$

4.

For $p⩾1$: $\underset{}{{\mathcal{M}}^p}\left(\{a+b\mid a\in A,b\in B\}\right)⩽\underset{}{{\mathcal{M}}^p}\left(A\right)+\underset{}{{\mathcal{M}}^p}\left(B\right).$

5.

For the harmonic mean: $harm\left(A\right)⩽\left|A\right|min\left(A\right)$.

2.3. Integral Power Means in Measure Spaces

In order to present this part with sufficient generality, let us denote by $(\mathcal{S},\mu )$ a measure space. Let $\mathfrak{M}\left(\mathcal{S}\right)$ be the $\sigma$ algebra of measurable subsets of $\mathcal{S}$ and ${\mathfrak{M}}_{<\infty }\left(\mathcal{S}\right)$ be the collection of those subsets with finite measure.

Now, we recall some fundamental properties of integral power means in this setting needed for the forthcoming sections. For $p\in \mathbb{R}\backslash \left\{0\right\}$ and a measurable function $f:X\subset \mathcal{S}\to [0,\infty )$ defined on a subset $X\in {\mathfrak{M}}_{<\infty }\left(\mathcal{S}\right)$, the p power mean or p-average of f over X is given by

$$\underset{x\in X}{{\mathcal{M}}^p}\left(f\left(x\right)\right):={\left(\frac{1}{\mu \left(X\right)}{\int }_{X}f{\left(x\right)}^{p}d\mu \right)}^{\frac{1}{p}}.$$

(2)

For convenience, rhs of Equation (2) will be denoted simply as

$$-{\int }_X{f}^p\mathrm{d}\mu \frac{1}{\left|X\right|}{\int }_{X}f{\left(x\right)}^p\mathrm{d}\mu ,$$

where $\left|X\right|:=\mu \left(X\right)$ refers in this context to the measure of X and not to its cardinality as in the finite case. For brevity, when the measure $\mu$ employed is clear, $\mathrm{d}\mu$ will be abbreviated by $dx$ to highlight the variable being integrated. The shorthand $\underset{}{{\mathcal{M}}^p}\left(f\left(X\right)\right):=\underset{x\in X}{{\mathcal{M}}^p}\left(f\left(x\right)\right)$ will also be employed.

For $p⩾1$, the integral p mean corresponds to $\underset{}{{\mathcal{M}}^p}\left(f\left(X\right)\right)={\left|X\right|}^{-\frac{1}{p}}{\parallel f\parallel }_p$, where ${\parallel ·\parallel }_p$ is the standard p norm of the Lebesgue space $L^p(X,\mu )$. The cases $p=\pm \infty$ can also be included by taking the limits $p\to \pm \infty$. In fact, since the essential supremum of the function f on X is ${\parallel f\parallel }_{\infty }={ess\; sup}_{x\in X}f\left(x\right)$, and when f is not identically zero its essential infimum is precisely ${\parallel 1/f\parallel }_{\infty }^{-1}={ess\; inf}_{x\in X}f\left(x\right)$; by calculating the limits, we obtain that

$$\begin{array}{cc}\hfill \underset{x\in X}{{\mathcal{M}}^{\infty }}\left(f\left(x\right)\right):=& \underset{p\to \infty }{lim}{\left(-{\int }_X{f}^p\mathrm{d}\mu \right)}^{\frac{1}{p}}={\parallel f\parallel }_{\infty },\hfill \end{array}$$

and similarly,

$$\begin{array}{cc}\hfill \underset{x\in X}{{\mathcal{M}}^{-\infty }}\left(f\left(x\right)\right):=& \underset{p\to -\infty }{lim}{\left(-{\int }_X{f}^p\mathrm{d}\mu \right)}^{\frac{1}{p}}=\parallel \frac{1}{f}{\parallel }_{\infty }^{-1}.\hfill \end{array}$$

Note that ${\parallel ·\parallel }_{\infty }$ corresponds to the norm of the space $L^{\infty }(X,\mu )$. For $p=0$, it is possible to define $\underset{}{{\mathcal{M}}^p}$ as the integral generalization of the notion of geometric mean, and it is given explicitly by

$$\underset{x\in X}{{\mathcal{M}}^0}\left(f\left(x\right)\right):=exp\left(-{\int }_{X}logf\mathrm{d}\mu \right).$$

Proposition 2.

For subsets $X,Y\in {\mathfrak{M}}_{<\infty }\left({\mathbb{R}}^k\right)$, nonnegative measurable functions $f,g:X\to [0,\infty )$, and any product-measurable function $d:X\times Y\to [0,\infty )$, the integral power mean $\underset{}{{\mathcal{M}}^p}$ satisfies that

1.

For $p\in \overline{\mathbb{R}}$, $k\in [0,\infty )$: $\underset{x\in X}{{\mathcal{M}}^p}\left(k\right)=k$ and $\underset{x\in X}{{\mathcal{M}}^p}\left(kf\left(x\right)\right)=k\underset{x\in X}{{\mathcal{M}}^p}\left(f\left(x\right)\right)$.

2.

For $p\in \overline{\mathbb{R}}$: $\underset{x\in X}{{\mathcal{M}}^p}\left(\underset{y\in Y}{{\mathcal{M}}^p}\left(d(x,y)\right)\right)=\underset{y\in Y}{{\mathcal{M}}^p}\left(\underset{x\in X}{{\mathcal{M}}^p}\left(d(x,y)\right)\right)$.

3.

For $p\in [1,\infty ]$: $\underset{x\in X}{{\mathcal{M}}^p}(f\left(x\right)+g\left(x\right))⩽\underset{x\in X}{{\mathcal{M}}^p}\left(f\left(x\right)\right)+\underset{x\in X}{{\mathcal{M}}^p}\left(g\left(x\right)\right)$.

4.

For $p\in \overline{\mathbb{R}}$ and $f⩽g$: $\underset{x\in X}{{\mathcal{M}}^p}\left(f\left(x\right)\right)⩽\underset{x\in X}{{\mathcal{M}}^p}\left(g\left(x\right)\right)$.

5.

For $p,q\in [0,\infty ]$ with $p⩽q$: $\underset{x\in X}{{\mathcal{M}}^p}\left(f\left(x\right)\right)⩽\underset{x\in X}{{\mathcal{M}}^q}\left(f\left(x\right)\right)$.

3. The p-Averaged Hausdorff Distance

When trying to measure the distance between subsets of Euclidean space or even an arbitrary metric space, a natural choice is the well-known Hausdorff distance $d_H$ that is extensively employed in many different contexts. However, its use is of limited practical value to measure the distance to the Pareto set/front in typical MOPs, such as stochastic search methods implemented by an evolutionary algorithm. This is due to the fact that these algorithms may produce a set of outliers that can be heavily punished by $d_H$. As a partial remedy, the use of an averaged Hausdorff distance ${\Delta }_p$ was first proposed in Reference [16] to replace $d_H$.

Let $d:\mathcal{S}\times \mathcal{S}\to [0,\infty )$ denote a distance function on a metric space $\mathcal{S}$ for which the standard properties of the identity of indiscernibles, nonnegativity, symmetry, and subadditivity (more commonly known as the triangle inequality) are satisfied.

Definition 2.

Given a point $x_0\in \mathcal{S}$ and subsets $X,Y\subset \mathcal{S}$, we have

1.

A pointwise distance to sets: $d(x_0,X):=inf\{d(x_0,x)\mid x\in X\}$.

2.

A pre-distance between sets: $d(Y,X):=sup\left\{d\right(y,X)\mid y\in Y\}$.

3.

The Hausdorff distance between sets: $d_H(X,Y):=max\left\{d\right(X,Y),d(Y,X\left)\right\}$.

For simplicity, throughout the text, the metric d can be assumed to be the standard Euclidean distance $d(x,y):=\parallel x-y\parallel$ induced on some $\mathcal{S}\subset {\mathbb{R}}^k$ by the Euclidean 2 norm of ${\mathbb{R}}^k$, but the theory carries over to any general metric space $(\mathcal{S},d)$.

Definition 3.

Let $p\in \mathbb{N}$. For finite subsets $A,B\subset \mathcal{S}$, their (modified) p generational distance is

$${GD}_p(A,B):={\left(\frac{1}{\left|A\right|}\sum _{a\in A}d{(a,B)}^p\right)}^{\frac{1}{p}},$$

and their (modified) p inverted generational distance is

$${IGD}_p(A,B):={\left(\frac{1}{\left|B\right|}\sum _{b\in B}d{(b,A)}^p\right)}^{\frac{1}{p}}.$$

From them, the p averaged Hausdorff distance is obtained by taking the maximum

$${\Delta }_p(A,B):=max\{{GD}_p(A,B),{IGD}_p(A,B)\}.$$

The indicators ${GD}_p$ and ${IGD}_p$ in Definition 3 correspond to simple adjustments to the definitions of the generational distance [61] and the inverted generational distance [62].

The standard Hausdorff distance is recoverable from ${\Delta }_p$ by taking the limit ${lim}_{p\to \infty }{\Delta }_p=d_H$, but for any finite value of p, the distance ${\Delta }_p$ is obtained from standard p power means of all the distances employed to calculate the supremum in part 2 of Definition 2, which is needed to define $d_H$.

The advantage of using ${\Delta }_p$ as an indicator is that it does not immediately disqualify a few outliers in a candidate set, contrary to what $d_H$ does and that, among the possible configurations of (finite) candidate solutions to a MOP, it assigns lesser distances to the Pareto front to those solutions appearing evenly spread along its whole domain (see, e.g., Reference [63]). The behavior of ${\Delta }_p$ as a quality indicator is studied, e.g., in References [16,28], and it corresponds to the particular case $q\to -\infty$ of the results for general $(p,q)$-indicators presented in Section 6.

Concerning its metric properties, ${\Delta }_p$ has the drawback of not being a proper metric in the usual sense because for any non-unit set $A\subset \mathcal{S}$ the distance ${\Delta }_p(A,A)>0$. This problem will be fixed in the following section with a simple modification. Nevertheless, independently from that, for a positive number p, the distance ${\Delta }_p$ does not satisfy the triangle inequality but only a weaker version of it. Indeed, as a consequence of Corollary 3, we have that

$${\Delta }_p(A,C)⩽N^{\alpha }\left({\Delta }_p(A,C)+{\Delta }_p(B,C)\right),$$

where $N=max\left\{\right|A|,|B|,|C\left|\right\}⩾1$ and $\alpha =1/p$.

For further details concerning ${\Delta }_p$, its properties, and its relation to other indicators, the reader can consult, e.g., References [16,63].

4. The (p,q)-Averaged Hausdorff Distance

To better evaluate the optimality of a certain candidate set to approximate the Pareto set/front of a MOP, several generalizations of the averaged Hausdorff distance ${\Delta }_p$ have been recently introduced.

4.1. (p,q)-Distances between Finite Sets

Definition 4.

For $p,q\in \mathbb{R}\backslash \left\{0\right\}$, the generational $(p,q)$-distance ${GD}_{p,q}(A,B)$ between two finite subsets $A,B\subset \mathcal{S}$ is given by

$${GD}_{p,q}(A,B):={\left(\overline{)\sum }_{a\in A}{\left(\overline{)\sum }_{b\in B}d{(a,b)}^q\right)}^{\frac{p}{q}}\right)}^{\frac{1}{p}}.$$

The distance ${GD}_{p,q}(A,B)$ can be extended for values of $p=0$ or $q=0$, by taking the limits $p\to 0$ or $q\to 0$, respectively. In such cases, properties of finite power means suggest the following definitions:

$$\begin{array}{cc}\hfill {GD}_{p,0}(A,B):=& {\displaystyle {\left(\overline{)\sum }_{a\in A}{\left(\prod _{b\in B}d(a,b)\right)}^{\frac{p}{\left|B\right|\phantom{{}^2}}}\right)}^{\frac{1}{p}},\mathrm{when}p\ne 0,}\hfill \\ \hfill {GD}_{0,q}(A,B):=& {\displaystyle {\left(\prod _{a\in A}{\left(\overline{)\sum }_{b\in B}d{(a,b)}^q\right)}^{\frac{1}{q}}\right)}^{\frac{1}{\left|A\right|\phantom{{}^2}}},\mathrm{when}q\ne 0,\mathrm{and}}\hfill \\ \hfill {GD}_{0,0}(A,B):=& {\displaystyle {\left(\prod _{a\in A}{\left(\prod _{b\in B}d(a,b)\right)}^{\frac{1}{\left|B\right|\phantom{{}^2}}}\right)}^{\frac{1}{\left|A\right|\phantom{{}^2}}}\mathrm{if}p=q=0.}\hfill \end{array}$$

We can also calculate ${GD}_{p,q}$ when $p\to \pm \infty$ or $q\to \pm \infty$ by changing the corresponding sum with a minimum or a maximum according to the case. In particular, we have the nice relation

$$\underset{q\to -\infty }{lim}{GD}_{p,q}(A,B)={GD}_p(A,B).$$

(3)

Note that the definition of ${GD}_{p,q}$ has two drawbacks, namely ${GD}_{p,q}(A,B)$ does not necessarily vanish if $A=B$ and in general ${GD}_{p,q}(A,B)\ne {GD}_{p,q}(B,A)$, hence it does not define a proper metric. In order to get one, a slight modification is needed.

Definition 5.

Let $p,q\in \mathbb{R}\backslash \left\{0\right\}$. For finite subsets $A,B\subset \mathcal{S}$, their$(p,q)$-averaged Hausdorff distance is

$${\Delta }_{p,q}(A,B)max\{{GD}_{p,q}(A,B\backslash A),{GD}_{p,q}(B,A\backslash B)\}.$$

Notice that ${GD}_p(A,B)={GD}_p(A,B\backslash A)$ when $A\cap B=⌀$, thus using Equation (3) and Definition 5, we easily obtain

$$\underset{q\to -\infty }{lim}{\Delta }_{p,q}(A,B)={\Delta }_p(A,B).$$

In this way, for finite and disjoint sets, the indicator ${\Delta }_{p,q}$ is a generalization of ${\Delta }_p$. Similarly to the relation

$${GD}_p(A,B)={\left|A\right|}^{-\frac{1}{p}}{\parallel D_{AB}\parallel }_p,$$

between the ${GD}_p(A,B)$ and the matrix ${\ell }_p$ norm $\parallel D_{AB}{\parallel }_p$ of the distance matrix $D_{AB}:={\left[d(a,b)\right]}_{a,b}$ for $a\in A$ and $b\in B$, we also have the following relation between the $(p,q)$-generational distance ${GD}_{p,q}(A,B)$ and the matrix ${\ell }_{p,q}$ norm $\parallel D_{AB}{\parallel }_{p,q}$, where the definition of the latter is precisely that of ${GD}_{p,q}$ but replacing all the normalized sums $\overline{)\sum }$ by standard ones ∑ (see, e.g., Reference [64]):

$$\begin{array}{cc}\hfill {GD}_{p,q}(A,B)& =\underset{a\in A}{{\mathcal{M}}^p}\left(\underset{b\in B}{{\mathcal{M}}^q}\left(d(a,b)\right)\right)={\left|A\right|}^{-\frac{1}{p}}{\left|B\right|}^{-\frac{1}{q}}{\parallel D_{AB}\parallel }_{p,q}.\hfill \end{array}$$

A useful property of the distance ${\Delta }_{p,q}$ is that the parameters can be adjusted independently to achieve some desired spread of the archives by choosing an appropriate q and that they can be located with custom closeness to the Pareto front of a MOP by an adequate choice of p.

4.2. $(p,q)$-Distances between Measurable Sets

With the aid of Proposition 2, the results of the previous section can be generalized to subsets of a metric space $(\mathcal{S},d)$ endowed with an appropriate measure $\mu$. For concreteness, $\mathcal{S}$ can be taken to be a subset of ${\mathbb{R}}^k$ carrying the metric induced from the Euclidean metric of ${\mathbb{R}}^k$ and endowed with an appropriate non-null measure $\mu$. Notice that, in our intended applications, $\mu$ will not be the restriction of the standard Lebesgue measure of ${\mathbb{R}}^k$ to $\mathcal{S}$ for the simple reason that it can easily vanish as it happens on any hypersurface or lower dimensional subsets of ${\mathbb{R}}^k$. In this case, a lower dimensional measure is needed and alternatives like the Hausdorff measure on $\mathcal{S}$ can be used, since it gives rise to the standard notion of d dimensional volume for d submanifolds of ${\mathbb{R}}^k$. When these submanifolds are parametrized by functions from subsets of ${\mathbb{R}}^d$, the same volume will be obtained by a change of variable formulae from the standard Lebesgue measure on those subsets of ${\mathbb{R}}^d$.

A very important observation in this context is that any set-theoretic relation obtained from measure-related calculations needs to be understood to hold almost everywhere (a.e.). Therefore, for $X,Y\in {\mathfrak{M}}_{<\infty }\left(\mathcal{S}\right)$, the statements $X=Y$ or $X\subset Y$ mean that the relations hold a.e., i.e., $\mu \{X\ne Y\}=0$ or $\mu \{X⊈Y\}=0$, respectively. In other words, in this setting, we will always identify $X\in {\mathfrak{M}}_{<\infty }\left(\mathcal{S}\right)$ with its equivalence class $\left[X\right]:=\{Y\mid X=Y,a.e.\}$. This means that those classes will be regarded as the elements of ${\mathfrak{M}}_{<\infty }\left(\mathcal{S}\right)$, removing the need to carry the abbreviation a.e. all the time. Henceforth, to simplify complicated formulae, $d(x,y)$ will be shortened to $d_{x,y}$.

Definition 6.

Let $p,q\in \mathbb{R}\backslash \left\{0\right\}$. For finite-measure subsets $X,Y\in {\mathfrak{M}}_{<\infty }\left(\mathcal{S}\right)$, their generational $(p,q)$-distance is given by

$${GD}_{p,q}(X,Y)\underset{x\in X}{{\mathcal{M}}^p}\left(\underset{y\in Y}{{\mathcal{M}}^q}\left(d_{x,y}\right)\right)={\left(-{\int }_X{\left(-{\int }_Y{d}_{x,y}^{q}dy\right)}^{\frac{p}{q}}dx\right)}^{\frac{1}{p}}.$$

The cases $p<0$ or $q<0$ are well defined only if X and Y are disjoint subsets.

Similarly to the finite case, ${GD}_{p,q}$ can be extended to values of $p,q\in \overline{\mathbb{R}}$, but there are two drawbacks: ${GD}_{p,q}(X,X)=0$ only if X is a unit-set or singleton, and ${GD}_{p,q}(X,Y)$ can differ from ${GD}_{p,q}(Y,X)$. To fix this undesirable behavior, we repeat the strategy used in the finite case as follows.

Definition 7.

Let $p,q\in \mathbb{R}\backslash \left\{0\right\}$. For finite-measure subsets $X,Y\in {\mathfrak{M}}_{<\infty }\left(\mathcal{S}\right)$, their $(p,q)$-averaged Hausdorff distance is given by

$${\Delta }_{p,q}(X,Y)max\{{GD}_{p,q}(X,Y\backslash X),{GD}_{p,q}(Y,X\backslash Y)\}.$$

Remark 1.

In general, the $(p,q)$-distances are maps: ${\mathfrak{M}}_{<\infty }\left(\mathcal{S}\right)\times {\mathfrak{M}}_{<\infty }\left(\mathcal{S}\right)\to [0,\infty )$. On the collection of finite subsets of $\mathcal{S}$, the standard counting measure can be taken as the underlying one needed for these measure-theoretic notions of ${GD}_{p,q}$ and ${\Delta }_{p,q}$, and in this case, these distances become precisely the finite-case distances given in Definitions 4 and 5.

Remark 2.

For disjoint subsets X and Y, Definition 5 in the finite case and Definition 7 above in the measurable case reduce to the simpler form

$${\Delta }_{p,q}(X,Y):=max\{{GD}_{p,q}(X,Y),{GD}_{p,q}(Y,X)\},$$

which is the one we will actually use in most situations. The more general definition for non-disjoint subsets is given with the purpose that the distance so-defined changes continuously as one set approaches the other until their distance vanishes. In other words, the general definition allows the distance to become a continuous function with respect to the metric topology that it determines. Nevertheless, for practical purposes dealing with applications and for most of the results presented below, the simpler definition between disjoint subsets suffices.

5. Metric Properties

To explain some of the terminology used in this section, we recall to the reader that the standard triangle inequality for a distance function $d:\mathcal{S}\times \mathcal{S}\to [0,\infty )$ is usually weakened in two different but related ways by postulating the existence of a constant $C>0$ such that, for any points $x,y,z\in \mathcal{S}$, one of the following conditions hold:

• The C relaxed triangle inequality: $d(x,z)⩽C\left(d\right(x,y)+d(y,z\left)\right)$.
• The C inframetric inequality: $d(x,z)⩽Cmax\left\{d\right(x,y),d(y,z\left)\right\}$.

Since the second condition implies the first one by using the very same constant $C>0$ and, reciprocally, the C relaxed triangle inequality implies the $2C$ inframetric one, both conditions are equivalent for an appropriate choice of constants. A semimetric satisfying any one of these conditions will be simply called an inframetric.

For arbitrary measurable sets in $\mathcal{S}$, the following results summarize the metric properties of ${GD}_{p,q}$ and ${\Delta }_{p,q}$. Using the counting measure, these properties also apply to finite sets. For more details, see Reference [17] in the finite case and Reference [18] in the generalized measure-theoretic context.

Theorem 1.

For $p,q\in [1,\infty ]$, the generational $(p,q)$-distance ${GD}_{p,q}$ is subadditive in ${\mathfrak{M}}_{<\infty }\left(\mathcal{S}\right)$, i.e., for any $X,Y,Z\in {\mathfrak{M}}_{<\infty }\left(\mathcal{S}\right)$, the triangle inequality holds true:

$${GD}_{p,q}(X,Z)⩽{GD}_{p,q}(X,Y)+{GD}_{p,q}(Y,Z).$$

Proof. 

The proof follows easily by simple steps using the properties in Proposition 2. We start from the standard triangle inequality for $d(·,·)$:

$$d_{x,z}⩽d_{x,y}+d_{y,z}(x\in X,y\in Y,z\in Z),$$

taking at both sides the q-average over Z and using 1–3 of Proposition 2 to arrive at

$$\begin{array}{c}\hfill \underset{z\in Z}{{\mathcal{M}}^q}\left(d_{x,z}\right)⩽\underset{z\in Z}{{\mathcal{M}}^q}(d_{x,y}+d_{y,z})⩽\underset{z\in Z}{{\mathcal{M}}^q}\left(d_{x,y}\right)+\underset{z\in Z}{{\mathcal{M}}^q}\left(d_{y,z}\right)=d_{x,y}+\underset{z\in Z}{{\mathcal{M}}^q}\left(d_{y,z}\right).\end{array}$$

(4)

Now, there are two independent cases for the parameters $p,q\in [1,\infty )$. We explain here only the case $p⩽q$, but the case $q<p$ follows by similar arguments; see Thm. 2 in Reference [18]. Calculating the p-average over X at both sides of Equation (4) and using 1, 3, and 5 of Proposition 2, we get

$$\underset{x\in X}{{\mathcal{M}}^p}\left(\underset{z\in Z}{{\mathcal{M}}^q}\left(d_{x,z}\right)\right)⩽\underset{x\in X}{{\mathcal{M}}^p}\left(d_{x,y}+\underset{z\in Z}{{\mathcal{M}}^q}\left(d_{y,z}\right)\right)=\underset{x\in X}{{\mathcal{M}}^p}\left(d_{x,y}\right)+\underset{z\in Z}{{\mathcal{M}}^q}\left(d_{y,z}\right).$$

(5)

Since the lhs of Equation (5) is ${GD}_{p,q}(X,Z)$, after a further p-average over Y at both sides of Equation (5) and parts 1, 3, and 5 of Proposition 2, we obtain

$$\begin{array}{cc}\hfill {GD}_{p,q}(X,Z)& ⩽\underset{y\in Y}{{\mathcal{M}}^p}\left(\underset{x\in X}{{\mathcal{M}}^p}\left(d_{x,y}\right)+\underset{z\in Z}{{\mathcal{M}}^q}\left(d_{y,z}\right)\right)=\underset{y\in Y}{{\mathcal{M}}^p}\left(\underset{x\in X}{{\mathcal{M}}^p}\left(d_{x,y}\right)\right)+{GD}_{p,q}(Y,Z).\hfill \end{array}$$

But from 2, 4, and 5 of Proposition 2, the first term at the rhs above satisfies

$$\underset{y\in Y}{{\mathcal{M}}^p}\left(\underset{x\in X}{{\mathcal{M}}^p}\left(d_{x,y}\right)\right)=\underset{x\in X}{{\mathcal{M}}^p}\left(\underset{y\in Y}{{\mathcal{M}}^p}\left(d_{x,y}\right)\right)⩽\underset{x\in X}{{\mathcal{M}}^p}\left(\underset{y\in Y}{{\mathcal{M}}^q}\left(d_{x,y}\right)\right)={GD}_{p,q}(X,Y).\hspace{1em}\square$$

Corollary 1.

If $p,q\in \mathbb{R}\backslash \left\{0\right\}$, the $(p,q)$-averaged Hausdorff distance ${\Delta }_{p,q}$ is a semimetric on the space ${\mathfrak{M}}_{<\infty }\left(\mathcal{S}\right)$ of finite-measure subsets of $\mathcal{S}$. Furthermore, if $p,q\in [1,\infty )$ the distance ${\Delta }_{p,q}$ behaves as a proper metric when it is restricted to disjoint subsets of ${\mathfrak{M}}_{<\infty }\left(\mathcal{S}\right)$.

Proof. 

From Definition 7, we obtain the relations ${\Delta }_{p,q}(·,·)⩾0$ and ${\Delta }_{p,q}(X,Y)={\Delta }_{p,q}(Y,X)$ for any $X,Y\in {\mathfrak{M}}_{<\infty }\left(\mathcal{S}\right)$ and all $p,q\in \mathbb{R}\backslash \left\{0\right\}$. Moreover, from Definition 6, it follows that ${GD}_{p,q}(X,Y\backslash X)=0$ if and only if $X=⌀$ or $Y\subseteq X$ (hence, $Y\backslash X=⌀$). Therefore, for $X,Y\ne ⌀$,

$${\Delta }_{p,q}(X,Y)=0⟺X=Y,$$

i.e., ${\Delta }_{p,q}$ is a semimetric on the collection of finite-measure subsets ${\mathfrak{M}}_{<\infty }\left(\mathcal{S}\right)$. Finally, for disjoint X and Y, it is clear that ${GD}_{p,q}(X,Y\backslash X)=G{D}_{p,q}(X,Y)$; thus, by Theorem 1, the triangle inequality holds for both arguments inside the maximum that defines ${\Delta }_{p,q}$ when $p,q\in [1,\infty )$. This implies that the triangle inequality is also valid for ${\Delta }_{p,q}$. □

Theorem 2.

Let $X,Y,Z\in {\mathfrak{M}}_{<\infty }\left(\mathcal{S}\right)$ be subsets admitting positive constants $r<R$ such that $r⩽d_{u,v}⩽R$ for any $u\in X\cup Y$ and $v\in Y\cup Z$. Then, for all $p,q\in \mathbb{R}\backslash \left\{0\right\}$, $\left|p\right|,\left|q\right|⩾1$ and at least one of them negative a relaxed triangle inequality holds for ${GD}_{p,q}$, namely

$${GD}_{p,q}(X,Z)⩽\frac{R^2}{r^2}\left({GD}_{p,q}(X,Y)+{GD}_{p,q}(Y,Z)\right).$$

Proof. 

Step 1: Let $p\in \mathbb{R}\backslash \left\{0\right\}$, and suppose that $q<0$. We will prove that

$${GD}_{p,\left|q\right|}(X,Y)⩽\frac{R}{r}{GD}_{p,q}(X,Y).$$

(6)

For all $x\in X$ and $y,z\in Y$, we have $\frac{r}{R}⩽\frac{d_{x,y}}{d_{x,z}}⩽\frac{R}{r}$. Thus,

$$\frac{R}{r}⩾{\left(-{\int }_Y-{\int }_Y{\left[\frac{d_{x,y}}{d_{x,z}}\right]}^{\left|q\right|}\mathrm{d}y\mathrm{d}z\right)}^{\frac{1}{\left|q\right|}}={\left(-{\int }_Y{d}_{x,y}^{\left|q\right|}\mathrm{d}y\right)}^{\frac{1}{\left|q\right|}}{\left(-{\int }_Y{d}_{x,z}^{-\left|q\right|}\mathrm{d}z\right)}^{\frac{1}{\left|q\right|}}.$$

Since $q=-\left|q\right|$, this means that $\underset{y\in Y}{{\mathcal{M}}^{\left|q\right|}}\left(d_{x,y}\right)⩽\frac{R}{r}\underset{y\in Y}{{\mathcal{M}}^q}\left(d_{x,y}\right)$. Taking the p-average $\underset{x\in X}{{\mathcal{M}}^p}$ at both sides and from 1 and 4 of Proposition 2, we find $\underset{x\in X}{{\mathcal{M}}^p}\left(\underset{y\in Y}{{\mathcal{M}}^{\left|q\right|}}\left(d_{x,y}\right)\right)⩽\frac{R}{r}\underset{x\in X}{{\mathcal{M}}^p}\left(\underset{y\in Y}{{\mathcal{M}}^q}\left(d_{x,y}\right)\right)$, which is exactly Equation (6).

Step 2: Now, for $q\in \mathbb{R}\backslash \left\{0\right\}$ and $p<0$, we will prove that

$${GD}_{\left|p\right|,q}(X,Y)⩽\frac{R}{r}{GD}_{p,q}(X,Y).$$

(7)

By assumption, we have $\frac{r}{R}⩽\frac{d_{x,y}}{d_{u,y}}⩽\frac{R}{r}$ for any $y\in Y$ and all $x,u\in X$. Similarly as before and using 1 and 4 of Proposition 2, we conclude from the rhs part that $\underset{y\in Y}{{\mathcal{M}}^q}\left(d_{x,y}\right)⩽\frac{R}{r}\underset{y\in Y}{{\mathcal{M}}^q}\left(d_{u,y}\right)$. However, since $p=-\left|p\right|$, after taking a p-average of the quotient of means, it follows from

$$\begin{array}{c}\hfill {\left({-\int }_X{\left(\underset{y\in Y}{{\mathcal{M}}^q}\left(d_{x,y}\right)\right)}^{\left|p\right|}dx\right)}^{\frac{1}{\left|p\right|}}{\left({-\int }_X{\left(\underset{y\in Y}{{\mathcal{M}}^q}\left(d_{u,y}\right)\right)}^{p}du\right)}^{\frac{1}{\left|p\right|}}={\left({-\int }_X{-\int }_X{\left[\frac{\underset{y\in Y}{{\mathcal{M}}^q}\left(d_{x,y}\right)}{\underset{y\in Y}{{\mathcal{M}}^q}\left(d_{u,y}\right)}\right]}^{\left|p\right|}dxdu\right)}^{\frac{1}{\left|p\right|}}⩽\frac{R}{r},\end{array}$$

that $\underset{x\in X}{{\mathcal{M}}^{\left|p\right|}}\left(\underset{y\in Y}{{\mathcal{M}}^q}\left(d_{x,y}\right)\right)⩽\frac{R}{r}\underset{x\in X}{{\mathcal{M}}^p}\left(\underset{y\in Y}{{\mathcal{M}}^q}\left(d_{x,y}\right)\right)$, which is now (7).

Step 3: The previous steps can be summarized in the expression

$${GD}_{\left|p\right|,\left|q\right|}(X,Y)⩽\frac{R}{r}{GD}_{\left|p\right|,q}(X,Y)⩽\frac{R^2}{r^2}{GD}_{p,q}(X,Y).$$

(8)

Using again 4 of Proposition 2 and Definition 6, we get ${GD}_{p,q}(X,Z)⩽{GD}_{\left|p\right|,\left|q\right|}(X,Z)$. From this, the subadditivity for ${GD}_{\left|p\right|,\left|q\right|}$ (Theorem 1), and Equation (8), we conclude

$$\begin{array}{cc}\hfill {GD}_{p,q}(X,Z)& ⩽{GD}_{\left|p\right|,\left|q\right|}(X,Y)+{GD}_{\left|p\right|,\left|q\right|}(Y,Z)⩽\frac{R^2}{r^2}\left({GD}_{p,q}(X,Y)+{GD}_{p,q}(Y,Z)\right).\hfill \end{array}$$

 □

Remark 3.

For parameters $(p,q)\in {\mathbb{R}}^2$ that lie in the orange or blue sectors in Figure 2, the distance ${GD}_{p,q}$ fulfills a C relaxed triangle inequality for a constant $C=R^2/r^2$ only if the condition $r⩽d_{u,v}⩽R$ holds for all $u\in X\cup Y$ and $v\in Y\cup Z$. On bounded and topologically separated sets (i.e., not having common limit points), this condition always holds, and on them, ${\Delta }_{p,q}$ becomes an inframetric as explained below.

Corollary 2.

Under the same hypotheses of Theorem 2, the $(p,q)$-averaged Hausdorff distance ${\Delta }_{p,q}$ satisfies

$${\Delta }_{p,q}(X,Z)⩽\frac{R^2}{r^2}\left({\Delta }_{p,q}(X,Y)+{\Delta }_{p,q}(Y,Z)\right).$$

Proof. 

It is immediate using Theorem 2 and Definition 7. □

When the involved sets are finite, a generally sharper inframetric relation holds. For emphasis, we employ in this context the notation $A,B,C$ for those subsets of $\mathcal{S}$.

Theorem 3.

If $p,q\in \mathbb{R}$ and $\left|p\right|,\left|q\right|>1$, the $(p,q)$-distance ${GD}_{p,q}$ satisfies the relaxed triangle inequality

$${GD}_{p,q}(A,C)⩽N^{\alpha }\left({GD}_{p,q}(A,B)+{GD}_{p,q}(B,C)\right),$$

for all finite subsets $A,B,C\subset \mathcal{S}$, where $N:=max\left\{\right|A|,|B|,|C\left|\right\}⩾1$ and ${\alpha :=\left|p\right|}^{-1}+{\left|q\right|}^{-1}$.

Proof. 

For arbitrary $p\ne 0$, let us assume that $q<0$, so that $\left|q\right|=-q$. We can write

$$\begin{array}{c}\hfill {GD}_{p,\left|q\right|}(A,B)={\left(\overline{)\sum }_{a\in A}{\left({\left[\overline{)\sum }_{b\in B}d{(a,b)}^{-q}\right]}^{-1}\right)}^{\frac{p}{q}}\right)}^{\frac{1}{p}}={\left(\overline{)\sum }_{a\in A}{\left({\left|B\right|}^{-2}\underset{b\in B}{harm}\left\{d{(a,b)}^q\right\}\right)}^{\frac{p}{q}}\right)}^{\frac{1}{p}},\end{array}$$

which, when combined with property 5 of Proposition 1, yields

$$\begin{array}{c}\hfill {GD}_{p,\left|q\right|}(A,B)⩽{\left(\overline{)\sum }_{a\in A}{\left({\left|B\right|}^{-1}\underset{b\in B}{min}\left\{d{(a,b)}^q\right\}\right)}^{\frac{p}{q}}\right)}^{\frac{1}{p}}⩽{\left|B\right|}^{\frac{1}{\left|q\right|}}{\left(\overline{)\sum }_{a\in A}{\left(\overline{)\sum }_{b\in B}d{(a,b)}^q\right)}^{\frac{p}{q}}\right)}^{\frac{1}{p}}={\left|B\right|}^{\frac{1}{\left|q\right|}}{GD}_{p,q}(A,B).\end{array}$$

A similar relation is true for any $q\ne 0$ if $p<0$. In conclusion, ${GD}_{\left|p\right|,\left|q\right|}(A,B)⩽N^{\alpha }{GD}_{p,q}(A,B)$, where

$$\alpha :=\left\{\begin{array}{cc}{|min\{p,q\}|}^{-1}\hfill & \mathrm{if}pq<0,\hfill \\ {\left|p\right|}^{-1}+{\left|q\right|}^{-1}\hfill & \mathrm{if}p<0,q<0.\hfill \end{array}\right.$$

If $N^{\alpha }$ does not need to be sharp, $\alpha$ can always be chosen to take the larger value ${\left|p\right|}^{-1}+{\left|q\right|}^{-1}$.

Now, for $\left|p\right|,\left|q\right|⩾1$, the final result follows from the triangle inequality for ${GD}_{\left|p\right|,\left|q\right|}$:

$$\begin{array}{c}\hfill {GD}_{p,q}(A,C)⩽{GD}_{\left|p\right|,\left|q\right|}(A,C)⩽N^{\alpha }\left({GD}_{p,q}(A,B)+{GD}_{p,q}(B,C)\right).\hspace{1em}\square \end{array}$$

Corollary 3.

If $p,q\in \mathbb{R}$ and $\left|p\right|,\left|q\right|⩾1$, the $(p,q)$-distance ${\Delta }_{p,q}$ satisfies the relaxed triangle inequality:

$${\Delta }_{p,q}(A,C)⩽N^{\alpha }\left({\Delta }_{p,q}(A,B)+{\Delta }_{p,q}(B,C)\right),$$

for all finite subsets $A,B,C\subset \mathcal{S}$, with $N:=max\left\{\right|A|,|B|,|C\left|\right\}⩾1$, and ${\alpha :=\left|p\right|}^{-1}+{\left|q\right|}^{-1}$.

Proof. 

The corollary follows immediately from Theorem 3 and Definition 5. □

To conclude this section, we return to the general setting of arbitrary measurable sets to explain the behavior of ${\Delta }_{p,q}$ when changing the value of its parameters p and q.

Theorem 4.

Let $X,Y\in {\mathfrak{M}}_{<\infty }\left(\mathcal{S}\right)$ and suppose that $p,p^{\prime },q,q^{\prime }\in \overline{\mathbb{R}}$ satisfy $p⩽p^{\prime }$ and $q⩽q^{\prime }$. Then,

$${\Delta }_{p,q}(X,Y)⩽{\Delta }_{p^{\prime },q}(X,Y)and{\Delta }_{p,q}(X,Y)⩽{\Delta }_{p,q^{\prime }}(X,Y).$$

Proof. 

It follows easily from part 5 of Proposition 2 and Definition 7. □

6. The (p,q)-Distances as Quality Indicators

Let Q be a decision space Q and $F:Q\to {\mathbb{R}}^k$ be a multi-objective function on it, of which the associated MOP consists in the simultaneous minimization of its k component functions $f_1,\dots ,f_k$. A candidate solution to this problem is Pareto-optimal if all elements of its image in $F\left(Q\right)\subset {\mathbb{R}}^k$ are nondominated in the sense of Pareto [31]; see Definition 1. For the forthcoming discussion, let us introduce the following abbreviated and useful notation. For $X,Y\subset Q$ and any $z\in Q$, we define the following

$$\begin{array}{cccc}\hfill X_{⪯z}:=& \{x\in X\mid x⪯z\},\hfill & \hfill X_{⪯Y}:=& \{x\in X\mid \exists y\in Y:x⪯y\},\hfill \\ \hfill X_{⋠z}:=& \{x\in X\mid x⋠z\},\hfill & \hfill X_{⋠Y}& \{x\in X\mid \nexists y\in Y:x⪯y\}.\hfill \end{array}$$

From these definitions, it follows that, for arbitrary $z\in Q$ and $X,Y\subset Q$, there are partitions:

$$X=X_{⪯z}\bigsqcup X_{⋠z},\mathrm{and}X=X_{⪯Y}\bigsqcup X_{⋠Y},$$

where ⊔ stands for the disjoint union of subsets. A similar notation with the subindices ≺, ≻, and ⪰ can also be used in an analogous way. Let us recall that an archive $X\subset Q$ is, by definition, a subset of mutually non-dominated points; therefore, for any $x,x^{\prime }\in X$, the condition $x⪯x^{\prime }$ implies $x=x^{\prime }$. This basic property implies that $F:Q\to {\mathbb{R}}^k$ is a bijection when restricted to any archive $X\subset Q$ and, therefore, the points in $F\left(X\right)\subset F\left(Q\right)$ can be univocally labeled by the elements of X. Moreover, for a finite archive $A\subset Q$, both sets have the same number of elements $\left|A\right|=\left|F\right(A\left)\right|$.

Now, we introduce a couple of strengthened notions of dominance between sets (archives) that are required for the validity of most of the results in this section.

Definition 8.

An archive X is well-dominated by an archive Y if

1.

X is dominated by Y, written $Y⪯X$, i.e., $\forall x\in X$, $\exists y\in Y$ s.t. $y⪯x$, and

2.

Y consists only of dominating points of X, i.e., $\forall y\in Y$, $\exists x\in X$ s.t. $y⪯x$.

Moreover, X is said to be strictly well dominated by Y if

3.

$\exists y\in Y\backslash X$, $\exists x\in X\backslash Y$ such that $y\prec x$.

For an archive $X\subset Q$, the ${GD}_{p,q}$, ${IGD}_{p,q}$, and ${\Delta }_{p,q}$ quality (or performance) indicators assigned to it will be defined as the distance of its image $F\left(X\right)$ to the Pareto front $F\left(P\right)$, i.e.,

$$\begin{array}{c}{\mathcal{I}}_{p,q}^{GD}\left(X\right):={GD}_{p,q}(F\left(X\right),F\left(P\right)),{\mathcal{I}}_{p,q}^{IGD}\left(X\right):={IGD}_{p,q}(F\left(X\right),F\left(P\right)),\\ \mathrm{and}{\mathcal{I}}_{p,q}^{\Delta }\left(X\right):={\Delta }_{p,q}(F\left(X\right),F\left(P\right)).\end{array}$$

In this section, we study the behavior of ${\mathcal{I}}_{p,q}^{GD}$, ${\mathcal{I}}_{p,q}^{IGD}$, and ${\mathcal{I}}_{p,q}^{\Delta }$ as performance indicators. An example of a weakly Pareto-compliant performance indicator is the Degree of Approximation (DOA; see Reference [10]).

6.1. Pareto Compliance of $(p,q)$-Indicators in the Finite Case

In order to obtain general conclusions on the features of the averaged Hausdorff distance ${\Delta }_{p,q}$ as a quality indicator, we consider first the behavior of ${GD}_{p,q}$. For additional details on the material presented in this section and other related results in the context of the p-averaged Hausdorff Distance ${\Delta }_p$, the reader is referred to Reference [28].

For the following statements, we will abbreviate ${\delta }_q(a,B):={\left({\overline{)\sum }}_{b\in B}d{(a,b)}^q\right)}^{\frac{1}{q}}$. Clearly, with this notation, ${\mathcal{I}}_{p,q}^{GD}\left(A\right)={\left({\overline{)\sum }}_{a\in A}{\delta }_q{(F\left(a\right),F\left(P\right))}^p\right)}^{\frac{1}{p}}$, where in the averaged sum $\overline{)\sum }$, we are labeling the points in $F\left(A\right)$ by the elements of the archive A, taking advantage of the fact that $\left|A\right|=\left|F\right(A\left)\right|$, as it also will be done with all the averages in this section.

Theorem 5.

Let $A,B\subset Q$ be finite archives with A strictly well dominated by B. For all $a\in A$ and $b\in B$,

1.

$b\prec a$ implies that ${\delta }_q(F\left(b\right),F\left(P\right))<{\delta }_q(F\left(a\right),F\left(P\right))$;

2.

$b⪯a$ implies that ${\displaystyle \frac{|B_{⪯a}|}{\left|B\right|}}⩽{\displaystyle \frac{|A_{⪰b}|}{\left|A\right|}}$ (or equivalently an strict equality);

then, ${\mathcal{I}}_{p,q}^{GD}\left(B\right)<{\mathcal{I}}_{p,q}^{GD}\left(A\right)$.

Proof. 

By condition 1, for all $a\in A$ and $b\in B_{⪯a}$, the inequality ${\delta }_q{(F\left(b\right),F\left(P\right))}^p⩽{\delta }_q{(F\left(a\right),F\left(P\right))}^p$ holds true. After averaging over all $b\in B_{⪯a}$ at both sides, we have

$$\overline{)\sum }_{b\in B_{⪯a}}{\delta }_q{(F\left(b\right),F\left(P\right))}^p⩽{\delta }_q{(F\left(a\right),F\left(P\right))}^p,$$

and averaging once again over all $a\in A$ produces

$$\overline{)\sum }_{a\in A}\left(\overline{)\sum }_{b\in B_{⪯a}}{\delta }_q{(F\left(b\right),F\left(P\right))}^p\right)⩽\overline{)\sum }_{a\in A}{\delta }_q{(F\left(a\right),F\left(P\right))}^p.$$

(9)

From property 2 and noticing that each $b\in B$ appears $|A_{⪰b}|$ times in the initial sum, the lhs becomes

$$\overline{)\sum }_{a\in A}\sum _{b\in B_{⪯a}}\frac{1}{|B_{⪯a}|}{\delta }_q{(F\left(b\right),F\left(P\right))}^p\ge \overline{)\sum }_{a\in A}\sum _{b\in B_{⪯a}}\frac{\left|A\right|}{\left|B\right|}\frac{1}{|A_{⪰b}|}{\delta }_q{(F\left(b\right),F\left(P\right))}^p=\overline{)\sum }_{b\in B}{\delta }_q{(F\left(b\right),F\left(P\right))}^p.$$

Returning to Equation (9), we conclude that ${\mathcal{I}}_{p,q}^{GD}\left(B\right)⩽{\mathcal{I}}_{p,q}^{GD}\left(A\right)$. Lastly, part 3 of Definition 8 for strictly well-dominated sets guarantees that this is an strict inequality, proving the assertion.  □

Remark 4.

Since we are dealing with finite archives, condition 2 of Theorem 5 regarding the relative size of some of their parts is equivalent to the condition $\left|F\right(B_{⪯a}\left)\right|/\left|F\right(B\left)\right|⩽\left|F\right(A_{⪰b}\left)\right|/\left|F\right(A\left)\right|$ regarding the relative size of their images. This is not necessarily the case in the context of measurable subsets, but see Remark 5.

Figure 3 shows examples where Theorem 5 holds with $q\to -\infty$. In this case, the q-averaged distance ${\delta }_q(a,B)$ becomes the standard distance $d(a,B)$ between a point and a set.

For the inverted generational distance ${IGD}_{p,q}$ in the finite case, we provide here two useful results without explicit proofs. The necessary steps are similar to the arguments used to prove the analogous statements for ${IGD}_p$ in Prop. 3.8 of Reference [28] and Thm. 3.9 in Reference [28]. Those statements correspond here to the limit $q\to -\infty$, and the main difference in the proofs is that the Euclidean distante $d(a,B)$ needs to be changed everywhere by the q-average ${\delta }_q(a,B)$, as it was done above for the proof of Theorem 5 that generalizes the proof of Thm. 3.4 in Reference [28]. The reader can also find there additional remarks on similar hypotheses to the ones needed for Theorem 6 below.

Proposition 3.

Let $A,B\subset Q$ be finite and strictly well-dominated archives with $B⪯A$ such that for all $a\in A$, $b\in B$, and $x\in P$:

$$b\prec a\mathit{implies}{\delta }_q(F\left(b\right),F\left(x\right))<{\delta }_q(F\left(a\right),F\left(x\right));$$

then, ${\mathcal{I}}_{p,q}^{IGD}\left(B\right)<{\mathcal{I}}_{p,q}^{IGD}\left(A\right)$.

Figure 4 illustrates two situations where the hypotheses of Proposition 3 are satisfied. Now, to state a more general result concerning the Pareto compliance of the ${IGD}_{p,q}$ indicator, we will further abbreviate the minimal p-average of distances ${\delta }_q(F\left(a\right),F\left(P_{⋠B}\right))$ by

$${\delta }_A:=\underset{a\in A}{min}\left\{{\left(\overline{)\sum }_{x\in P_B}{\delta }_q{(F\left(x\right),F\left(a\right))}^p\right)}^{\frac{1}{p}}\right\}=\underset{a\in A}{min}{IGD}_{p,q}(F\left(a\right),F\left(P_{⋠B}\right)).$$

Theorem 6.

Let $A,B\subset Q$ be finite and strictly well-dominated archives such that $B⪯A$. If at least one of the following conditions is satisfied,

1.

$\forall a\in A$, $\forall b\in B$: $b\prec a\mathit{implies}{IGD}_{p,q}(F\left(b\right),F\left(P_{⋠B}\right))<{IGD}_{p,q}(F\left(a\right),F\left(P_{⋠B}\right))$;

2.

$\exists a_0\in A$ such that $\forall x\in P_{⋠B}$: $a_0\in {arg\; min}_{a\in A}{\delta }_q(F\left(x\right),F\left(a\right))$;

3.

$\forall x\in P_{⋠B}$: ${\delta }_q(F\left(A\right),F\left(x\right))={\delta }_A$;

then ${\mathcal{I}}_{p,q}^{IGD}\left(B\right)<{\mathcal{I}}_{p,q}^{IGD}\left(A\right)$.

Finally, a general statement on the Pareto compliance of the finite case of the $(p,q)$-averaged Hausdorff distance ${\Delta }_{p,q}$ follows as a consequence of Theorems 5 and 6.

Theorem 7.

Let $A,B\subset Q$ be finite and well-dominated archives such that $B⪯A$. If for all $a\in A$, $b\in B$:

$$b⪯a\mathit{implies}{\displaystyle \frac{|B_{⪯a}|}{\left|B\right|}}={\displaystyle \frac{|A_{⪰b}|}{\left|A\right|}},$$

and at least one of the following conditions is satisfied:

1.

$\forall a\in A$, $\forall b\in B$, $\forall x\in P$: $b\prec a\mathit{implies}{\delta }_q(F\left(b\right),F\left(x\right))<{\delta }_q(F\left(a\right),F\left(x\right))$;

2.

$\exists a_0\in A$ such that $\forall x\in P_{⋠B}$: $a_0\in {arg\; min}_{a\in A}{\delta }_q(F\left(x\right),F\left(a\right))$;

3.

$\forall x\in P_{⋠B}$: ${\delta }_q(F\left(A\right),F\left(x\right))={\delta }_A$;

then, ${\mathcal{I}}_{p,q}^{\Delta }\left(B\right)<{\mathcal{I}}_{p,q}^{\Delta }\left(A\right)$.

Figure 5 illustrates four situations where Theorems 6 and 7 apply with very large q. In the first row, the left diagram is a modification of the second case in Figure 4 where condition 1 holds. In the right diagram, the diamond lying at the lower left corner of $F\left(A\right)$ represents the image $F\left(a_0\right)$ of a point $a_0$ satisfying condition 2. Finally, both diagrams in the second row exhibit cases where the points of $F\left(P\right)$ are equidistant to corresponding points in $F\left(A\right)$, making condition 3 valid, with ${\delta }_A$ being this distance.

6.2. Pareto Compliance of $(p,q)$-Indicators in the General Case

We consider now the behavior of the generalized ${GD}_{p,q}$ distance with respect to the Pareto-compliance, concentrating on the most important aspects that describe its characteristics and using similar hypotheses to the ones needed in the previous section for ${\Delta }_{p,q}$ in the finite case.

Here, we will continue to assume that the decision space Q with objective function $F:Q\to {\mathbb{R}}^k$ defining the MOP under consideration has a Pareto set $P\subset Q$ with corresponding Pareto front $F\left(P\right)\subset F\left(Q\right)$. Also, we assume that the objective space $F\left(Q\right)\subset {\mathbb{R}}^k$ carries a metric d that, for simplicity, can be taken to be the one inherited from the Euclidean distance $d(·,·)$ in ${\mathbb{R}}^k$. In addition, to define the $(p,q)$-indicators on MOPs that require general non-finite sets, we need a measure space $(\mathcal{S},\mu )$, that here will be taken to be $\mathcal{S}F\left(Q\right)$ endowed with a non-null measure $\mu$ according to the comments at the beginning of Section 4.2. In this context X, $Y\subset Q$ will denote arbitrary subsets such that $F\left(X\right),F\left(Y\right)\subset F\left(Q\right)$ are measurable with non-null and finite measures.

Remark 5.

Recall that, here, $\left|F\right(X\left)\right|=\mu \left(F\right(X\left)\right)$ denotes the measure of $F\left(X\right)\subset \mathcal{S}$. In this context, Q will not be asked to carry a measure and the notation $\left|X\right|$ will have no a priori meaning for $X\subset Q$. Nevertheless, it is possible to induce a measure on those subsets of Q where F is bijective by taking the pullback ${\mu }^{*}$ of μ to them, making the identity $\left|X\right|={\mu }^{*}\left(X\right):=\mu \left(X\right)=\left|F\left(X\right)\right|$ trivially true. This can be done for all archives but not for subsets where F is not bijective. When it is Q that carries a measure, a push-forward measure can be always defined on its image $F\left(Q\right)$, making this identity true for all sets. This was implicitly assumed in the presentation provided in Reference [18] (Section 3.4). For clarity, we avoid here this identification and state everything from the assumption that the measure μ is defined only on $S:=F\left(Q\right)$.

Before stating the complete result, let us recall that a partition of a set X is a collection of disjoint and non-empty subsets of X whose union is the whole of X and a partition of an archive $X\subset Q$ induces a partition of $F\left(X\right)\subset F\left(Q\right)$ by the bijectivity of F restricted to X. For convenience, we abbreviate the measure-theoretic q-averaged distance from a point $F\left(x\right)\in F\left(Q\right)$ to a set $F\left(Z\right)\subset F\left(Q\right)$ by ${\delta }_q(F\left(x\right),F\left(Z\right)):={(-{\int }_{v\in F\left(Z\right)}d{(F\left(x\right),v)}^q)}^{\frac{1}{q}}$.

Theorem 8.

For $p,q\in \overline{\mathbb{R}}$, let $X,Y\subset Q$ denote archives of which the images $F\left(X\right)$ and $F\left(Y\right)$ are of non-null finite measures in $F\left(Q\right)$. Moreover, assume that

1.

there exist finite partitions $X={⨆}_{i=1}^m{X}_i$ and $Y={⨆}_{i=1}^m{Y}_i$ such that $\forall i\in \{1,\dots ,m\}$:

(a)

$F\left(X_i\right)\subset F\left(X\right)$ and $F\left(Y_i\right)\subset F\left(Y\right)$ are subsets of non-null finite measure in $F\left(Q\right)$;

(b)

$\forall x\in X_i$, $\forall y\in Y_i$: $x⪯y$;

2.

$\forall x\in X$, $\forall y\in Y$: $x⪯y\mathit{implies}{\delta }_q(F\left(x\right),F\left(P\right))⩽{\delta }_q(F\left(y\right),F\left(P\right))$;

then, ${\mathcal{I}}_{p,q}^{GD}\left(X\right)⩽{\mathcal{I}}_{p,q}^{GD}\left(Y\right)$.

Proof. 

By $1\left(a\right)$ of Theorem 8, the sets X and Y can be subdivided into the same number m of subsets, and by $1\left(b\right)$, if $x\in X_i$ and $y\in Y_i$ for any $i\in \{1,\dots ,m\}$, then ${\delta }_q(F\left(x\right),F\left(P\right))⩽{\delta }_q(F\left(y\right),F\left(P\right))$. Therefore, we can take successive integral p-averages over $F\left(X_i\right)$ and, afterwards, over $F\left(Y_i\right)$ at both sides of this inequality to find that, for each i, we have

$$a_i^p:=\frac{1}{\left|F\right(X_i\left)\right|}{\int }_{F\left(X_i\right)}{\delta }_q{(v,F\left(P\right))}^{p}dv⩽\frac{1}{\left|F\right(Y_i\left)\right|}{\int }_{F\left(Y_i\right)}{\delta }_q{(v,F\left(P\right))}^{p}dv=:b_i^p.$$

(10)

For those $i\in \{1,\dots ,m\}$ violating the inequality $\frac{|X_i|}{\left|X\right|}⩽\frac{|Y_i|}{\left|Y\right|}$, we subdivide $X_i$ into a sufficiently large partition of $m_i$ subsets $X_{i,1},X_{i,2},\dots ,X_{i,m_i}$, with images by F of non-null finite measure, so as to guarantee that, for all $j\in \{1,\dots ,m\}$, we get

$$w_{i,j}:=\frac{\left|F\right(X_{i,j}\left)\right|}{\left|F\right(X\left)\right|}⩽\frac{\left|F\right(Y_i\left)\right|}{\left|F\right(Y\left)\right|}=:{\tilde{w}}_i.$$

(11)

Notice that this is indeed possible because each $F\left(X_i\right)$ is of non-null finite measure. Since $\forall x\in X_{i,j}$, $\forall y\in Y_i$, we have $x⪯y$, an inequality similar to Equation (10) also holds for them, i.e.,

$$a_{i,j}^p:=\frac{1}{\left|F\right(X_{i,j}\left)\right|}{\int }_{F\left(X_{i,j}\right)}{\delta }_q{(v,F\left(P\right))}^{p}dv⩽\frac{1}{\left|F\right(Y_i\left)\right|}{\int }_{F\left(Y_i\right)}{\delta }_q{(v,F\left(P\right))}^{p}dv=:b_i^p,$$

for all $i\in \{1,\dots ,n\}$, $j\in \{1,\dots ,m_i\}$. However, $\left|F\left(X\right)\right|={\sum }_{i=1}^m\left|F\left(X_i\right)\right|$, where $|F\left(X_i\right)|={\sum }_{j=1}^{m_i}\left|F\left(X_{i,j}\right)\right|$ and $\left|F\left(Y\right)\right|={\sum }_{i=1}^m\left|F\left(Y_i\right)\right|$. Therefore, with the notation of Equation (11), a simple calculation shows that ${\sum }_{i=1}^m{\sum }_{j=1}^{m_i}{w}_{i,j}={\sum }_{i=1}^m{\tilde{w}}_i=1$, implying that $w_{i,j}$ and ${\tilde{w}}_i$ are normalized weights useful for weighted averages. Since $0⩽a_{i,j}⩽b_i$ and $0⩽w_{i,j}⩽{\tilde{w}}_i⩽1$, simple properties of discrete weighted power mean imply the inequality ${\sum }_{i=1}^m{\sum }_{j=1}^{m_i}{w}_{i,j}{a}_{i,j}^p⩽{\sum }_{i=1}^m{\tilde{w}}_i{b}_i^p$. Thus, we can finally write

$$\begin{array}{cc}\hfill {\mathcal{I}}_{p,q}^{GD}{\left(F\left(Y\right)\right)}^p& =\frac{1}{\left|F\right(X\left)\right|}\sum _{i=1}^m\sum _{j=1}^{m_i}{\int }_{F\left(X_{i,j}\right)}{\delta }_q{(v,F\left(P\right))}^p\mathrm{d}v=\sum _{i=1}^m\sum _{j=1}^{m_j}\frac{\left|F\right(X_{i,j}\left)\right|}{\left|F\right(X\left)\right|}{a}_{i,j}^p=\sum _{i=1}^m\sum _{j=1}^{m_i}{w}_{i,j}{a}_{i,j}^p\hfill \\ \hfill & ⩽\sum _{i=1}^m{\tilde{w}}_i{b}_i^p=\sum _{i=1}^m\frac{\left|F\right(Y_i\left)\right|}{\left|F\right(Y\left)\right|}{b}_i^p=\frac{1}{\left|F\right(Y\left)\right|}\sum _{i=1}^m{\int }_{F\left(Y_i\right)}{\delta }_q{(v,F\left(P\right))}^p\mathrm{d}v={\mathcal{I}}_{p,q}^{GD}{\left(Y\right)}^p.\hfill \end{array}$$

 □

Remark 6.

From condition 1 of Theorem 8, it follows the simpler (and somewhat weaker) dominance conditions:

($a^{\prime }$)

$X⪯Y$ (i.e., $\forall y\in Y$, $\exists x\in X$ such that $x⪯y$), and

($b^{\prime }$)

$\forall x\in X$, $\exists y\in Y$ such that $x⪯y$.

For simple situations where ($a^{\prime }$) and ($b^{\prime }$) are valid, the partitions needed for part 1 of Theorem 8 are not difficult to find; however, this is not always possible as the right side of Figure 6 indicates. Indeed, Figure 6 presents some examples where ($a^{\prime }$) and ($b^{\prime }$) hold true, but ${\mathcal{I}}_{p,q}^{GD}\left(X\right)⩽{\mathcal{I}}_{p,q}^{GD}\left(Y\right)$ can be both true (left side) and false (right side). Furthermore, it is possible to show that X and Y comply (left side) and do not comply (right side) with condition 1 of Theorem 8, respectively.

Remark 7.

An important advantage of using ${GD}_{p,q}$ over ${GD}_p$ is that condition 2 of Theorem 8 provides the possibility of choosing an appropriate $q\in \overline{\mathbb{R}}$ for which the condition ${\delta }_q(F\left(x\right),F\left(P\right))⩽{\delta }_q(F\left(y\right),F\left(P\right))$ holds when $x⪯y$, ensuring in this way the compliance to Pareto optimality for ${GD}_{p,q}$. This freedom is lacking for ${GD}_p$ because, in the limit $q\to -\infty$, the distance ${\delta }_q(F\left(x\right),F\left(P\right))$ becomes the standard distance $d\left(F\right(x),F(P\left)\right)$, which does not allow for any choice.

7. Examples and Numerical Experiments

In this section, we present some numerical experiments involving finite sets first, and afterwards, we study the case of continuous sets.

7.1. Working with ${\Delta }_{p,q}$ over Finite Sets

Let us take a hypothetical Pareto front P given by the line segment from $(0,1)$ to $(1,0)$ in ${\mathbb{R}}^2$, i.e., the set of all points

$$(t,1-t)\in {\mathbb{R}}^2,\mathrm{for}0⩽t⩽1.$$

This is the same example considered in Reference [16] p. 506 and enables us to make a comparison with values of ${\Delta }_p$. In order to use the finite version of ${\Delta }_{p,q}$, we discretize P by taking 11 uniformly distributed points; we call this set $P^{\prime }$. We assume two archives: $X_1$ is obtained from $P^{\prime }$ by changing $(0,1)$ for $(0,10)$, including an outlier, and by adding $1/10$ to the remaining ordinates. $X_2$ is obtained from $P^{\prime }$ by adding 5 to each ordinate. See Figure 7.

As explained in Section 3, we know that

$${\Delta }_{\infty }(A,B)\underset{p\to \infty }{lim}{\Delta }_p(A,B)$$

coincides with the standard Hausdorff distance $d_H$. In this case, we obtained

$$\begin{array}{cccc}\hfill {\Delta }_1(P^{\prime },X_1)& =0.9091,\hfill & \hfill {\Delta }_1(P^{\prime },X_2)& =4.5412,\hfill \\ \hfill d_H(P^{\prime },X_1)& =9,\hfill & \hfill d_H(P^{\prime },X_2)& =5;\hfill \end{array}$$

and according to Theorem 4 and Reference [16] p. 512, these values must increase as p increases.

Table 1. ${\Delta }_{p,q}(P^{\prime },X_1)$ for several values of p and q.

	p	1	2	5	10	20
q
$-\infty$		$0.9091$	$2.7153$	$5.5714$	$7.0811$	$7.9831$
$-100$		$0.9272$	$2.7701$	$5.6839$	$7.2241$	$8.1443$
$-20$		$0.9537$	$2.8367$	$5.8202$	$7.3974$	$8.3396$
$-5$		$0.9895$	$2.8624$	$5.8705$	$7.4613$	$8.4117$
$-1$		$1.1131$	$2.8782$	$5.8848$	$7.4795$	$8.4322$
1		$1.3243$	$2.9112$	$5.8920$	$7.4886$	$8.4425$
2		$2.9277$	$2.9295$	$5.8956$	$7.4932$	$8.4476$
5		$5.8920$	$5.8956$	$5.9063$	$7.5068$	$8.4630$
10		$7.4886$	$7.4932$	$7.5068$	$7.5292$	$8.4882$

and

Table 2. ${\Delta }_{p,q}(P^{\prime },X_2)$ for several values of p and q.

	p	1	2	5	10	20
q
$-\infty$		$4.5412$	$4.5497$	$4.5751$	$4.6160$	$4.6867$
$-100$		$4.6442$	$4.6529$	$4.6790$	$4.7209$	$4.7933$
$-20$		$4.8425$	$4.8518$	$4.8795$	$4.9239$	$5.0003$
$-5$		$4.9624$	$4.9720$	$5.0007$	$5.0465$	$5.1250$
$-1$		$5.0008$	$5.0105$	$5.0394$	$5.0856$	$5.1646$
1		$5.0203$	$5.0301$	$5.0591$	$5.1055$	$5.1848$
2		$5.0301$	$5.0398$	$5.0690$	$5.1154$	$5.1949$
5		$5.0591$	$5.0690$	$5.0983$	$5.1450$	$5.2248$
10		$5.1055$	$5.1154$	$5.1450$	$5.1921$	$5.2725$

show that we can find values of p and q such that the $(p,q)$-averaged distance does not punish heavily the outliers, for example, $p=q=1$ or $p=1$ and $q=-1$. We remark that the values of ${\Delta }_{p,q}(P^{\prime },X_1)$ do not present a significative change under variations of $q⩽1$ for a fixed p. Thus, it is possible to work with $q=1$, in which case ${\Delta }_{p,q}$ is a metric according to Corollary 1, and to still obtain values close to the ones given by the inframetric ${\Delta }_p$, with the same $p⩾1$.

For large values of p, the behavior of ${\Delta }_{p,q}$ presents the same disadvantages of ${\Delta }_p$ or of the standard Hausdorff distance. For example, in Table 1 and Table 2, it can be observed that all distances for $p⩾5$ are useless because they imply that the distance from the discrete Pareto front $P^{\prime }$ to the archive $X_1$ is larger than its distance to the archive $X_2$. Figure 7 suggests that this is an undesirable outcome.

Table 3. Triangle inequality violations, in percentage, for several values of p and q: Here, we randomly chose 80 sets, each one containing 2 points in ${[0,10]}^2$, and verified the triangle inequality for all possible set permutations (that is, 492,960).

	p	1	2	5	10
q
$-1$		$0.05396$	0	0	0
$-2$		$0.10265$	$0.00041$	0	0
$-5$		$0.28815$	$0.01217$	0	0
$-10$		$0.35622$	$0.05031$	$0.00041$	0
$-20$		$0.43046$	$0.08439$	$0.00446$	$0.00041$

shows that ${\Delta }_{p,q}$ is close to a metric when $q⩽-1$ and $p⩾1$. The percentage of triangle inequality violations decreases as p increases or q decreases.

7.2. Optimal Archives for Discretized Spherical Pareto Fronts

We now consider two standard Pareto fronts: The spheric convex and spheric concave quarter-circles, see Figure 8 and Figure 9.

$$\begin{array}{cc}\hfill P_1& =\left\{(cos(\theta )+1,sin(\theta )+1):-\pi ⩽\theta ⩽-\pi 2\right\},\hfill \\ \hfill P_2& =\left\{(cos(\theta ),sin(\theta \left)\right):0⩽\theta ⩽\pi 2\right\}.\hfill \end{array}$$

(12)

To numerically find the optimal ${\Delta }_{p,q}$ archive of size M, we discretized the Pareto front with 1000 equidistant points (which is an acceptable discretization according to Reference [63] p. 603) and randomly chose an initial M sized archive. Then, we used a random-walk (or step climber) evolutionary algorithm, moving one point at a time. Finally, we refined the optimal archive with the “evenly spaced” construction suggested by Reference [63] p. 607.

When finding optimal ${\Delta }_{p,q}$ archives, our numerical experiments suggest a clear geometrical influence of the parameters p and q. For values of p in $(-\infty ,-1)$, the optimal archive sets are basically the same. When $q\in [-1,1]$ increases, the optimal archive tends to lose dispersion, converging to one point. When $q⩾1$, the optimal archive collapses to one point, and when $q\in (-\infty ,-1]$, the corresponding optimal archives are basically the same (see Figure 10). When $p⩾-1$ increases, the optimal archive moves away from the Pareto set (see Figure 11).

The following Figure 10 and Figure 11 show certain “optimal” archives A for the Pareto front $P_1$ in Equation (12), where the optimality means that the distance ${\Delta }_{p,q}(X,P_1)$ is minimum when $X=A$. Because of the choice of the parameters p and q, this solution is clearly different from the one shown in the Figure 8.

7.3. Optimal Archives for Disconnected and Discretized Pareto Sets

In this section, we present the optimal ${\Delta }_{p,q}$ archives for a disconnected step Pareto front:

$$P_3^{(s,\gamma )}=\left\{\left(t,1-\gamma t+(\gamma -1)\frac{\lfloor st\rfloor }{s}\right):0⩽t⩽1\right\},$$

(13)

where s is the number of steps, $\gamma >0$ is a small constant responsible for the step’s twist, and $\lfloor ·\rfloor$ stands for the integer part function.

Figure 12 shows numerical optimal ${\Delta }_{1,-1}$ archives of sizes 20. The archive coordinates reveal that

$$A\cap P_3^{\left(5,\frac{1}{10}\right)}=⌀,$$

i.e., the optimal archive points do not lie over the Pareto front but they are so close to it that this is hardly noticeable. It is also evident that the archives are evenly distributed along the Pareto front.

7.4. General Example for Continuous Sets

In this first example, we are going to construct simple and illustrative continuous sets A and B. Let A be the straight segment in ${\mathbb{R}}^2$ from $a=(-1,0)$ to $b=(1,0)$, that is

$$A=\overline{ab}.$$

(14)

For a small positive $\epsilon >0$ and a variable $\delta >0$, let $B_{\delta }\subset {\mathbb{R}}^2$ be the set given by the following union of straight segments

$$B_{\delta }=\overline{c{d}_{\delta }}\cup \overline{e_{\delta }{f}_{\delta }}\cup \overline{g_{\delta }h},$$

(15)

where $c=(-1,\epsilon )$, $d_{\delta }=(-\delta ,\epsilon )$, $e_{\delta }=(-\delta ,1)$, $f_{\delta }=(\delta ,1)$, $g_{\delta }=(\delta ,\epsilon )$, and $h=(1,\epsilon )$. We can regard the set $B_{\delta }$ as a continuous approximation of A, where the central segment $\overline{e_{\delta }{f}_{\delta }}$ can be seen as the outlier.

In the following Figure 13, we can see the sets A and $B_{\delta }$ for $\epsilon =0.10$ and $\delta =0.10,0.20$. According to

Table 4. ${\Delta }_{p,q}$ results between the sets A and $B_{\delta }$ in Equations (14) and (15) for $\epsilon =0.10$ and some parameter values of p, q, and $\delta$.

p	q	${\Delta }_{\mathit{pq}}(\mathit{A},{\mathit{B}}_{0.05})$	${\Delta }_{\mathit{pq}}(\mathit{A},{\mathit{B}}_{0.10})$	${\Delta }_{\mathit{pq}}(\mathit{A},{\mathit{B}}_{0.20})$	${\Delta }_{\mathit{pq}}(\mathit{A},{\mathit{B}}_{0.40})$
1	1	$0.7149$	$0.7464$	$0.8091$	$0.9324$
1	1	$0.4105$	$0.4506$	$0.5311$	$0.6945$
1	100	$0.1503$	$0.1961$	$0.2878$	$0.4711$
1	200	$0.1479$	$0.1934$	$0.2844$	$0.4663$
1	$10,000$	$0.1451$	$0.1901$	$0.2802$	$0.4602$

, as $\delta$ decreases, the ${\Delta }_{p,q}$ distance between the approximation $B_{\delta }$ and the set A also decreases.

We remark that the classical Hausdorff distance between A and $B_{\delta }$ produces the value 1 for any $\delta >0$. Thus, by working with the $(p,q)$-distance instead of $d_H$, we can detect “better” approximations.

7.5. Approximating Pareto Set and Front of a MOP

Finally, we address the problem to approximate the Pareto sets and fronts of given MOPs. As an example, we will consider the bi-objective Lamé super-sphere problem [32] which is defined as follows:

$$\underset{x}{min}F:{\mathbb{R}}^n⟶{\mathbb{R}}^2,$$

(16)

where $F\left(x\right)=(f_1\left(x\right),f_2\left(x\right))$ is defined as

$$f_1\left(x\right)={\left(\frac{1}{n}\sum _{i=1}^n{x}_i^2\right)}^{\frac{\gamma }{2}}\mathrm{and}{f}_2\left(x\right)={\left(\frac{1}{n}\sum _{i=1}^n{(x_i-1)}^2\right)}^{\frac{\gamma }{2}}$$

where $x\in {\mathbb{R}}^n$ and $\gamma \in \mathbb{R}$. For $n=2$, the Pareto sets and fronts of this problem are shown in Figure 14 and Figure 15 for $\gamma =2$ and $\gamma =1/2$, respectively.

In a first step, we discuss the principle difference of discrete and continuous archives when approximating the Pareto set/front on a hypothetical example. For this, we assume that we are given the 5-element archive $A=\{x_1,\dots ,x_5\}\subset {\mathbb{R}}^2$; those elements are given by

$$x_1=(-0.02,0.03),x_2=(0.29,0.20),x_3=(0.41,0.49),x_4=(0.70,0.62),x_5=(1.02,0.98).$$

Hence, we can see A as a 5-element approximation of the Pareto set and its image $F\left(A\right)$ as a 5-element approximation of the Pareto front. Now, instead of A, we may use a polygonal curve that is defined by A:

$$B:=\overline{x_1{x}_2}\cup \cdots \cup \overline{x_4{x}_5}.$$

In the following, we will call A a discrete archive while we call the polygon approximation B the continuous archive. Figure 16 and Figure 17 show the approximations A and B as well as their images $F\left(A\right)$ and $F\left(B\right)$. Apparently, the approximation qualities are much better for the linear interpolates. This impression gets confirmed by the values of ${\Delta }_{p,q}$ for this problem that are shown in

Table 5. ${\Delta }_{p,q}$ results for the approximations of the Pareto set and front for MOP (Equation (16)).

	p	q	Decision Space		Objective Space
			Finite Arch.	Cont. Arch.	Finite Arch.	Cont. Arch.
$\gamma =2$	1	1	$0.5262$	$0.4775$	$0.4377$	$0.3851$
	1	1	$0.2710$	$0.2017$	$0.2051$	$0.1070$
	1	100	$0.1121$	$0.0341$	$0.0862$	$0.0040$
	1	200	$0.1112$	$0.0333$	$0.0855$	$0.0039$
	1	10,000	$0.1103$	$0.0324$	$0.0848$	$0.0038$
$\gamma =\frac{1}{2}$	1	1	$0.5262$	$0.4775$	$0.5520$	$0.4965$
	1	1	$0.2710$	$0.2017$	$0.2587$	$0.1120$
	1	100	$0.1121$	$0.0341$	$0.1079$	$0.0012$
	1	200	$0.1112$	$0.0333$	$0.1071$	$0.0012$
	1	10,000	$0.1103$	$0.0324$	$0.1062$	$0.0011$

. We can observe the following two behaviors: (i) the distances are much better for the continuous archives and the differences are even larger in objective space, and (ii) the distances decrease with decreasing q (which is in accordance to the result of Theorem 4).

In a next step, we consider discrete archives that have been generated from multi-objective evolutionary algorithms together with their resulting continuous archives. For multi-objective evolutionary algorithms, we have chosen the widely used methods NSGA-II [65] and MOEA/D [66]. We stress, however, that any other MOEA could be chosen and that the conclusions we draw out by our results apply in principle to any other such algorithm.

Table 6. Parameter setting for NSGA-II and MOEA/D: Here, n denotes the dimension of the decision variable space.

Algorithm	Parameter	Value
NSGA-II	Population size	12
	Number of generations	500
	Crossover probability	0.8
	Mutation probability	$1/n$
	Distribution index for crossover	20
	Distribution index for mutation	20
MOEA/D	Population size	12
	# weight vectors	12
	Number of generations	500
	Crossover probability	1
	Mutation probability	$1/n$
	Distribution index for crossover	30
	Distribution index for mutation	20
	Aggregation function	Tchebycheff
	Neighborhood size	3

shows the parameter setting we have used for our studies.

Figure 18 and Figure 19 and

Table 7. For MOP (Equation (16)), the Table shows the ${\Delta }_{p,q}$ results for the finite and continuous Pareto front approximations. We used the NSGA-II generated archives for $p=1$ and $q=-10$.

Generation	$\mathit{\gamma }=1/2$		$\mathit{\gamma }=2$
	Finite Arch.	Cont. Arch.	Finite Arch.	Cont. Arch.
50	$0.0439$	$0.0147$	$0.0696$	$0.0160$
100	$0.0498$	$0.0109$	$0.0540$	$0.0102$
200	$0.0613$	$0.0118$	$0.0716$	$0.0207$
250	$0.0651$	$0.0265$	$0.0572$	$0.0061$
400	$0.0602$	$0.0102$	$0.0723$	$0.0276$
450	$0.0630$	$0.0154$	$0.0584$	$0.0088$
460	$0.0612$	$0.0154$	$0.0658$	$0.0098$
470	$0.0523$	$0.0102$	$0.0566$	$0.0083$
480	$0.0754$	$0.0269$	$0.0684$	$0.0241$
490	$0.0510$	$0.0091$	$0.0584$	$0.0118$
500	$0.0722$	$0.0097$	$0.0560$	$0.0103$

show the results of NSGA-II where we have used 500 generations and a population size of 12. Figure 20 and Figure 21 and

Table 8. For MOP (Equation (16)), the Table shows the ${\Delta }_{p,q}$ results for the finite and continuous Pareto front approximations. We used the MOEA/D generated archives for $p=1$ and $q=-10$.

Generation	$\mathit{\gamma }=1/2$		$\mathit{\gamma }=2$
	Finite Arch.	Cont. Arch.	Finite Arch.	Cont. Arch.
50	$0.0610$	$0.0171$	$0.0648$	$0.0119$
100	$0.0519$	$0.0051$	$0.1093$	$0.0016$
200	$0.0536$	$0.0037$	$0.0781$	$0.0009$
250	$0.0522$	$0.0037$	$0.0790$	$0.0008$
400	$0.0511$	$0.0017$	$0.0784$	$0.0009$
450	$0.0511$	$0.0017$	$0.0784$	$0.0009$
460	$0.0509$	$0.0012$	$0.0784$	$0.0009$
470	$0.0509$	$0.0012$	$0.0784$	$0.0009$
480	$0.0509$	$0.0010$	$0.0783$	$0.0009$
490	$0.0509$	$0.0010$	$0.0783$	$0.0009$
500	$0.0509$	$0.0010$	$0.0783$	$0.0009$

show the respective results for MOEA/D where we have also used 500 generations and population size 12. We can see that, for both algorithms, the ${\Delta }_{p,q}$ values are significantly better for the continuous archives. We can also make another observation: the ${\Delta }_{p,q}$ values oscillate for the results of the dominance-based algorithm NSGA-II which is indeed typical. For the continuous archives, these oscillations are less notorious, which indicates that the use of continuous archives may have a smoothing effect on the approximations, which is highly desired.

We want to investigate the last statement further on. To this end, we consider the following convex bi-objective problem: the objectives are given by $f_1,f_2:{\mathbb{R}}^3\to \mathbb{R}$, where

$$\begin{array}{cc}\hfill f_1\left(x\right)& ={(x_1+1)}^2+x_2^2+x_3^2\hfill \\ \hfill f_2\left(x\right)& ={(x_1-1)}^2+x_2^2+x_3^2.\hfill \end{array}$$

(17)

Figure 22 shows the Pareto set and front of MOP (Equation (17)). The Pareto set is given by the straight segment joining $(0,0,0)$ and $(1,0,0)$.

The values of ${\Delta }_{p,q}$ obtained by NSGA-II for the discrete archives (using population size 20) as well as for the respective continuous archives can be seen in Figure 23 and

Table 9. ${\Delta }_{p,q}$ results between the Pareto Front and its respective discrete and continuous approximations of NSGA-II for MOP (Equation (17)): The data shown is the averaged over the 20 independent runs above.

Generation	Continuous Archive	Finite Archive
20	$0.1333$	$0.2401$
40	$0.0176$	$0.1451$
60	$0.0090$	$0.1561$
80	$0.0088$	$0.1355$
100	$0.0065$	$0.1472$
120	$0.0074$	$0.1412$
140	$0.0081$	$0.1395$
160	$0.0075$	$0.1549$
180	$0.0092$	$0.1468$
200	$0.0074$	$0.1429$
220	$0.0066$	$0.1408$
240	$0.0075$	$0.1397$
260	$0.0066$	$0.1460$
280	$0.0074$	$0.1439$
300	$0.0084$	$0.1421$
320	$0.0070$	$0.1352$
340	$0.0070$	$0.1373$
360	$0.0081$	$0.1454$
380	$0.0079$	$0.1413$
400	$0.0066$	$0.1388$
420	$0.0063$	$0.1400$
440	$0.0097$	$0.1384$
460	$0.0067$	$0.1418$
480	$0.0067$	$0.1421$
500	$0.0076$	$0.1426$

. Also for this example, the values for the continuous archives are much better and the oscillations are significantly reduced compared to the discrete archives.

Figure 24, Figure 25 and Figure 26 show the results of both kinds of archives after 300, 400, and 500 generations which confirm this observation. The results show that NSGA-II is indeed capable of computing points near the Pareto front while the distribution of the points vary. This is a known fact since there exists no “limit archive” for this algorithm (as it is, e.g., not based on the averaged Hausdorff distance or any other performance indicator). When considering the respective results of the continuous archives, however, NSGA-II computes (at least visually) nearly perfect approximations of the Pareto front. The ${\Delta }_{p,q}$ values reflect this.

8. Conclusions and Perspectives

In this paper, we have presented a comprehensive overview of the averaged Hausdorff distances that have recently appeared in connection with the study of MOPs.

Among the averaged Hausdorff distances studied here, the generalized ${\Delta }_{p,q}$ as defined for arbitrary measurable sets was shown to provide a general and robust definition for applications that carries good metric properties, is adequate for use with continuous approximations of the Pareto set of a MOP, and even reduces to the previously introduced definition for discrete approximations.

Concerning the appearance of the additional parameter q in the definition of ${\Delta }_{p,q}$ which could give the impression of an overly complicated expression, it is important to highlight, as it was observed in Remark 7, that it can provide the possibility to choose a suitable value of q in order to make ${GD}_{p,q}$ as Pareto compliant as possible for the MOP under consideration. This is an argument in favor of the flexibility provided by the generalized version ${GD}_{p,q}$, which is not available for the ${GD}_p$ distance, and this particular aspect worths further investigation.

Nevertheless, since the freedom provided by the two parameters p and q may appear as excessive and perhaps undesirable in many applications, there remains to find a practical recipe to determine and fix these parameters according to the characteristics of the problem under consideration. Certainly, the desired spreads of the optimal archives, the distance of an approximation to the Pareto front, and the convexity of these fronts need to be taken into account in order to determine an appropriate set of preferred values for these parameters depending on the situation.

To achieve these aims, more theoretical as well as numerical studies of optimal solutions associated with Pareto fronts with different convexities must be carried out and experiments evaluating how the Pareto compliance can be enhanced in each situation by the choice of parameters need to be performed.

Finally, we stress that the results we have shown in Section 7 show the advantage of a new performance indicator that is able to compute the performance of a continuous approximation of the solution set. Continuous approximations, e.g., of the Pareto set/front of multi-objective optimization problems have not been considered so far, though both Pareto set and front typically form continuous sets in case the objectives are continuous. The examples have indicated that the consideration of continuous archives (via use of interpolation on the populations generated by the evolutionary algorithms) could allow a reduction in population sizes and, hence, a significant reduction of the computational effort of the evolutionary algorithms. This is because the time complexity for all existing multi-objective evolutionary algorithms is quadratic in the population size and in each generation of the algorithm. To verify this statement, more computations are needed, which is left for future work.