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.
Origin | Files produced by the author(s) |
---|---|
licence |