Les aléas menaçant dans les hautes terres centrales de Madagascar

Les algorithmes génétiques 

Principe des algorithmes génétiques

Les AG proviennent de la modélisation de la théorie de l’évolution de C. Darwin (Darwin 1859). Les AG sont des algorithmes d’optimisation, ils font partie du cadre plus générale des métaheuristiques évolutionnaires comprenant, entre autres, les AG (Holland 1975), les stratégies d’évolution (Beyer 2001) et la programmation évolutionnaire (Fogel et al. 1966). Une étude bibliographique très riche a été présentée par Kicinger dans (Kicinger et al. 2005). Cette étude regroupe des travaux de recherche récents dans le domaine de l’optimisation structurale par méthode évolutionnaire, en particulier par AG. Initialement développés par Holland (1975), les AG sont devenus populaires à partir de la publication du livre « Genetic Algorithms in search, optimization and machine learning » de Goldberg (1989). La forme canonique d’un algorithme génétique est donnée par : Initialiser la population d’individus : P0 Evaluer les individus de la population P0 t=0 Répéter Sélectionner les individus pour la production : 𝑃𝑡 𝑝𝑎𝑟𝑒𝑛𝑡 ⊆ 𝑃𝑡 Croiser les individus de 𝑃𝑡 𝑝𝑎𝑟𝑒𝑛𝑡 : 𝑃𝑡 𝑒𝑛𝑓𝑎𝑛𝑡 −1 Muter les individus de 𝑃𝑡 𝑒𝑛𝑓𝑎𝑛𝑡 : 𝑃 𝑡 𝑒𝑛𝑓𝑎𝑛𝑡 Sélectionner les individus de 𝑃𝑡 𝑝𝑎𝑟𝑒𝑛𝑡 ∪ 𝑃 𝑡 𝑒𝑛𝑓𝑎𝑛𝑡 à conserver Les individus sélectionnés forment de la population 𝑃𝑡+1 t=t+1 Tant que condition d’arrêt non vérifiée Le principe général du fonctionnement d’un algorithme génétique est représenté sur la figure 4.3 : on commence par générer une population d’individus de façon aléatoire. Pour passer d’une génération k à la génération k+1, les trois opérations suivantes sont répétées pour tous les éléments de la population k. Des couples de parents P1 et P2 sont sélectionnés en fonction de leurs adaptations. L’opérateur de croisement leur est appliqué avec une probabilité Chapitre 4. Moteur de reconnaissance GA/HMM 87 Pc (généralement autour de 0.6) et génère des couples d’enfants C1 et C2. D’autres éléments P sont sélectionnés en fonction de leur adaptation. L’opérateur de mutation leur est appliqué avec la probabilité Pm (Pm est généralement très inférieur à Pc) et génère des individus mutés P0. Le niveau d’adaptation des enfants (C1, C2) et des individus mutés P0 sont ensuite évalués avant insertion dans la nouvelle population. Figure 4.3 – Principe général des algorithmes génétiques. Différents critères d’arrêt de l’algorithme peuvent être choisis :  Le nombre de générations que l’on souhaite exécuter peut être fixé à priori. C’est ce que l’on est tenté de faire lorsque l’on doit trouver une solution dans un temps limité.  L’algorithme peut être arrêté lorsque la population n’évolue plus ou plus suffisamment rapidement. Nous allons maintenant détailler chacun de ces points. 

Description détaillée

Codage des données Historiquement le codage utilisé par les AG était représenté sous forme de chaînes de bits contenant toute l’information nécessaire à la description d’un point dans l’espace d’état. Ce type de codage a pour intérêt de permettre de créer des opérateurs de croisement et de mutation simples. C’est également en utilisant ce type de codage que les premiers résultats de convergence théorique ont été obtenus. Cependant, ce type de codage n’est pas toujours bon comme le montrent les deux exemples suivants :  deux éléments voisins en terme de distance de Hamming ne codent pas nécessairement deux éléments proches dans l’espace de recherche. Cet inconvénient peut être évité en utilisant un codage de Gray.  Pour des problèmes d’optimisation dans des espaces de grande dimension, le codage binaire peut rapidement devenir mauvais. Généralement, chaque variable est représentée par une partie de la chaîne de bits et la structure du problème n’est pas bien reflétée, l’ordre des variables ayant une importance dans la structure du chromosome alors qu’il n’en a pas forcément dans la structure du problème. Les AG utilisant des vecteurs réels (Goldberg 1991 ; Wright 1991) évitent ce problème en conservant les variables du problème dans le codage de l’élément de population sans passer par le codage binaire intermédiaire. La structure du problème est conservée dans le codage.

Génération aléatoire de la population initiale

Le choix de la population initiale d’individus conditionne fortement la rapidité de l’algorithme. Si la position de l’optimum dans l’espace d’état est totalement inconnue, il est naturel de générer aléatoirement des individus en faisant des tirages uniformes dans chacun des domaines associés aux composantes de l’espace d’état en veillant à ce que les individus produits respectent les contraintes (Michalewicz and Janikov 1991). Si par contre, des informations à priori sur le problème sont disponibles, il parait bien évidemment naturel de générer les individus dans un sous-domaine particulier afin d’accélérer la convergence. Dans l’hypothèse ou la gestion des contraintes ne peuvent se faire directement, les contraintes sont  généralement incluses dans le critère à optimiser sous forme de pénalités. Il est clair qu’il vaut mieux, lorsque c’est possible ne générer que des éléments de population respectant les contraintes. 

Évaluation

A chaque solution, on associe une fonction performance « fitness » reliée à la valeur de la fonction objectif. Cette fonction décrit le mérite de l’individu qui est représenté par un chromosome. L’évaluation des individus en optimisation topologique des structures se fait par une méthode d’analyse numérique des structures, généralement la méthode des éléments finis. La fonction performance est très importante pour un AG au même titre que le codage. En effet, pour que les AG se comportent bien, nous devons trouver une manière de formuler des fonctions performance ne comportant pas trop de maxima locaux et ne présentant pas de maximum local isolé. La construction de la fonction performance est évidente pour certains problèmes. Pour les problèmes de maximisation par exemple, la fonction mérite peut être égale à la fonction objectif. Par contre, pour les problèmes de minimisation, l’objectif est de trouver des solutions pour lesquelles la fonction objectif atteint des valeurs minimales. Dans ce cas, la fonction performance choisie est la réciproque de la fonction objectif. Dans tous les cas, l’AG cherche à maximiser la fonction performance qui, dans le cadre d’un problème de minimisation, prend la forme suivante : 𝐹𝑖𝑡𝑛𝑒𝑠𝑠 𝑥𝑖 = 1 𝑓(𝑥𝑖) (4.27) Ou 𝑓(𝑥𝑖) représente la fonction objectif évaluée pour l’individu𝑥𝑖 . Un choix classique de fonction objectif est la compliance. Ce choix se justifie pleinement dans le cadre d’une approche déterministe ou il est nécessaire de dériver pour pouvoir procéder à une analyse de sensibilité. Dans un AG, ou l’approche stochastique ne nécessite pas de dérivation, le choix de la compliance comme fonction objectif n’est pas aussi vital. Jakiela et ses collaborateur (Jakiela 2000) ont posé le problème d’optimisation sous forme de maximisation de la raideur de la structure en supposant que la raideur est inversement proportionnelle au déplacement maximal ‘𝛿𝑚𝑎𝑥 ’ de la structure : 𝐹𝑖𝑡𝑛𝑒𝑠𝑠 = 1 |𝛿𝑚𝑎𝑥 | (4.28)  La raideur n’étant pas une grandeur différentiable, les méthodes déterministes ne sont opérationnelles pour maximiser mérite définie par (1-10). En revanche, ce n’est pas le cas pour les méthodes stochastique, telles que les AG, qui sont exemptées de l’analyse de sensibilité.

Gestion des contraintes

Un élément de population qui viole une contrainte se verra attribuer une mauvaise fitness et aura une probabilité forte d’être éliminé par le processus de sélection. Il peut cependant être intéressant de conserver, tout en les pénalisant, les éléments non admissibles car ils peuvent permettre de générer des éléments admissibles de bonne qualité. Pour de nombreux problèmes, l’optimum est atteint lorsque l’une au moins des contraintes de séparation est saturée, c’est-à-dire sur la frontière de l’espace admissible. Gérer les contraintes en pénalisant la fonction fitness est difficile, un « dosage » s’impose pour ne pas favoriser la recherche de solutions admissibles au détriment de la recherche de l’optimum ou inversement. Disposant d’une population d’individus non homogène, la diversité de la population doit être entretenue au cours des générations afin de parcourir le plus largement possible l’espace d’état. C’est le rôle des opérateurs de croisement et de mutation.