Soutenance mémoire
Télécharger le fichier pdf d’un mémoire de fin d’études
ALGORITHMES É VOLUTIONNAIRES (AES)
Les algorithmes évolutionnaires (AEs) sont des méthodes stochastiques qui simulent le processus de l’évolution naturelle dans la résolution des problèmes d’optimisation [Zitzler et al, 2003]. Ils reposent sur l’analogie avec l’un des princip es Darwiniens les plus connus : la survie de l’individu le mieux adapté [Lepadatu, 2006]. Ils sont basés sur la notion de « population d’individus », dans laquelle chaque individu représente une solution potentielle de l’espace de recherche. Ces algorithmes permettent de surmonter certains problèmes rencontrés avec les méthodes classiquesCe. sont des méthodes d’optimisation globales qui assurent la convergence vers les optima globaux malgré la présence d’optima locaux, et indépendamment de la répartition de la opulation initiale. Ils peuvent également être utilisés pour des problèmes discrets et discontinus. En outre, en tant qu’algorithme à base de population, leur parallélisation est aisée : ilsuffit de distribuer l’évaluation des fonctions coût sur autant de processeurs qu’il y a d’individu s dans la population. Ils sont fréquemment utilisés à cause de leur robustesse et de leur souplesse, qui leurs permettent d’aborder les problèmes les plus raides.
Historiquement, les algorithmes évolutionnaires sont utilisés depuis les années soixante. Ils se divisent en quatre catégories principales, voir laFigure 5.
Dans le reste de cette section, on présente la description du principe de fonctionnement d’un algorithme évolutionnaire, puis des algorithmes génétiques et des stratégies d’évolution, avant de discuter de la différence entre les AEs mono-objectif et multi-objectifs.
Principe de fonctionnement d’un algorithme évolutionnaire
Comme présenté par l’organigramme de laFigure 6, le principe de fonctionnement d’un AE est extrêmement simple. On part d’un ensemble initial d’individus (chacun correspondant à une valeur du jeu de paramètres), nommé « population parent initiale » et générée le plus souvent d’une manière aléatoire dans l’espace de recherche. Ensuite, on évalue de manière exacte la performance de chaque individu en calculant la valeur de la fonction coût correspondant à son jeu de paramètres. L’applicatio n des trois opérateurs génétiques de « sélection, croisement et mutation » permet de créer un nouvel ensemble d’individus appelé « population enfant ». Cette population est évaluéeà son tour pour indiquer la performance de chacun de ses individus. Cette connaissance permet de décider lesquels des individus enfants méritent de remplacer certains parents. La nouvellepopulation obtenue, appelée « population parent », constitue la population parent de la nouvelle génération. Si les critères d’arrêt sont vérifiés, on considère la ou les solutions obtenuescomme satisfaisantes, autrement, on recommence le cycle jusqu’à satisfaction de ces cri tères.
Le critère d’arrêt d’un AE peut être la convergencede l’ensemble des individus de la génération courante vers un même extremum, dans lecas d’un problème mono-objectif, ou alors vers un même ensemble optimal de Pareto, dansle cas multi-objectifs. Le plus souvent, l’algorithme est arrêté au bout d’un nombre d’itérations (générations) fixé a priori.
Algorithme génétique et stratégie d’évolution
Algorithme génétique
Les algorithmes génétiques (AGs) ont été mis au point par John Holland de l’université du Michigan aux États-Unis dans les années 60 [Holland, 1962]. Ils ont ensuite été raffinés par De Jong [De Jong, 1975] et popularisés par Goldberg [Goldberg, 1989] et Goldberg et Holland [Goldberg and Holland, 1988]. Suivant le type de codage utilisé, c’est-à-dire suivant la représentation des paramètres utilisée à la place des paramètres eux-mêmes, on distingue deux types d’algorithmes génétiques : les AGs avecun codage binaire et ceux avec un codage réel.
Représentation
Représentation binaire :
Le codage binaire consiste à représenter chaque vecteur des paramètres X par une chaîne de bits dont chaque instance prend la valeur 0 ou 1. Cette chaîne peut être une concaténation des différents paramètres à optimiser, chaque paramètreétant transformé en sa valeur binaire avec un nombre de bits fixé a priori. La Figure 7 présente un exemple du codage binaire d’une solution avec trois paramètres, soit X10, 6, 3 , dans laquelle on utilise 5 bits pour coder chacun des trois paramètres.
Ce codage s’adapte bien aux problèmes où les paramètres ont une valeur binaire, comme les problèmes booléens ou discrets, ou une valeur entière. Pour les problèmes d’optimisation ayant un espace de recherche continu, la précision de la solution dépend du nombre de bits affecté au codage (et fixé a priori).
Représentation réelle :
Le codage réel utilise directement la valeur réelledes paramètres. Selon Kalyanmoy Deb [Deb, 2001], dans le cas des problèmes d’optimisation avec des variables réelles, la résolution est plus efficace en utilisant des AGs avec un codage réel que binaire.
Sélection
La sélection est un opérateur essentiel pour améliorer la qualité d’une population. Son objectif est de retenir et multiplier les meilleurs individus qui contribueront à l’opération de croisement, et d’éliminer les plus mauvais, en accord avec la théorie de Darwin. Indépendamment du codage utilisé, la littérature propose différents types de sélection, comme celle par tournoi, proportionnelle (roulette) ou par rang. Pour plus de détails, le lecteur peut consulter Deb [Deb, 2001] et Do [Do, 2006].
Croisement
Le croisement est l’opérateur principal des algorithmes génétiques (AGs). Son rôle consiste à choisir aléatoirement deux individus parents parmi ceux sélectionnés pour les combiner et créer deux nouveaux individus enfants. Il joue un rôle important sur la convergence de l’AG, en lui permettant de concentrer une partie de la population autour des meilleurs individus. À chaque type de codage correspondent différents types de croisement. Pour les AGs avec un codage binaire, on utilise le croisement à un point (chaque bit du « génome » caractérisant le nouvel individu est celui de l’un de ses « parents » choisi aléatoirement) [Holland, 1962], à multipoints [De Jong and Spears, 1992] [Spears and De Jong, 1991] et le croisement uniforme [Syswerda, 1989]. Selon Deb [Deb, 2001], les AGs avec un codage réel peuvent utiliser la méthode de croisement linéaire (la valeur de l’individu enfant est une combinaison linéaire de celle de ses parents), naïf, mélangé ou encore binaire simulé.
Mutation
Les AGs utilisent l’opérateur de mutation pour conserver la diversité de la population et évite en particulier à l’AG de converger vers un optimum local [Gildemyn, 2008]. Pour les AGs avec un codage binaire, elle consiste à changer la valeur d’un ou plusieurs bits de l’individu de la population parent d’une valeur 1 à la valeur 0, ou réciproquement, avec une probabilité de mutation pm fixée. Concernant les AGs avec un codage réel, ilexiste différentes méthodes de mutation telles que la mutation aléatoire, la mutation non uniforme, la mutation distribuée normalement et la mutation polynomiale [Deb, 2001].
Remplacement
Le remplacement consiste à déterminer quels sont les individus de la génération courante, constituée de parents et d’enfants, qui seront les parents de la génération suivante. Plusieurs stratégies de remplacement peuvent être utilisées :
Remplacement générationnel
La nouvelle population est composée uniquement des enfants de la génération précédente. L’inconvénient majeur de cette approche est la disparition des meilleurs individus, auxquels on ne permet pas de survivre, et donc la possibilité de perdre de bonnes solutions.
Remplacement continu
Cette approche consiste à remplacer les parents les moins performants par des enfants choisis aléatoirement.
Remplacement élitiste
L’opérateur d’élitisme [Deb, 2001] permet de conserver les tout meilleurs individus de la population courante. Il est essentiel pour l’optimisation multi-objectifs [Zitzler et al, 2000]. L’élitisme peut être utilisé de manière locale, squelor deux enfants viennent d’être créés : ils sont comparés à leurs parents. Parmi les quatre individus parents et enfants, seuls les deux meilleurs sont conservés ; les parents sont en concurrence directe avec leurs enfants. Il peut également être utilisé d’une manière globale : unefois la population enfant créée, elle est combinée avec la population parent, et seuls les meilleurs individus sont retenus pour former la nouvelle population. Ainsi, une bonne solution trouvée très tôt dans l’optimisation n’est pas perdue même si une autre meilleure solution est trouvée. Donc l’élitisme accroît la probabilité de créer des meilleurs enfants et d’assurer une convergence rapide vers la solution optimale.
Stratégie d’évolution
La méthode d’optimisation à base de stratégies d’évolution (SE) fut initialement proposée par Ingo Rechenberg, en 1965, [Rechenberg, 1965] à l’Université Technique de Berlin, en Allemagne. Il l’a ensuite développée en collaboration avec Hans-Paul Schwefel. Cette approche s’appuie sur une représentation en nombres réels. Elle utilise un opérateur de mutation gaussienne. Pour plus de détails, le lecteur peut consulter [Beyer and Schwefel, 2002]. En tant qu’AE, une stratégie d’évolution est déterminée par les trois opérateurs évolutionnaires : sélection, croisement (ou recombinaison) et mutation. Elle commence par la génération d’une population parentinitiale, de taille . À la génération t, la population enfant de taille est obtenue en appliquant les opérateurs génétiques.
Sélection
La sélection augmente la performance d’une population en retenant les meilleurs individus afin de guider la recherche vers des régions prometeuses. Elle repose sur un processus déterministe qui transmet les meilleurs individus de la génération courante à la nouvelle génération. Selon la prise en compte de la population parent ou non, on distingue deux types de SE :
( -SE : On sélectionne les meilleurs individus parmi la population des parent et des
enfants de la population courante pour créer la population parent de la nouvelle génération. Ce type de sélection est élitiste. Il garantit la survie des meilleurs individus et l’amélioration de la population.
( , -SE : La sélection des individus de la nouvelle population parent se limite à la population enfant. Beyer et Schwefel [Beyer and Schwefel, 2002] considèrent que l’utilisation d’une population enfant de taille est nécessaire pour la convergence de cette méthode vers la solution optimale.
Croisement
Le croisement est facultatif pour les SEs. Il combine les informations des individus d’une population pour créer des autres individus. Contrairement aux AGs, le croisement peut utiliser plus que deux individus parents ( individus) choisis aléatoirement pour créer un seul individu enfant.
Mutation
L’opérateur de mutation est l’opérateur de base d’une stratégie d’évolution donc il est la source principale de la variation génétique. Il garantit à la fois la globalité de la recherche, en permettant d’explorer l’ensemble de l’espace de rec herche, et la convergence vers un optimum, en utilisant, le plus souvent, une mutation gaussienne auto-adaptative [Do, 2006].
Les AEs mono-objectif et les AEs multi-objectifs
On distingue deux catégories d’AEs, les mono-objectif et les multi-objectifs. Selon Justesen [Justesen, 2009], la plus grande différence entre ces deux familles, est que dans le cas mono-objectif, il est simple de retourner la solution optimale d’une population, celle ayant la valeur minimale de la fonction coût, alors que dans le cas multi-objectifs (AEMO – Algorithme Évolutionnaire Multi-Objectifs), la situation est t rès différente. Suivant la dimension de l’espace fonctionnel, F, les individus d’une population peuvent être incomparables entre eux, chacun représentant un compromis entre plusieurs objectifs. Le résultat d’un AEMO est donc en général l’ensemble des solutions non dominées (SOP).
SE-META
Dans ce paragraphe, on présente l’algorithme, SE-META, actuellement intégré dans le logiciel éléments finis, forge 2009, pour résoudreles problèmes d’optimisation mono-objectif de mise en forme. L’algorithme SE-META (en anglais Metamodel Assisted Evolution Strategies (MAES)) est un couplage entre une -SE et le métamodèle de Krigeage pour réduire le nombre d’évaluations exactes de la fonction coût. Il est proposé par Emmerich et al. [Emmerich et al, 2002] et est également décrit dans [Fourment et al, 2009], [Fourment et al, 2010] et [Massé, 2010]. Un aperçu de SE-META est représenté sur la Figure 8. SE-META commence par un choix aléatoire d’une population initiale de taille deux fois le nombre de paramètres d’optimisation (2n) pour construire le métamodèle initial. Il utilise une population parent de taille, fixée à 2 fois le nombre de paramètres d’optimisation, tandis que le nombre d’enfants est= max20, 3µ . Après le calcul exact de la population initiale, les individus sont utilisés pour donner les enfants. Ces derniers sont approximés par le métamodèle initial. Les valeurs de la fonction coût f ne sont pas directement approchées par f% , mais par la fonction mérite f mérite f%f% oùf% est l’erreur d’approximation locale du modèle de Krigeage (Eq (38)). La fonction mérite représente une estimation de la valeur la plus basse possible de f. Les meilleurs individus ayant min f%f% parmi les individus parents et enfants seront évalués exactement pour enrichir le métamodèle de krigeage,et cette procédure est répétée jusqu’à ce que le nombre maximal de calculs exacts soit atteint.
ALGORITHME GENETIQUE É LITISTE DE TRI NON- DOMINE (NSGA-II)
Dans cette partie, on présente l’Algorithme Génétique élitiste de Tri Non- Dominé (Elitist Non-Dominated Sorting Genetic Algorithm), NSGA-II, qui sera utilisé dans la suite de cette thèse. NSGA-II, a été développé par Kalyanmoy Debt ses étudiants à partir de 2000 ([Deb et al, 2000a] [Deb et al, 2002a]). Il est également décrit dans [Deb, 2001] et [Goal et al, 2007], et apparaît comme l’un des algorithmes de référence pour trouver l’ensemble optimal de Pareto avec une excellente variété de solutions. Il est certainement le plus populaire algorithme génétique multi-objectifs[Justesen, 2009]. Il est basé sur les trois caractéristiques suivantes : il utilise le principe de l’élitisme, il favorise les solutions non dominées, et il utilise une variété explicite des olutions, grâce au critère de distance d’encombrement.
Définition 4: Pour estimer la densité des solutions autour d’une solution particulière i de la population courante, on utilise la distance moyenne normalisée des deux solutions les plus proches de i , dans les sens croissant et décroissant, et pour chacune des fonctions coût. Cette quantité di , est appelée distance d’encombrement . Elle constitue une estimation du périmètre de l’hyper cube formée par les plus proches voisins de i .
|
Table des matières
Introduction Générale
Chapitre I Optimisation Multi-objectifs, Algorithmes Évolutionnaires et Métamodèl
I.1 Introduction
I.2 Optimisation multi-objectifs
I.2.1 Introduction
I.2.2 Définition
I.2.3 Buts de l’optimisation multi-objectifs
I.3 Algorithmes Évolutionnaires (AEs)
I.3.1 Principe de fonctionnement d’un algorithme évolutionnaire
I.3.2 Algorithme génétique et stratégie d’évolution
I.3.2.1 Algorithme génétique
I.3.2.1.1 Représentation
I.3.2.1.2 Sélection
I.3.2.1.3 Croisement
I.3.2.1.4 Mutation
I.3.2.1.5 Remplacement
I.3.2.2 Stratégie d’évolution
I.3.2.2.1 Sélection
I.3.2.2.2 Croisement
I.3.2.2.3 Mutation
I.3.3 Les AEs mono-objectif et les AEs multi-objectifs
I.4 SE-META
I.5 Algorithme Génétique Élitiste de Tri Non- Dominé (NSGA-II)
I.6 Métamodèles
I.6.1 Définition
I.6.2 La Méthodologie des Surfaces de Réponse (MSR)
I.6.2.1 Construction de la Méthodologie des Surfaces de Réponse
I.6.2.2 Validation de la Méthodologie des Surfaces de Réponse
I.6.2.2.1 Validation des hypothèses proposées pour la construction de la MSR
I.6.2.2.2 Validation de la précision de la MSR
I.6.3 Le Krigeage
I.6.3.1 Construction du krigeage
I.6.3.2 Validation du Krigeage
I.6.3.2.1 Validation des hypothèses
I.6.3.2.2 Validation de la précision du krigeage
I.6.4 Les Fonctions à Bases Radiales
I.7 Conclusion
Chapitre II Métamodèle à base de Différences Finies Sans Maillage
II.1 Introduction
II.2 Construction du métamodèle
II.2.1 Métamodèle linéaire : M-MDFSM-1
II.2.1.1 Formulation du métamodèle linéaire
II.2.1.2 Performance du métamodèle linéaire
II.2.2 Métamodèle quadratique : M-MDFSM-2
II.2.2.1 Formulation du modèle quadratique
II.2.2.2 Performance du métamodèle quadratique
II.2.3 Approximation mixte : M-MDFSM
II.2.3.1 Formulation du métamodèle régularisé
II.2.3.2 Performance du métamodèle régularisé
II.3 Paramétrage du métamodèle M-MDFSM
II.3.1 Critère de singularité
II.3.2 Ordre de la fonction de pondération h
II.3.3 Valeur de la fonction de lissage g
II.4 Validation du métamodèle M-MDFSM
II.5 Étude de l’erreur du métamodèle M-MDFSM
II.5.1 Erreur MC1
II.5.2 Erreur EAP
II.5.3 Erreur MC
II.5.4 Erreur H1
II.5.5 Analyse de l’erreur
II.5.5.1 Convergence asymptotique
II.5.5.2 Application de critère de convergence asymptotique
II.6 Étude de bruit
II.6.1 Introduction
II.6.2 Métamodèle avec bruit
II.6.3 Application
II.7 Conclusion
Chapitre III Couplage du M-MDFSM avec NSGA-II
III.1 Introduction
III.2 Couplage de NSGA-II avec le métamodèle M-MDFSM
III.2.1 Couplage constant : C-Constant
III.2.2 Couplage Actualisé aléatoirement: C-Actualisé
III.2.3 Couplage évolutif avec fonction mérite: C-Évolutif-FM
III.3 Problèmes tests analytiques
III.3.1 Problèmes tests d’optimisation mono-objectif
III.3.1.1 Fonction de Camel-Back
III.3.1.2 Fonction de Griewank
III.3.1.3 Fonction de Rastrigin
III.3.1.4 Fonction de Rosenbrock
III.3.2 Problèmes tests d’optimisation multi-objectifs
III.3.2.1 Construction d’un problème test
III.3.2.1.1 L’approche des fonctions mono-objectif multiple
III.3.2.1.2 L’approche ascendante
III.3.2.1.3 L’approche de surface avec contrainte
III.3.2.2 Critère de comparaison des algorithmes
III.3.2.3 Problèmes tests multi-objectifs
III.3.2.3.1 Min-Ex
III.3.2.3.2 Max-Ex
III.3.2.3.3 SCH1
III.3.2.3.4 SCH2
III.3.2.3.5 Const-Min-Ex
III.3.2.3.6 POL
III.3.2.3.7 VNT
III.3.2.3.8 TNK
III.3.2.3.9 KUR
III.4 Conclusion
Chapitre IV Optimisation des procédés de mise en forme
IV.1 Introduction
IV.2 Paramétrage de l’algorithme C-Évolutif-MC
IV.3 Paramétrage des procédés de mise en forme
IV.3.1 Procédé de remplissage d’une bielle
IV.3.2 Procédé de remplissage d’une couronne
IV.3.3 Procédé de tréfilage
IV.4 Optimisation du procédé de remplissage d’une bielle
IV.5 Optimisation du procédé de remplissage d’une couronne
IV.6 Optimisation du procédé de tréfilage
IV.6.1 Description
IV.6.2 Choix des paramètres d’optimisation
IV.6.3 Choix des fonctions coût
IV.6.4 Étude de l’optimisation du procédé de tréfilage
IV.6.4.1 Optimisation mono-objectif du procédé de tréfilage
IV.6.4.1.1 Tréfilage à deux paramètres
IV.6.4.1.2 Tréfilage à trois paramètres
IV.6.4.1.3 Tréfilage à quatre paramètres
IV.6.4.2 Optimisation multi-objectifs du procédé de tréfilage
IV.6.4.2.1 Tréfilage à deux paramètres
IV.6.4.2.2 Tréfilage à quatre paramètres
IV.7 Conclusion
Conclusion générale
Bibliographie
Télécharger le rapport complet
