Clouds of points optimization in convex polygons with evolutionary algorithms based on Wasserstein barycenters - FAYOL - Institut Henri Fayol
Conference Poster Year : 2024

Clouds of points optimization in convex polygons with evolutionary algorithms based on Wasserstein barycenters

Abstract

We consider the optimization of functions where the variables are clouds of points (equivalently bags of vectors). The clouds can have different sizes and the objective functions are invariant under arbitrary permutation of the points within the cloud. Furthermore, no information related to the convexity and/or smoothness of the functions is available. Such functions are of practical interest as they appear, for example, when studying networks of sensors or actuators. The design of a wind farm where the variables are a bag of turbine positions belongs to this family of problems. The above characteristics make it hard to use off-the-shelf algorithms such as gradient-based methods. We introduce a generic approach for such black-box optimization problems where the cloud is modeled as a discrete uniform measure supported by the cloud points. This allows to define stochastic, evolutionary, optimization algorithms whose transition operators (crossover and mutation) use Wasserstein barycenters (see [1] for a review). The crossover operator interpolates between two clouds of points, by calculating their average in the Wasserstein sense. We give an illustration of such an interpolation on clouds in Figure 1. We prove that the Wasserstein barycenter has a contracting effect, which can lead to a premature convergence to degenerated solutions. Specific mutations, once again based on Wasserstein barycenters, are designed to counteract this effect. We first investigate the performance of variants of our Wasserstein-based optimizers by comparing them to classical evolutionary algorithms on a family of test functions including wind farm proxies. The point domains are convex polygons such as squares and trapezes. Second, the points optimization domain is generalized to involve exclusion zones, defined as subdomains which must not include any point of the optimal solution. Exclusion zones constitute a specific type of constraint which is handled by penalization.
Fichier principal
Vignette du fichier
poster.pdf (600.08 Ko) Télécharger le fichier
Origin Files produced by the author(s)
licence

Dates and versions

hal-04645929 , version 1 (12-07-2024)

Licence

Identifiers

  • HAL Id : hal-04645929 , version 1

Cite

Babacar Sow, Rodolphe Le Riche, Julien Pelamatti, Merlin Keller, Sanaa Zannane. Clouds of points optimization in convex polygons with evolutionary algorithms based on Wasserstein barycenters. MASCOT-NUM2024, Apr 2024, Giens, France. ⟨hal-04645929⟩
145 View
23 Download

Share

More