## 2 Wasserstein Barycenters for the Evolutionary Optimization of Sets
### Frechet Mean to Wasserstein Barycenter  
Recall that \(\delta_{\mathbf{x_{i}}}\) is the Dirac measure at \(\mathbf{x_{i}}\). To each cloud of points \(X=\{\mathbf{x_{1}},...,\mathbf{x_{n}}\}\), we associate the measure \(P_{X}=\frac{1}{n}\sum_{i=1}^{n}\delta_{\mathbf{x_{i}}}\). This mapping allows us to reformulate the considered problems as optimizations over the space of discrete uniform measures with a finite support. With this representation, we define crossovers based on the Frechet mean (a notion developed in [35] for details). We adopt as distance between two measures the Wasserstein distance. Please note that in the literature, this concept is sometimes also called the Kantorovich metric, as in [36]. We remind readers of the following definitions.  
**Definition 1**.: _For two measures \(\mu\) and \(\
u\) defined over \(\mathbb{R}^{d}\), the Wasserstein distance of order \(p\) is defined as follows: \(W_{p}^{p}(\mu,\
u)=\inf_{\pi\in\Pi(\mu,\
u)}\int_{\mathbb{R}^{d}\times\mathbb{ R}^{d}}\rho(\mathbf{x},\mathbf{x}^{\prime})^{p}\mathrm{d}\mathbf{B}(\mathbf{x}, \mathbf{x}^{\prime})\)_  
* \(\rho(\mathbf{x},\mathbf{x}^{\prime})\) _corresponds to the Euclidean distance between_ \(\mathbf{x}\) _and_ \(\mathbf{x}^{\prime}\)__
* \(\Pi(\mu,\
u)\) _is the set of all probability measures defined over_ \(\mathbb{R}^{d}\times\mathbb{R}^{d}\) _with marginals_ \(\mu\) _and_ \(\
u\)_._  
**Definition 2**.: _A barycenter \((\
u^{*})\) of \(N\) measuring \(\
u_{1},...,\
u_{N}\) is the minimizer of \(f(\
u)=\sum_{i=1}^{N}\epsilon_{i}W_{p}^{p}(\
u,\
u_{i})\), with \(\epsilon_{i}\geq 0,\sum_{i=1}^{N}\epsilon_{i}=1\)._  
Algorithms to compute this minimum for a fixed size are discussed in [37] and are implemented in the POT Python library [38]. For more information on this topic, specifically with regards to the existence and uniqueness of the barycenter, please refer to [39].  
In the following, we consider the Euclidean distance with \(p=2\). We show in Figure 2 an example of such a mean between two clouds of points represented as uniform discrete measures. We can see that the barycenter inherits the shapes of the two clouds. We can demonstrate the following result, that can be interpreted as the contracting or shrinking effect of the Wasserstein barycenter.  
**Theorem 1**.: _Consider \(\mathcal{P}^{\prime}\) to be the set of discrete measures over \(\mathbb{R}^{d}\) with finite support and \(\epsilon\in[0,1]\). Let \(P_{X_{1}}\), \(P_{X_{2}}\) and \(P_{X^{*}}\) be defined, respectively, as_  
* \(\sum_{i=1}^{n}\alpha_{i}\delta_{\mathbf{x_{i}}}^{*},\sum_{i=1}^{n}\alpha_{i}= 1,\alpha_{i}>0\)__,
* \(\sum_{j=1}^{n}\beta_{j}\delta_{\mathbf{x_{i}}}^{*},\sum_{j=1}^{n}\beta_{j}=1, \beta_{j}>0\)__,
* \(\sum_{l=1}^{k}\lambda_{l}\delta_{\mathbf{x_{i}}}^{*},\sum_{l=1}^{k}\lambda_{ l}=1,\lambda_{l}>0\)__,  
_with \(P_{X^{*}}\) the unique minimizer of \(\arg\limits_{P_{X}\in\mathcal{P}^{\prime}}\min\epsilon W_{2}^{2}(P_{X},P_{X_{ 1}})+(1-\epsilon)W_{2}^{2}(P_{X},P_{X_{2}})\)._  
_If the above is verified, we have_  
\[\forall l\in\{1,...,k\},\mathbf{x_{i}^{*}}\in\overline{Conv(\mathbf{x_{1}^{ *}},...,\mathbf{x_{n}^{*}},\mathbf{x_{1}^{*}},...,\mathbf{x_{n}^{*}})}\]  
Figure 2: Two initial clouds at the (**left**, in black) and (**right**, in red) and their equal weight Wasserstein barycenter (i.e., their mean) in the (**middle**, in blue).  
_where \(\overline{Conv(\mathbf{x}_{1}^{1},...,\mathbf{x}_{n}^{1},\mathbf{x}_{1}^{2},..., \mathbf{x}_{m}^{2})}\) is the closed convex hull of the set \(\{\mathbf{x}_{1}^{1},...,\mathbf{x}_{n}^{1},\mathbf{x}_{1}^{2},...,\mathbf{x}_ {m}^{2}\}\)._  
The proof for this theorem is provided in Appendix A. This contracting effect, when at work through the Wasserstein-barycenter-based evolutionary operators, can lead to the desertion of the edges of the search space in favor of the center of the space. We propose in the following paragraphs a way to correct this effect.