Soutenance mémoire
Factorisation de la matrice de covariance
Le système (1.7) peut, par exemple, être résolu en factorisant le membre de gauche. Cette factorisation est en O(n3), et la prédiction en un point de l’espace des facteurs est ensuite en O(n2). Ce coût algorithmique peut rendre cette approche inapplicable à de grands jeux de données. La solution la plus simple pour remédier à ce problème est de ne réaliser la prédiction en un point donné qu’à l’aide des observations situées dans un voisinage de ce point (voisinage dont la taille doit directement dépendre de la portée de la covariance).
Krigeage & critères d’échantillonnage
Le principe commun aux méthodes d’optimisation reposant sur le krigeage est d’évaluer f de manière itérative en un point qui optimise un critère d’échantillonnage construit à l’aide des résultats d’évaluation déjà disponibles. L’approche la plus simple serait d’utiliser un minimiseur de la prédiction par krigeage ˆf comme nouveau point d’évaluation. Cependant, en procédant de cette manière, on accorderait une confiance trop grande à la prédiction, qui n’est, après tout, construite qu’à l’aide d’un petit nombre d’évaluations de f , et peut être très éloignée de f . L’optimisation risque alors de stagner sur un minimum local, comme c’est le cas pour l’optimisation de la fonction test présentée sur la figure 1.2. Pour obtenir un compromis satisfaisant entre recherche locale et recherche globale, il est ainsi nécessaire d’utiliser l’erreur de prédiction pour diriger la recherche vers les zones où la confiance dans la prédiction doit être améliorée. Cette idée a conduit à la création de nombreux critères d’échantillonnage utilisant simultanément la prédiction ˆf et l’évaluation de l’erreur associée. Dans cette section, les principaux critères de la littérature sont rappelés. Notre objectif est de mettre en avant leurs avantages et leurs inconvénients de manière à justifier le choix des critères retenus par la suite pour la comparaison avec le critère que nous avons développé et qui sera présenté au paragraphe 1.4. Cette section n’est pas une analyse détaillée de la littérature en optimisation globale bayésienne ; nous renvoyons pour cela au travaux de Mockus (1989a) et de Jones (2001). Remarque 1.3. L’exemple de la figure 1.2, qui sera réutilisé pour le reste du chapitre, consiste à optimiser ftest(x) = −sin(10x)−exp(x/2)+1 définie pour x ∈ [0,1], à partir de 4 évaluations initiales utilisées pour estimer les paramètres de la covariance de F. Cette fonction (inspirée de Sasena et al., 2002) présente l’avantage de posséder un minimum local proche du minimum global et à même de piéger les méthodes accordant trop peu d’importance à l’aspect global de la recherche.
Maximiser la crédibilité
Une des conclusions les plus importantes de Jones (2001) est que les critères présentés jusqu’à présent (au même titre que le critère de minimisation de l’ECM présenté par la suite) peuvent se comporter de manière peu efficace si le plan d’expériences initial est trompeur. Un exemple symptomatique en est donné à la page 373 de son article, où une fonction sinus est échantillonnée en utilisant sa propre période. Il s’en suit une prédiction constante et une erreur de prédiction supposée très faible. Pour faire face à ce manque de robustesse à un mauvais choix de covariance, l’idée avancée par Jones est alors de chercher simultanément le prochain point d’évaluation et les paramètres de la covariance. Supposons que la moyenne de F soit nulle3 et, dans un premier temps, que l’on souhaite non plus trouver le minimum global, mais atteindre une cible T. Le critère proposé par Jones consiste à chercher le point d’évaluation x et les paramètres de la covariance θ = [ν,ρ,σ] T qui maximisent la vraisemblance des résultats d’évaluations disponibles conditionnellement à {F(x) = T}.
Entropie conditionnelle des minimiseurs
Tous les critères présentés précédemment évaluent, plus ou moins explicitement, f en un point dont ils espèrent qu’il soit un minimiseur global. Cependant, dans bien des situations, il peut être plus efficace d’échantillonner la fonction dans le seul but d’écarter des parties de l’espace de recherche où un tel minimiseur n’a que peu de chances d’apparaître. Dans Villemonteix et al. (2008b), un critère partant de ce constat a été proposé. L’idée est de mesurer l’attrait d’une évaluation candidate par l’information qu’elle peut apporter sur la position du minimum global, et de réaliser l’évaluation au point qui maximise le gain d’information attendu. Cette information est mesurée par l’entropie conditionnelle des minimiseurs globaux (définie dans la section suivante) et la fonction est évaluée au point qui apporte potentiellement la plus grande réduction de cette entropie. Cette approche est analogue à celle utilisée par Geman et Jedynak (1995) — baptisée SUR pour Stepwise Uncertainty Reduction — dans le contexte tout à fait différent de la détection de routes sur des images satellites. Plus récemment (Vergassola et al., 2007), indépendamment des travaux de Geman, cette stratégie a aussi été utilisée, sous le nom d’« infotaxie » pour modéliser la stratégie de déplacement d’une bactérie en quête d’une source de nourriture, et par Bettinger et al. (2008) pour de la planification d’expériences lorsque l’on souhaite inverser le système étudié. Cette stratégie est finalement assez naturelle pour tous les problèmes de recherche à mener avec peu d’information. Cette section détaille son application à l’optimisation globale.
Remarque 1.6. Notons que, plus généralement, l’entropie est un outil classique pour mesurer l’incertitude dans les problèmes de recherche. Mentionnons par exemple les travaux de Hill (1978) sur la recherche d’un plan d’expériences optimal pour le choix d’une structure de modèles, ou encore les travaux plus généraux de Pronzato et al. (1997).
Plan d’expériences initial et choix d’une fonction de covariance
Le plan d’expériences initial (étape 1 dans l’algorithme 2 décrit ci-après) est utilisé pour une première recherche globale, mais surtout pour réaliser une première estimation des paramètres de la covariance. Jones et al. (1998) proposent d’utiliser pour cela un plan LHS2 (pour Latin Hypercube Sampling, voir par exemple McKay et al., 1979) de taille 10d. Cette règle empirique est inapplicable ici, puisque le budget total en évaluations pour les problèmes motivant ces travaux est en général bien inférieur. En revanche, là où EGO utilise une covariance non isotrope et estime ainsi 2d + 1 paramètres, il nous semble plus raisonnable de se limiter, en l’absence d’information a priori, à l’utilisation d’une covariance isotrope. En effet, même à l’aide de cette simplification, l’estimation des paramètres par maximum de vraisemblance reste trop incertaine. Pour s’en convaincre, simulons 10 000 réalisations d’un processus gaussien centré, stationnaire et de covariance de Matérn de paramètres ν = 3, ρ = 0.3 et σ 2 = 0.5. Ces réalisations sont échantillonnées sur un plan LHS, et pour chacune, calculons la dérivée seconde de la log-vraisemblance par rapport au paramètre ν, pour la vraie valeur du vecteur des paramètres. La moyenne de ces dérivées secondes est, au signe près, l’information de Fisher relative à l’estimation par maximum de vraisemblance de ν (les autres paramètres étant supposés connus). Nous pouvons alors calculer la racine carrée de l’inverse de cette quantité pour nous faire une idée grossière de l’écart-type de l’erreur d’estimation. Le tableau 2.1 présente pour différentes dimensions de l’espace de recherche et différentes tailles du plan LHS, les valeurs moyennes de cette quantité. On y constate la difficulté à estimer ne serait-ce qu’un paramètre en utilisant le nombre d’essais préconisés par Jones et al. (1998) pour des dimensions de l’espace des facteurs en accord avec nos objectifs. Nous proposons donc de n’utiliser en général le plan d’expériences initial que pour effectuer une première recherche et nous préconiserons dans la section 4.3.3 une règle empirique pour le choix du nombre d’évaluations dans ce plan. La covariance devra quant à elle être en général choisie a priori (excepté lorsque le budget d’évaluations et la dimension du problème le permettent). Ce choix, qui pourra être révisé au cours de la procédure dès que l’estimation des paramètres devient possible, s’avère souvent relativement aisé en pratique. En effet, des données ou des connaissances métiers sont fréquemment disponibles sur le système étudié et sont d’une grande utilité pour le choix des paramètres de la covariance. Par exemple, lors de la conception d’une nouvelle version d’un système, les paramètres peuvent être directement estimés à partir des données recueillies sur son prédécesseur.
|
Table des matières
Introduction
Notations
1 Optimisation globale bayésienne avec un a priori gaussien
1.1 Objectifs et plan du chapitre
1.2 Processus gaussiens et krigeage
1.2.1 Principe
1.2.2 Prédiction par krigeage
1.2.3 Exemple
1.2.4 Complexité calculatoire
1.3 Krigeage & critères d’échantillonnage
1.3.1 Minimiser une borne inférieure
1.3.2 Maximiser la probabilité d’amélioration
1.3.3 Maximiser l’espérance de l’amélioration
1.3.4 Maximiser la crédibilité
1.4 Entropie conditionnelle des minimiseurs
1.4.1 Distribution de probabilité des minimiseurs
1.4.2 Entropie conditionnelle
1.4.3 Entropie conditionnelle des minimiseurs
1.5 Discussion
2 Algorithme IAGO
2.1 Introduction
2.2 Principe de IAGO
2.2.1 Approximation de PX∗ (·|F n) et conditionnement par krigeage
2.2.2 Choix de Q
2.2.3 Schéma général
2.3 Mise en œuvre de IAGO
2.3.1 Plan d’expériences initial et choix d’une fonction de covariance
2.3.2 Choix de G et optimisation du critère d’échantillonnage
2.3.3 Critère d’arrêt
2.4 Extensions
2.4.1 Résultats d’évaluation incertains
2.4.2 Prise en compte de résultats d’évaluation du gradient
2.4.3 Prise en compte de contraintes
2.4.4 Optimisation à plusieurs pas
2.5 Conclusions
3 Optimisation robuste de fonctions coûteuses
3.1 Introduction
3.2 Formulations du problème
3.2.1 Mesures de robustesse
3.2.2 Formulations du problème d’optimisation
3.2.3 Choix d’une formulation
3.3 Prédiction des mesures de robustesse
3.3.1 Prédiction de la moyenne
3.3.2 Prédiction de la variance
3.3.3 Prédiction de la probabilité de défaillance
3.3.4 Position incertaine des évaluations
3.4 Optimisation robuste
3.4.1 Prise en compte des variables d’environnement
3.5 Conclusions
4 Comparaison des critères
4.1 Objectifs et méthode
4.2 Comparaison à l’aide de fonctions-tests
4.2.1 Exemples classiques en optimisation globale
4.2.2 Un problème d’identification
4.3 Estimation des vitesses de convergence
4.3.1 Vitesses de convergence à covariance connue
4.3.2 Robustesse par rapport à une erreur d’estimation de la covariance
4.3.3 Influence de la taille du plan d’expériences initial
4.3.4 Comparaison des critères dans des conditions d’utilisation réalistes
4.4 Influence du bruit sur les vitesses de convergence
4.4.1 Influence d’un bruit sur le résultat des évaluations
4.4.2 Performances des versions robustes
4.5 Discussion
5 Applications industrielles
5.1 Introduction
5.1.1 Contraintes propres à la conception dans l’industrie automobile
5.1.2 Automatisation des évaluations
5.2 Mise en place des algorithmes d’optimisation
5.2.1 Extension des critères d’échantillonnage aux problèmes multi-objectifs
5.2.2 Problème des données manquantes
5.2.3 Choix des paramètres de la covariance
5.3 Optimisation du conduit d’admission
5.3.1 Automatisation des simulations numériques
5.3.2 Résultats
5.4 Optimisation d’une chasse combustion
5.4.1 Construction d’un cas test
5.4.2 Résultats
5.5 Optimisation du contrôle de la direction assistée électrique
5.5.1 Présentation du problème
5.5.2 Résultats
5.6 Optimisation de la masse d’un absorbeur de choc
5.6.1 Présentation du problème
5.6.2 Résultats
5.7 Conclusions
Conclusions et perspectives
Annexes
A Prédiction par krigeage
A.1 Choix d’une fonction de covariance
A.1.1 Classes de covariances
A.1.2 Estimation des paramètres
A.2 Prédiction d’un processus convolué
B Extention du krigeage à la prédiction de plusieurs phénomènes corrélés
B.1 Cokrigeage
B.2 Prédiction à l’aide d’observations bruitées
B.3 Prédiction jointe de f et de ses dérivées
Liste des figures
Liste des tableaux
Index
Références bibliographiques
Télécharger le rapport complet
