Optimisation Génétique

Le contenu qui suit a été élaboré en s’inspirant notamment des travaux de stage effectués au sein d’AREP par G. Emperauger

Introduction

Certains problèmes en physique sont irréguliers ou ne sont mathématiquement pas différentiables : un cas appliqué au bâtiment pourrait être le choix entre double et simple vitrage, ou la position ouverte/fermée d’une fenêtre. Les algorithmes classiques de résolution sont dans ce cas inefficaces car bien souvent ils sont basés sur le calcul d’un gradient pour la recherche de solutions. En termes simples, les méthodes classiques regardent la variation d’une fonction par rapport à un incrément de la variable, cependant lorsque la fonction n’est pas continue et donc différentiable, il est ardu de calculer ce gradient.

Les algorithmes génétiques, imitant la sélection naturelle du plus apte, proposent une solution alternative à ce problème que nous allons aborder ici. Le principe est de générer un ensemble de solutions potentielles du problème d’optimisation (appelés “individus”, et formant une “population”), et de les faire évoluer vers la solution optimale au fur et à mesure des générations. Les algorithmes génétiques sont souvent confondus avec les algorithmes d’optimisation par essaims particulaires (Particle Swarm Optimisation – PSO) qui fonctionnent comme une nuée d’insectes se dirigeant dans l’espace en direction de la meilleure solution obtenue par l’essaim, sans sélection des plus aptes.

Principe

La sélection darwinienne du plus apte repose sur la “survie” des individus qui sont les mieux adaptés à leur environnement. L’algorithme imite ce concept en sélectionnant les combinaisons de paramètres qui sont “les plus aptes”, c’est à dire qui minimisent ou maximisent une fonction de coût établie par l’utilisateur.

Le déroulement d’une procédure d’optimisation génétique est la succession des étapes suivantes (également illustrée sur la figure ci-après) :

• Le croisement des individus, imitant le croisement chromosomique, permet d’échanger des traits caractéristiques des individus “parents” pour créer la génération d’après.
• L’application de mutations stochastiques qui apportent une composante aléatoire et permettent d’éviter de rester sur des minima locaux, bien qu’elles ne garantissent pas de résultat. Lorsque le taux de mutation est important, la diversité des solutions est grande mais l’algorithme peut être lent à converger.
• L’évaluation des individus par rapport à l’objectif fixé de minimisation/maximisation : c’est en général l’étape chronophage du calcul (dans nos applications il pourra s’agir d’un calcul thermique dynamique).
• Le classement des individus selon le(s) critère(s) choisi(s).

On notera qu’à l’étape d’évaluation des individus de la population, chaque individu peut être évalué indépendamment, ce qui offre un potentiel de parallélisation intéressant.

Nécessairement, la taille de la population est un facteur de performance pour l’algorithme : plus celle-ci est grande, mieux l’espace des solutions est balayé. Cependant le coût calculatoire augmente avec la population car il faut évaluer tous les individus.

Optimisation bi-objectif

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.

L’ensemble des solutions qui ne sont pas dominées constitue le front de Pareto  : sur le type de graphe tel que le précédent, il s’agit de la frontière basse du nuage. Concrètement, ce sont les solutions pour lesquelles on ne peut pas améliorer un objectif sans dégrader le second.

Pour évaluer la disparité des solutions ou l’étendue du front de Pareto, on introduit la notion d’hypervolume. On se place au niveau d’un point de référence qui est dominé par l’ensemble des solutions (voir figure ci-après) pour pouvoir calculer l’aire entre celui ci et l’ensemble des points de Pareto. Numériquement, des librairies dédiées en différents langages permettent de le calculer ( pygmo / pagmo ).

L’hypervolume est également un indicateur de convergence de l’algorithme. Son évolution au fil des générations peut donner une idée de la convergence des solutions, comme montré sur l’exemple de la figure qui suit.

Exemples d’application

On présente dans cette section quelques cas d’usage pratiques.

Un cas d’utilisation de la méthode a consisté à déterminer pour une halle vitrée la combinaison entre facteur solaire, conductance thermique \(U\) du vitrage et émissivité de surface de la dalle sous verrière, afin de minimiser l’inconfort en été et en hiver. Le résultat obtenu est donné sur la figure suivante. On constate que pour l’hiver les facteurs solaires élevés et les coefficients \(U\) faibles dominent, tandis que c’est l’inverse pour l’été.

Un cas d’optimisation discrète est celui du choix du nombre et du positionnement des ouvrants sur une façade vitrée dont l’illustration est donnée ci-dessous (il s’agit de maximiser le confort n été et de réduire le coût lié à l’installation/maintenance des fenêtres – nombre et hauteur). On constate que le front de Pareto est moins “lisse” du fait des variables discrètes qui influent sur les fonctions objectifs.

Le choix des fonctions objectif est cependant crucial : celles-ci font office de “boussole” de l’algorithme. Ainsi lorsqu’une fonction objectif est mal choisie. À titre d’exemple le résultats ci-dessous est une variante du précédent : il s’agit de déterminer la position d’un nombre donnée d’ouvrants sur la façade étudiée. La fonction objectif de coût était choisie telle qu’elle favorise les fenêtres placées en hauteur et ainsi l’algorithme a convergé vers ce type de solutions.