AEMO asynchrones avec coûts d’évaluation hétérogènes 

Télécharger le fichier pdf d’un mémoire de fin d’études

Optimisation évolutionnaire multi-objectif

Comme décrit précédemment dans ce chapitre, les algorithmes évolutionnaires manipulent une population de solutions au lieu d’une seule solution. Cette propriété leur permet d’être bien adaptés à la résolution des problèmes d’optimisation multi-objectif où l’optimum est représenté par un ensemble de points (ensemble de Pareto) et non pas par une solution unique. Dans la littérature, plusieurs approches ont été proposées afin d’adapter les algorithmes évolutionnaires au cas de l’optimisation multi-objectif. L’objectif principal de ces différentes approches est le même : obtenir une bonne approximation du front optimal tout en assurant une bonne diversité des solutions le long de ce dernier. Ces méthodes diffèrent toutefois entre elles dans la façon d’aborder cette problématique en utilisant des procédure de sélection diffé-rentes. Avant de présenter principaux AEMO, nous nous focalisons dans un premier temps sur ce qui fait la différence entre ces algorithmes à savoir les différentes mé-thodes de comparaison pouvant être utilisées pour sélectionner les solutions. Comme ces méthodes de sélection font parfois recourt aux indicateurs de performance, nous commençons d’abord par présenter ces derniers.

Indicateurs de Performance

L’évaluation de la performance des AEMO peut avoir plusieurs aspects, comme par exemple la qualité des résultats obtenus, ou le temps de calcul nécessaire. Nous nous focalisons seulement sur le premier aspect étant donné que le temps d’exécu-tion des algorithmes devient négligeable dès lors qu’il s’agit d’une application réelle ou l’évaluation des objectifs peut durer de quelques minutes à quelques jours. Plusieurs indicateurs de performance ont été proposés dans la littérature afin de comparer la qualité des AEMO. Parmi ces indicateurs, nous retrouvons ceux qui s’intéressent seulement à la diversité des solutions (spacing [Schott 1995], maxi-mum spread [Zitzler 1999a]) et ceux qui s’intéressent plutôt à la convergence ou la proximité au front de Pareto (Error Ratio [Veldhuizen 1999], Set Coverage Metric [Zitzler 1999a]). Par la suite la communauté des AEMO a vu apparaitre de nou-veaux indicateurs qui évaluent à la fois la convergence et la diversité des AEMO (L’indacteur de l’hypervoulume [Zitzler 1999b], l’indicateur Epsilon [Zitzler 2003], l’indicateur R [Hansen 1998]).
Les indicateurs de performance peuvent être classés aussi selon qu’ils sont unaires ou binaires : Un indicateur de qualité I unaire affecte à chaque ensemble de solutions une valeur réelle I : Ω → R . Un indicateur binaire est un indicateur qui affecte une valeur réelle à une paire d’ensemble de solutions. Cette valeur réelle représente la mesure de qualité d’un ensemble de solutions par rapport à un autre I : Ω × Ω → R. Nous présentons dans ce qui suit les indicateurs les plus utilisés de l’état de l’art à savoir l’indicateur de l’hypervolume et l’indicateur Epsilon.

Indicateur Hypervolume

L’indicateur de l’hypervolume (IH ) [Zitzler 1999b] mesure le volume de la portion faiblement dominée par un ensemble de point A, dans l’espace des objectifs. Le calcul de ce volume nécessite la désignation d’un point de référence, qui soit de préférence dominé par la totalité des points de l’ensemble A (figure 2.2(a)). L’indicateur de l’hypervolume est souvent calculé par rapport à un ensemble de référence R (figure 2.2(b)), cet indicateur est noté IH− et est défini comme suit :
IH−(A) = IH (R) − IH (A) (2.3)
où plus la valeur de IH− est petite, plus la qualité est meilleure. L’indicateur de l’hy-pervolume permet de prendre en compte à la fois la convergence de l’algorithme et la diversité des solutions trouvées. Toutefois, le coût de calcul est élevé : la complexité est exponentiellement proportionnelle au nombre d’objectifs. [Knowles 2006]

Indicateur Epsilon

L’indicateur Epsilon a été introduit dans [Zitzler 2003] et comprend deux va-riantes : multiplicative et additive. Pour les deux versions il existe une forme unaire et une autre binaire. Cet indicateur est basé sur la notion de l’ε-dominance définie dans la section (2.2.2).

Procédures de comparaison

Plusieurs procédures de sélection ont été proposées dans la littérature des AEMO. Cependant nous pouvons distinguer deux catégories principales : la pre-mière utilise une comparaison basée sur la dominance + un deuxième critère de diversité tandis que la deuxième catégorie utilise uniquement une mesure basée sur les indicateurs de performance qui permettent d’évaluer la convergence et la diver-sité à la fois (indicateur de l’hypervolume, indicateur epsilon).
Pour les algorithmes qui utilisent la comparaison basée sur la dominance, comme cette dernière est une relation d’ordre partiel, nous nous retrouvons avec une catégo-rie d’individus qui sont non-comparables entre eux. Pour cela, un deuxième critère de comparaison est utilisé afin de départager les individus qui sont non-dominés entre eux. Ce critère concerne la densité des solutions et a pour but de favoriser la diversité du front de Pareto. Nous présentons dans ce qui suit les techniques utilisées pour comparer les individus au sens de la dominance ainsi que celles relatives au deuxième critère qui est la densité des solutions, et nous finissons cette section par la procédure de comparaison basée uniquement sur les indicateurs de performance.

Comparaison basée sur la dominance

Rang de Pareto [Deb 2002] Avec ce critère de comparaison, les individus non-dominés d’un ensemble A se voient attribuer une valeur de rang égale à 1. Par la suite, en considérant les individus non dominés de l’ensemble A sauf les individus du 1er rang, on obtient les individus du 2ème rang. La procédure est répétée jusqu’à ce que tous les individus soient attribués à un rang. Le Strength [Zitzler 2001] Avec ce critère le classement des individus en uti-lisant le principe de dominance se fait via la valeur de Strength Si qui représente pour chaque individu i appartenant à un ensemble A, le nombre de solutions qu’il domine :
S(i) = |{j : j ∈ A et i ≺ j}| (2.6)

Critères de densité

Critère de surpeuplement Ce critère proposé dans [Deb 2002] permet d’ordon-ner des individus non-départageables par la relation de dominance (non-dominés entre eux) selon une mesure de densité qui permet d’évaluer leur degré de contribu-tion à la diversité.
La distance de surpeuplement di d’une solution i est une mesure de l’espace de recherche autour de i qui n’est pas occupé par aucune autre solution dans la popu-lation.
Critère du kime voisin Ce critère proposé dans [Zitzler 2001] est une adaptation de la technique du « kime plus proche voisin » [Silverman 1986]. La densité d’un point est une fonction décroissante de la distance le séparant du kime plus proche point. le critère de densité est défini dans [Zitzler 2001] comme étant l’inverse de la distance au kime point voisin. Plus précisément, pour chaque individu i, les distances (dans l’espace des objectifs) le séparant de tous les autres individus j de la population sont calculées et ordonnées dans une liste. Le kme élément correspond à la distance recherchée, dénotée σik. La valeur de k est définie habituellement comme étant la racine carrée de la taille de l’ensemble des individus.
Critère de contribution à l’hypervolume Ce critère proposé dans [Igel 2007a] repose sur l’utilisation de l’indicateur de l’hypervolume décrit ci-dessus. Ce critère mesure la qualité d’un point en calculant sa contribution à l’hypervolume de l’en-semble de la population A. La mesure de la contribution d’un individu a à l’hyper-volume d’une population A est donnée par :
ΔIH− (a, A) = IH−(A) − IH−(A { a}) (2.7)

Indicateurs de performance

Une autre possibilité pour comparer les individus entre eux est d’utiliser les in-dicateurs de performance comme mesure de comparaison des individus. L’utilisation d’un indicateur évaluant la convergence et la diversité des individus en même temps (Indicateur de l’hypervolume, indicateur epsilon) permet de considérer une mesure unique pour établir un ordre total dans l’ensemble des individus de la population.

Etat de l’art des algorithmes évolutionnaires multi-objectifs

Nous présentons dans cette section l’état de l’art des algorithmes évolutionnaire multi-objectif en se focalisant seulement sur les principaux derniers travaux dans ce domaine à savoir : NSGA-II, SPEA2, IBEA, ε-MOEA et MO-CMA-ES.

NSGA-II

NSGA-II (Non-dominated Sorting Genetic Algorithm) [Deb 2002] a longtemps été l’algorithme phare dans le domaine de l’optimisation évolutionnaire multi-objectif. Il tient son appellation de l’algorithme NSGA qui a été proposé auparavant par les mêmes auteurs [Srinvas 1994]. l’algorithme NSGA reprend l’idée proposée par Goldberg sur l’utilisation du concept de classement par dominance dans les algo-rithmes génétiques [Goldberg 1989]. Dans la plus part des aspects NSGA-II est très différent de NSGA, cependant le nom a été gardé pour indiquer les origines de cette approche. Nous nous contenterons dans ce qui suit de présenter les différentes étapes de l’algorithme NSGA-II.
Dans NSGA-II la population des enfants Qt est d’abord créée en utilisant la po-pulation des parents Pt. Les deux populations sont ensuite réunies pour former la population mixte Rt de taille 2N . Cette population est triée selon le critère du rang de Pareto décrit ci-dessus pour former les fronts successifs : le premier front F1 correspond à l’ensemble des solutions non-dominées de Rt. En considérant le reste des individus dans Rt après avoir enlever ceux de F1, et après avoir réaliser un nou-veau tri de dominance, nous obtenons le deuxième front F2 constitué des individus non-dominés de l’ensemble (RtF 1). Cette procédure est répétée jusqu’à ce que tous les individus de Rt soient attribués à un front. Par la suite, la nouvelle population Pt+1 est créée et est remplie au fur et à mesure avec les différents fronts successifs. Comme la taille de la population Rt est 2N , les fronts successifs ne peuvent pas intégrer en totalité la nouvelle population qui doit être de taille N .

SPEA2

SPEA2 (Strenght Pareto Evolutionary Algorithm) [Zitzler 2001] représente une version corrigée de l’algorithme SPEA [Zitzler 1998] proposé auparavant par les mêmes auteurs. SPEA2 repose sur l’utilisation d’une archive représentée par une population externe At de taille Narchive. Cette archive de taille fixe est destinée à contenir un nombre limité de solutions non-dominées trouvées par l’algorithme au cours de l’optimisation. A chaque itération, les nouveaux individus non-dominés de la population Pt sont comparés aux membres de l’archive At en utilisant le critère de dominance. Si le nombre d’individus non-dominés n’est pas suffisant, l’archive est complétée par les meilleurs individus dominés.

Table des matières

1 Introduction
I Algorithmes évolutionnaires multi-objectif parallèles 
2 Contexte et démarche
2.1 Introduction
2.2 Notions préliminaires
2.2.1 Problème d’optimisation multi-Objectif
2.2.2 Principe de dominance
2.2.3 Optimalité de Pareto
2.3 Méthodes classiques
2.3.1 Méthode d’agrégation
2.3.2 Méthode de ε-contraintes
2.3.3 Mesure de Chebyshev
2.4 Algorithmes évolutionnaires
2.4.1 Vocabulaire et Terminologie
2.4.2 Principe de fonctionnement
2.4.3 Le dilemme exploration/exploitation
2.4.4 Les procédures de sélection
2.5 Les moteurs d’évolution
2.5.1 Algorithmes générationnels
2.5.2 Algorithmes stationnaires (« steady-state »)
2.6 Optimisation évolutionnaire multi-objectif
2.6.1 Indicateurs de Performance
2.6.2 Procédures de comparaison
2.7 Etat de l’art des algorithmes évolutionnaires multi-objectifs
2.7.1 NSGA-II
2.7.2 SPEA2
2.7.3 IBEA
2.7.4 ε-MOEA
2.7.5 MO-CMA-ES
2.8 Fonctions tests
2.9 Comparaisons des algorithmes de l’état de l’art
2.9.1 Réglages
2.9.2 Résultats
2.9.3 Discussions
2.10 Algorithmes évolutionnaires et modèles parallèles
2.10.1 Modèle Maître-esclave
2.10.2 Modèle en îlots
iv Table des matières
2.10.3 Modèle totalement distribué
2.11 Hétérogénéité des coûts d’évaluation et asynchronicité des AEMO
2.12 Démarche
2.13 Conclusion
3 AEMO asynchrones avec coûts d’évaluation hétérogènes
3.1 Introduction
3.2 Parallélisation des AEMO avec le modèle Maître-esclave
3.2.1 NSGA-II Stationnaire
3.2.2 MO-CMA-ES Stationnaire
3.2.3 AEMO Asynchrones Stationnaires
3.3 Implémentation des modèles de test artificiels
3.3.1 L’hétérogénéité aléatoire « Rand-VC »
3.3.2 L’hétérogénéité proportionnelle aux valeurs des objectifs « Eps-VC »
3.3.3 L’hétérogénéité liée à une région « Region-VC »
3.4 Conditions expérimentales générales
3.4.1 Réglages algorithmiques
3.4.2 Représentation graphique des résultats
3.5 Accélération de convergence asynchrone
3.6 Contexte hétérogène
3.6.1 Le modèle Eps-VC
3.6.2 Le modèle Région-VC
3.7 Conclusion
4 AEMO asynchrones et méta-modèles
4.1 Introduction
4.2 Modèles d’approximation : État de l’art
4.2.1 Approximation quadratique des moindres carrés
4.2.2 Modèles de krigeage
4.2.3 SVM (Support Vector Machines)
4.3 Méta-modèles & AEMO générationnels
4.4 Méta-modèles & asynchronicité
4.5 Réglages expérimentaux
4.5.1 Réglages du méta-modèle
4.5.2 Réglages de l’AEMO
4.6 Résultats
4.6.1 Réglage de Niter et Neval
4.6.2 Comparaison des algorithmes
4.7 Conclusion
II Optimisation de la combustion Diesel 
5 Généralités
5.1 Introduction
5.2 Cycle d’un moteur Diesel
5.3 Mécanisme d’auto-inflammation
5.4 Formation des polluants
5.5 Modélisation de la combustion
6 Modélisation phénoménologique (0D)
6.1 Introduction
6.2 Présentation de l’outil PDF0D
6.2.1 Equilibre thermodynamique
6.2.2 Mélange des particules
6.2.3 Pertes Thermiques aux Parois
6.2.4 Injection du carburant
6.2.5 Combustion
6.3 Définition du problème d’optimisation
6.3.1 Paramètres de l’optimisation
6.3.2 Objectifs de l’optimisation
6.3.3 Contrainte de l’optimisation
6.4 Réglages
6.5 Résultats
6.5.1 Variabilité du temps de calcul
6.5.2 Coût global de l’optimisation
6.5.3 Comparaison des fronts de Pareto
6.5.4 Analyse physique
6.6 Conclusion
7 Modélisation multidimensionnelle (3D)
7.1 Introduction
7.2 Travaux connexes
7.3 Spécificités de la modélisation Diesel
7.3.1 Symétrie de la chambre de combustion
7.3.2 Injection à soupapes fermées
7.4 Présentation de la chaine de modélisation 3D
7.5 Définition du problème d’optimisation
7.5.1 Les paramètres de l’optimisation
7.5.2 Les contraintes de l’optimisation
7.6 La chaine d’optimisation
7.7 Implémentation de la chaine d’optimisation
7.7.1 La plateforme CINES
7.7.2 Le serveur PSA
7.7.3 Discussion
7.8 Réglages
7.9 Résultats
7.9.1 Front de Pareto
7.9.2 Analyse physique
7.9.3 Méta-modèle : résultats préliminaires
7.10 conclusion
8 Conclusion
Bibliographie 
A Courbes des expérimentations réalisées avec le modèle artificiel « Eps-VC » 1
B Courbes des expérimentations sur l’accélération avec différentes tailles de grille de calcul
B.1 accélération en fonctions de la taille de la grille
B.2 Courbes des expérimentations réalisées avec le modèle séquentiel

Télécharger le rapport complet