Optimisation génétique

[The following content has been elaborated on the basis of the work done by G. Emperauger during his internship at AREP.]

1. Introduction

Some problems in physics are irregular or not mathematically differentiable: an applied case for a building could be the choice between double and single glazing, or the open/closed position of a window. Classical resolution algorithms are inefficient in such cases because they are often based on the computation of a gradient to find solutions. In simple terms, classical methods look at the variation of a function with respect to an increment of the variable (one can check the excellent illustrated course from Stanford University), however when the function is not continuous and therefore differentiable, it is difficult to calculate this gradient.

Genetic algorithms, imitating the natural selection of the most capable, propose an alternative solution to this problem that we will discuss here. The principle is to generate a set of potential solutions to the optimization problem (called "individuals", and forming a "population"), and to make them evolve towards the optimal solution as the generations go by. Genetic algorithms are often confused with particle swarm optimization (PSO) algorithms which work like a swarm of insects moving in space towards the best solution obtained by the swarm, without selecting the most suitable ones.

2. Principle

Darwinian selection of the fittest is based on the "survival" of individuals that are best adapted to their environment. The algorithm mimics this concept by selecting the combinations of parameters that are "fittest", i.e. that minimize or maximize a cost function established by the user.

A genetic optimization procedure consists of the following steps (also shown in the figure below):

The cross-breeding of individuals, mimicking chromosomal crossover, allows the exchange of characteristic traits of "parent" individuals to create the next generation.
The application of stochastic mutations which bring a random component and allow to avoid staying on local minima, although they do not guarantee any result. When the mutation rate is important, the diversity of solutions is great but the algorithm can be slow to converge.
The evaluation of the individuals with respect to the fixed objective of minimization/maximization: this is generally the time-consuming step of the calculation (in our applications it could be a dynamic thermal calculation).
The ranking of individuals according to the chosen criterion(s).
Animation depicting the selection of individuals, their cross-breeding, the occurrence of random mutations and their classification [from G. Emperauger's internship presentation].

Note that at the stage of evaluation of the individuals in the population, each individual can be evaluated independently, which offers an interesting potential for computational parallelization.

Necessarily, the size of the population is a performance factor for the algorithm: the larger it is, the better the solution space is scanned. However, the computational cost increases with the population size because all individuals must be evaluated.

3. Multi-objective optimization

Dans bien des cas, l’optimisation consiste à concilier deux objectifs contradictoires. Par exemple, la minimisation à la fois de l’impact environnemental des matériaux de construction choisi et le coût total d’un ouvrage consiste en deux objectifs contradictoires (les matériaux à faible contenu de carbone sont souvent plus onéreux). Ainsi on optimise souvent un objectif au détriment d’un autre. Afin de les classer les uns par rapport aux autres, on introduit la notion de domination : sur la figure ci-dessous, au regard des objectifs 1 et 2, l’individu matérialisé par le point bleu domine les solutions situées dans le coin supérieur droit mais est dominé par celles dans le coin inférieur gauche. Pour les deux autres coins, l’analyse est moins aisée car selon l’un des objectifs, le point bleu est meilleur tandis que par rapport à l’autre il est moins bon.

Relation de domination entre solutions par rapport aux objectifs 1 et 2 [tiré de la présentation de stage de G. Emperauger]

The set of solutions that are not dominated constitutes the Pareto front : On the type of graph such as the previous one, it is the low boundary of the cloud. In practice, these are the solutions for which we cannot improve one objective without degrading the second.

To evaluate the disparity of the solutions or the extent of the Pareto front, we introduce the notion of hypervolume. We place ourselves at the level of a reference point which is dominated by the set of solutions (see figure below) to be able to calculate the area between this point and the set of Pareto points. Numerically, dedicated libraries in different languages allow to compute it (pygmo/pagmo).

otion of hypervolume computed with respect to a reference point to evaluate the extent of the solution set [from G. Emperauger's internship report].

The hypervolume is also an indication of the convergence of the algorithm. Its evolution over the generations can give an idea of the convergence of the solutions, as shown on the example of the following figure.

Exemple d’évolution de l’hypervolume en fonction des générations [tiré du rapport de stage de G. Emperauger].

4. Application examples

In this section we present some practical use cases.

A use case of the method has been to determine for a glazed hall the combination between solar factor, thermal conductance U of the glazing and surface emissivity of the slab under the glass roof, in order to minimize the discomfort in summer and in winter. The result obtained is shown in the following figure. It can be seen that in winter high solar factors and low U coefficients dominate, while the opposite is true in summer.

Example of an optimization result: over the generations, we observe the progression towards the origin of the Pareto front (non dominated, optimal combinations).

A case of discrete optimization is the choice of the number and positioning of windows on a glazed facade, illustrated below (the aim is to maximize comfort in summer and reduce the cost of installing/maintaining windows - number and height - this will be detailed in a futur conference paper). On constate que le front de Pareto est moins « lisse » du fait des variables discrètes qui influent sur les fonctions objectifs.

Discrete optimization for the number and position of openings on a glass façade [from the internship report of G. Emperauger].

However, the choice of objective functions is crucial: they act as the algorithm's "compass". Thus when an objective function is badly chosen. As an example, the result below is a variant of the previous one: it consists in determining the position of a given number of windows on the studied façade. The objective function for cost was chosen such that it favors windows placed in height and thus the algorithm converged to this type of solution.