Télécharger le fichier original (Mémoire de fin d’études)

Optimisation par Algorithme Génétique

Introduction

La méthode d’optimisation par algorithme génétique est, initialement développée par John Holland [31] sur les systèmes adaptatifs remontent à 1962, elle utilise à la fois les principes de la survie des structures les mieux adaptées et les échanges d’informations pseudo-aléatoires pour former un algorithme d’exploration qui possède certaines caractéristiques de l’évolution des espèces.
La théorie de l’évolution de Charles Darwin [10] décrit l’évolution des systèmes biologiques selon le principe de la sélection naturelle. C’est sur ce concept d’évolution que se base la notion d’algorithme génétique. Dans un algorithme génétique la sélection au fil des générations s’opère sur des individus. Ces individus évoluent ensuite selon des mécanismes génétiques de croisements et de mutation. Ces principes, sont schématisés par la figure 2.1.
Les algorithmes génétiques ont fait la preuve de leur capacité dans de nombreuses études théoriques et expérimentales. Pour Forrest [19] et Goldberg [25], ces mécanismes de sélection, croisement et mutation permettent aux algorithmes génétiques d’évoluer vers les solutions d’un problème d’optimisation. Cependant, il est important de souligner que par cette méthode seule une petite partie de l’espace de recherche est examinée. Il n’est donc pas raisonnable de penser qu’un algorithme génétique identifie l’optimum global de l’espace, il identifie uniquement les bonnes régions de l’espace. Mais, la puissance d’un algorithme génétique est de converger rapidement vers une zone privilégiée de l’espace de recherche. L’optimisation par algorithmes génétiques a montré son efficacité dans de nombreux domaines.
Plus particulièrement, les algorithmes génétiques permettent de résoudre une large gamme de problèmes géophysiques ou géotechniques. En géophysique, Gallagher et Sambridge [22; 23] utilisent des algorithmes génétiques pour le calage de propagations d’ondes sismiques. Pour eux, le risque des méthodes de type Monte Carlo est de réaliser un grand nombre de calculs inutiles dans des zones défavorables de l’espace de recherche. Il est préférable d’utiliser un algorithme génétique car il combine la robustesse de l’exploration Monte Carlo à une exploitation efficace de l’information.
Simpson et Priest [78] sont parmi les premiers à avoir évoqué l’utilisation d’algorithmes génétiques pour l’optimisation de problèmes géotechniques. Ils appliquent notamment cette méthode à l’identification de la fréquence de discontinuité maximale dans des structures rocheuses complexes. Leur étude montre qu’une solution proche de l’optimum peut être déterminée après le calcul d’une petite fraction de l’espace de recherche.
McCombie et Wilkinson [48] utilisent quant à eux un algorithme génétique pour résoudre des problèmes de stabilité de pentes. Par une étude comparative entre un algorithme génétique et une optimisation classique de type Monte Carlo, ils montrent que cette méthode est plus efficace qu’une méthode traditionnelle d’optimisation numérique pour la caractérisation d’une surface de rupture circulaire critique et du coefficient de sécurité correspondant. Zolfaghari et al. [87] étendent ces résultats aux surfaces de rupture non circulaires. Ils montrent que grâce à cet algorithme génétique, une surface de rupture non circulaire avec un coefficient de sécurité minimal est identifiable en un faible temps de calcul. Ils conseillent d’appliquer ce type d’approche aux problèmes de stabilité de barrages en terre, de pentes naturelles ou à tout autre problème géotechnique à une ou plusieurs couches. De même, Goh [24] utilise un algorithme génétique pour la recherche de surfaces critiques de glissement dans une analyse de stabilité multi-coins. Il montre que cette méthode est suffisamment robuste pour traiter des problèmes multicouches et de couches minces. Sarat Kumar Das [11] a utilisé un algorithme génétique à codage réel pour trouver la surface de rupture réelle et le coefficient de sécurité correspondant par la méthode d’analyse de stabilité des trois coins.
De même pour Mendjel et al. [49 ; 51] ont montré qu’une solution proche de l’optimum peut être déterminée après le calcul d’une petite fraction de l’espace de recherche pour l’identification de coefficient de sécurité minimal et de surface circulaire de la rupture correspondante.
Pal et al. [58] tout comme Samarajiva et al. [67] appliquent les algorithmes génétiques au calage de paramètres de modèles de comportement sur des essais de laboratoire. Ils montrent que contrairement à toute autre méthode de calage, l’utilisation d’un algorithme génétique permet de tenir compte des caractéristiques globales des résultats d’essais de laboratoire selon chaque chemin de contrainte ou de déformation. La méthode de calage traditionnelle est séquentielle et un seul paramètre est identifié à la fois. Or, les paramètres de modèles constitutifs sont souvent interdépendants, la moindre erreur sur un paramètre affecte toute la chaîne d’identification. Comme un algorithme génétique identifie plusieurs paramètres simultanément, il évite ce genre de problèmes.
Levasseur et al. [38 ; 39 ; 40 ; 41 ; 42] et Malécot et al. [46] en géotechnique expliquent quant à eux qu’un algorithme génétique permet d’identifier un plus grand nombre de paramètres ainsi que des paramètres corrélés ou peu sensibles contrairement aux méthodes de gradient qui fonctionnent plus difficilement dans ces cas.
Levasseur [39] a posé la problématique d’analyse inverse en géotechnique comme suit : quelles informations concernant les paramètres constitutifs du sol est-il possible d’obtenir à partir de mesures géotechniques in situ ?
Ainsi, l’optimisation par algorithme génétique s’avère être un outil puissant pour optimiser des problèmes variés de géotechnique. Cependant comme le souligne Goh [24], le principal inconvénient des algorithmes génétiques par rapport aux autres méthodes est la puissance informatique nécessaire pour mener l’optimisation. Le coût de calcul d’une optimisation par algorithme génétique est supérieur à celui nécessaire à toute autre méthode d’optimisation. Pour Simpson et Priest [78], un algorithme génétique est une méthode fortement probabiliste. Plus le problème est mal posé, plus le coût de calcul augmente [23], il est donc difficile de savoir à l’avance le nombre d’évaluations nécessaires à l’identification de l’optimum.
Les algorithmes génétiques ont comme principal objectif d’améliorer une solution. Leur priorité est d’atteindre rapidement une performance de niveau satisfaisant. Ils isolent rapidement des zones intéressantes d’un espace de recherche, et n’ont besoin que des valeurs de la fonction à optimiser associée à chaque individu. Cette caractéristique fait des algorithmes génétiques une méthode très générale comparée à beaucoup de méthodes d’exploration. Pour Renders [62] les algorithmes génétiques sont une classe de stratégies de recherche réalisant un compromis équilibré et raisonnable entre l’exploration et l’exploitation de l’espace de recherche.
Un algorithme génétique est une procédure itérative sur un échantillon de candidats pour la résolution d’un problème d’optimisation.

Principe d’optimisation

Après avoir définit les paramètres à optimiser, l’algorithme génétique recherche la ou les extrema d’une fonction définie sur un espace de données. Pour l’utiliser on définit les principales étapes d’optimisation par les points suivants : Codage, individu, population et espace de recherche
La concaténation des paramètres recherchés forme un individu, les individus sont codés sous formes (décimal, analogique ou binaire), comme le souligne Magnin [44], le codage binaire facilite le codage de toutes sortes d’objets : des réels, des entiers, des chaines de caractères…
Renders [62] précise qu’il garantit une meilleure indépendance du codage par rapport au problème.
Dans cette étude les paramètres sont codés sous forme binaire, la chaine de bits codant un paramètre s’appelle un gène.
Une population est un ensemble de Nindividus individus (chromosomes). Chaque individu est un vecteur de Nparamètre paramètres il est représenté sous forme d’une chaine de Nbit bits contenant toute l’information nécessaire à la description d’un point dans l’espace de recherche.
Levasseur [39] montre que l’algorithme génétique se caractérise par des constantes telles que la taille de la population Nindividus et la longueur de la chaine de bits Nbit. La taille de l’espace de recherche doit être choisie en fonction des bornes minimale Pimin et maximale Pimax supposées pour chaque paramètre Pi. La taille de la chaine de bits doit être choisie en fonction de l’incertitude ΔPi acceptée sur l’évaluation des paramètres
La taille de la population Nindividus joue un rôle important sur l’efficacité de l’algorithme génétique [35]. Si la taille de la population est trop petite, l’algorithme converge prématurément avant d’identifier l’optimum. Si la taille de la population est trop grande, la solution est meilleure mais le temps de calcul est beaucoup plus long [22 ; 23; 44 ; 62; 67]. Par raison de simplicité, une taille de population constante est couramment choisie dans la littérature [19]. Pour Goldberg [25], il n’y a aucune raison particulière pour garder la taille de la population constante au cours d’optimisation. Une population est donc un tableau d’individus dans lequel chaque élément représente les paramètres codés (figures 2.2 (a)et 2.2(b)).
La taille de la population initiale choisie pour cette thèse est deux fois plus grande que la taille de la population des générations suivantes. Ce qui permet d’avoir une bonne exploration initiale de l’espace de recherche et facilite la convergence de l’algorithme génétique.

Evaluation de la population

Les individus choisis d’une population initiale générée aléatoirement, sont testés pour qualifier chaque individu par une évaluation numérique correspondant à la fonction erreur (fonction objective). Le peu d’hypothèses requises sur cette fonction permet de traiter des problèmes très complexes.
Pour cette thèse on a deux fonctions erreurs à examiner selon les deux problèmes à étudier.
La première fonction erreur, correspond aux équations d’équilibre limite pour l’analyse de la stabilité des talus. Cette fonction est pour but de faire chercher le coefficient de sécurité minimal pour la surface de glissement critique. Elle dépend de la méthode de résolution du problème.
La deuxième fonction erreur, est faite pour l’identification de paramètres hydromécaniques d’un sol non saturé. Elle est définit pour l’estimation de l’écart entre une courbe calculée numériquement (décrite par N points Uni) et une courbe de référence mesurée in situ (décrite par N points Uei) est évalué par la fonction d’écart type suivante notée Ferr

Mécanisme d’évolution de la population

La population est évolue vers les zones les plus favorables de l’espace de recherche après avoir évalué chaque individu. Chaque nouvelle population correspond à ce qu’on appelle en biologie une nouvelle génération. Une génération correspond à une itération de l’algorithme.
Une nouvelle génération est créée en utilisant des parties des meilleurs individus de la génération précédente. Pour cela trois opérateurs se succèdent : sélection, croisement et mutation.
 Sélection
La sélection sert à éliminer d’une population les individus dont la fonction erreur est mauvaise. Dans la littérature, deux méthodes existent pour sélectionner les individus : une méthode dite roue de loterie biaisée et une méthode dite élitiste [25].
Goldberg [25] montre que pour les fonctions erreurs unimodales, la méthode élitiste augmente significativement les performances de l’algorithme (stabilité, efficacité et rapidité de convergence), alors que pour des fonctions erreurs multimodales, la méthode élitiste détériore les performances. Nous avons choisi dans notre problème unimodal la méthode de sélection élitiste. Dans cette méthode les individus sont triés selon leur fonction erreur. Seuls les individus aux plus faibles valeurs de fonction erreur sont sélectionnés pour survivre dans la génération suivante. Cette méthode assure la conservation d’un plus grand nombre d’individus performants d’une génération à une autre. Ainsi, après l’évaluation de Ferr pour chaque individu de la génération k, les individus sont triés par ordre croissant de Ferr. Sur une population de Nindividus individus, quelques individus sont conservés pour construire une nouvelle génération k+1, les autres sont éliminés. Les individus conservés forment ce que l’on appelle une population parent. Traditionnellement, le nombre d’individus conservé est compris entre1/3 et 2/3 de l’ensemble des individus de la population. Dans cette étude nous avons choisi 1/3 d’individus conservés à chaque génération, pour une diversité génétique et une convergence non prématurée.
 Croisement et mutation
Ces mécanismes sont appliqués aux individus parent pour former une population enfant. Le croisement caractérise la phase d’échange d’informations entre deux individus parents sélectionnés aléatoirement. Ils sont croisés entre eux pour former de nouveaux individus (Tableau.2.1), Pc détermine le nombre de combinaisons de paramètres recréées à chaque itération. De Jong [14] a étudié l’impact de ce taux de croisements sur le processus d’optimisation. Il a conclu que Pc =2/3 est un compromis raisonnable. Le croisement se fait entre les morceaux coupés des individus, l’emplacement de Ncoupure coupures sur la chaine de bits est choisi aléatoirement et indépendamment des gènes, cela signifie qu’un gène, peut être coupé en plusieurs morceaux comme être ne pas coupé du tout. Pal et al. [59] montrent qu’utiliser un nombre de coupure égale au nombre de paramètres (Ncoupure = Nparamètre), augmente la convergence d’un algorithme génétique pour la géotechnique. C’est notre choix dans cette thèse.
La mutation fabrique des erreurs de recopie, pour diversifier les individus de la nouvelle population (inversion d’un bit d’un gène) (Tableau.2.2). Comme ce phénomène est rare dans la nature, le taux de mutation doit être faible [58]. Goldberg [25] recommande d’utiliser un taux de mutation Pm entre 0.001 et 0.1. Davis [12], comme Stoffa et Sen [80], considèrent qu’un taux de mutation de l’ordre de 0.01 est un choix raisonnable. Pour combattre la perte prématurée de chaines de bits, il est souvent conseillé d’augmenter le taux de mutation. Pour Magnin [44], les probabilités de mutation doivent dépendre du gène considéré et de la taille de la population. Levasseur [39] montre que fixer un taux de mutation à chaque génération en fonction du nombre de paramètres permet une bonne convergence de l’algorithme et limite le temps de calcul. Ces références montrent que la littérature est floue sur le choix de Pm.
Pour cette thèse on a pris, pour l’application sur l’analyse de stabilité des talus Pm =0.09. Et pour l’identification de paramètres à partir de mesures in situ, on a pris le choix fait par Levasseur [39] : = 2 è / (2.4)
Les deux phases de croisement et de mutation créent de nouveaux individus qui ont des chances d’être meilleurs. D’après Davis [12], la combinaison des deux mécanismes de croisement et de mutation pour générer de nouvelles combinaisons de paramètres permet de mieux converger vers une solution que l’utilisation d’un seul de ces mécanismes. La phase de croisement est une étape très importante de l’algorithme génétique. C’est elle qui caractérise la méthode, la rende différente des autres algorithmes d’optimisation. En combinant des blocs de bonnes solutions sur divers individus, le croisement accélère le processus de recherche. La phase de mutation sert à introduire de la diversité dans une population d’individus. Ce mécanisme évite à l’algorithme de converger prématurément vers un minimum local.
 Critères d’arrêt
Les deux étapes d’évaluation et d’évolution de la population sont répétées jusqu’à ce qu’un critère d’arrêt soit satisfait. Les critères d’arrêt envisageables pour les algorithmes génétiques sont :
– Un nombre maximal de génération : si l’algorithme ne converge pas vers une solution, la procédure est stoppée après un nombre maximal de calculs.
– La convergence vers l’optimum : si la fonction erreur ou la moyenne sur la fonction erreur converge vers la solution.

Conclusion

Un algorithme génétique est une méthode stochastique itérative d’optimisation qui opère sur des ensembles de points codés, à partir d’une population initiale, et qui est bâti à l’aide de trois opérateurs : croisement, mutation et sélection. Les deux premiers sont des opérateurs d’exploration de l’espace, tandis que le dernier fait évoluer la population vers les optima d’un problème. Une petite partie de l’espace de recherche est examinée, il n’est donc pas raisonnable de penser qu’un algorithme génétique identifie à coup sûr l’optimum global de l’espace de recherche. Malgré tout, il isole rapidement les zones intéressantes.
Les paramètres optimaux caractérisant un algorithme génétique varient d’un problème à un autre [12 ; 62 ; 80]. Il semble peu réaliste d’attaquer le problème de front, en analysant mathématiquement et rigoureusement les phénomènes intervenants dans les algorithmes génétiques, pour essayer d’en tirer une théorie applicable à tout type de problème géotechnique [39]. Cependant, il est important de bien choisir les paramètres caractérisant les algorithmes génétiques pour leur bonne utilisation.
Ces particularités de la méthode d’optimisation par algorithme génétique justifient son intérêt pour la géotechnique. Pour montrer l’efficacité de la méthode, deux programmes ont été élaborés et validés par des exemples tirés de la littérature pour l’analyse de la stabilité des talus en déterminant la surface de glissement critique et le coefficient de sécurité minimal correspondant. Un autre programme est conçu pour l’estimation de la perméabilité d’un versant à multicouches en se basant sur des mesures in situ.

Table des matières

Introduction générale
Chapitre 1 : Méthodes d’optimisation
1.1 Introduction
1.2 Principe d’analyse inverse
1.3 Analyse inverse par méthode numérique directe : algorithmes d’optimisation
1.3.1 Les méthodes énumératives
1.3.2 Les méthodes déterministes
1.3.3 Les méthodes stochastiques
1.3.3.1 Les méthodes Monte Carlo
1.3.3.2 Le recuit simulé
1.3.3.3 Les algorithmes de voisinage
1.3.3.4 Les réseaux de neurones
1.3.3.5 Algorithmes évolutionnaires
1.4 Conclusion
Chapitre 2 : Optimisation par Algorithme Génétique
2.1 Introduction
2.2 Principe d’optimisation
 Codage, individu, population et espace de recherche
 Evaluation de la population
 Mécanisme d’évolution de la population
o Sélection
o Croisement et mutation
o Critères d’arrêt
2.3 Conclusion
Chapitre 3 : Analyse de la stabilité des talus
3.1 Introduction
3.2 Méthodes de calcul de stabilité des talus
3.3 Méthodes de calcul à la rupture
3.3.1 Méthodes des blocs
3.3.2 Méthodes des tranches
3.3.2.1 Méthode de Fellenius (1927)
3.3.2.2 Méthode de Bishop (1955)
3.3.2.3 Méthode de Morgenstern and Price (1965)
3.3.2.4 Méthode de Spencer (1967)
3.3.2.5 Méthode de Janbu simplifiée
3.4 Conclusion
Chapitre 4 : Développement de deux processus de résolution d’équations d’équilibre limite comme approches d’optimisation dans l’analyse de la stabilité des talus
4.1 Introduction
4.2 Processus de résolution par algorithme génétique (cas de surface de rupture circulaire)
4.2.1 Applications numériques
4.3 Processus de résolution par algorithme génétique (cas de surface de rupture non circulaire)…..
a. Résolution de l’équation de Morgenstern-Price pour trouver le coefficient de sécurité qui assure l’équilibre au maximum pour chaque surface de rupture
b. Détermination de la surface de rupture non circulaire critique
4.3.1 Applications numériques
4.4 Conclusion
Chapitre 5 : Identification des paramètres hydromécaniques d’un sol non saturé d’un talus par algorithme génétique
5.1 Introduction
5.2 Présentation et modélisation du versant.
5.3 Principe d’optimisation par algorithme génétique
5.4 Résultats de l’identification
5.5 Conclusion
Conclusion générale
Annexe A : Code de calcul par éléments finis (Plaxis v8.2 et PlaxFlow)
A.1 Introduction
A.2 Code de calcul Plaxis v8.2
A.2.1 Options par défaut et solutions approchées
A.2.2 Lois de comportement dans Plaxis
A.2.2.1 Modèle de Mohr-Coulomb
A.2.2.2 Modèle élastoplastique avec écrouissage (Hardening Soil Model H.S.M)
A.3 Code de calcul PlaxFlow
Bibliographie

Télécharger le rapport complet