Thèse d'habilitation à diriger des recherches "Analysis of Comparison-based Stochastic Continuous Black-Box Optimization Algorithms"

Anne Auger 1
1 TAO - Machine Learning and Optimisation
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
Résumé : Ce mémoire décrit l'essentiel de mon travail scientifique depuis la fin de ma thèse. Mes travaux sont centrés sur l'optimisation numérique dite "boîte-noire" à l'exception d'un article effectué durant mon séjour post-doctoral à l'ETH Zurich qui introduit un nouvel algorithme d'optimisation stochastique pour simuler des systèmes en chimie ou bio-chimie [23]. Les algorithmes d'optimisation au coeur de mon travail sont des algorithmes adaptatifs sansd érivées et stochastiques. Ils sont particulièrement adaptés à l'optimisation de problèmes difficiles dans des contextes oèu la fonction n'est accessible qu'à travers une \boîte-noire" retournant l'information d'ordre zero, c'est-à-dire que la seule information disponible et utilisable par l'algorithme sont les couples (points de l'espace de recherche, valeur de fonction objectif associée). Ce contexte est très courant dans l'industrie oèu les problèmes d'optimisation rencontrés font appel à des codes de simulations numériques pour lesquels, souvent, simplement un executable du code est disponible. L'aspect "sans-dérivées" est aussi très commun car le calcul d'un gradient (qui présuppose la fonction sous-jacente dérivable) sur des codes de simulations numériques, par exemple en utilisant une méthode d'adjoint ou de differentiation automatique peut ^etre couteux en temps de développement. Il est par ailleurs usuel que la formulation d'un problème d'optimisation change au fur et à mesure de sa résolution, adapter le code de calcul de gradient peut alors s'avérer très lourd et peut motiver l'utilisation d'une méthode d'optimisation boîte-noire. Ce contexte d'optimisation boîte-noire s'appelle également optimisation sans dérivées dans la communauté \mathematical programming" et l'acronyme anglais associé est DFO pour \derivative free optimization". Les méthodes qualifiées de DFO sont généralement deterministes. Les méthodes DFO les plus connues à l'heure actuelle sont l'algorithme du simplexe ou de Nelder- Mead [79, 77], les algorithmes de "pattern search" [54, 90, 6] et l'algorithme NEWUOA (NEW Unconstraint Optimization Algorithm) développé par Powell [82, 81]. Ce dernier algorithme est à l'heure actuelle considéré comme l'algorithme DFO déterministe état de l'art. Mon travail porte ainsi sur des méthodes DFO au sens littéral du terme. En revanche, les méthodes auxquelles je me suis intéressées ont une large composante stochastique et ont été développées dans la communauté des algorithmes bio-inspirés qui se compose essentiellement d'ingénieurs et d'informaticiens. Les premiers algorithmes ont été introduits dans les années 70. Un parallèle entre la théorie de Darwin de l'évolution des espèces et l'optimisation a servi à l'origine de source d'inspiration pour leur développement. A l'heure actuelle, ce domaine des méthodes bio-inspirées est également appelé \Evolutionary Computation". Un terme générique pour les algorithmes est algorithme évolutionnaire (EA). Pour beaucoup de chercheurs (dont je fais partie) dans ce domaine, l'aspect bio-inspiré n'est plus présent et le développement des algorithmes est seulement motivé par des considérations mathématiques et numériques. Parmi les algorithmes évolutionnaires, les algorithmes génétiques (GA) sont probablement encore les plus célèbres en dehors de la communauté EC. En revanche, les GAs ne sont pas des algorithmes compétitifs pour l'optimisation numérique{ce fait est reconnu depuis plus d'une dizaine d'années. Les strategies d'évolutions (ES), introduites à la fin des annéees 70 [83], se sont imposées comme les algorithmes évolutionnaires pour l'optimisation numérique. A l'heure actuelle, l'algorithme ES le plus abouti est l'algorithme Covariance Matrix Adaptation Evolution Strategy (CMA-ES) [50]. L'algorithme adapte un vecteur Gaussien (paramétré par vecteur moyenne et matrice de covariance) qui encode la métrique sous-jacente. Cette métrique apprend sur des fonctions convexes quadratiques l'information d'ordre 2, c'est à dire que la matrice de covariance devient proportionnelle à l'inverse de la matrice Hessienne. Ainsi, CMA-ES peut ^etre vu comme le pendant stochastique d'une méthode de quasi-Newton. Une particularité essentielle de CMA-ES et des ES en général est d^u au fait qu'ils n'utilisent que des comparaisons pour les difrérentes mises à jour. Plus précisément, nous avons vu que les ESs sont des algorithmes d'optimisation sans dérivées, ils n'utilisent cependant qu'une information \dégradée" de ce que la boîte-noire leur fournit, à savoir simplement le résultat de la comparaison des solutions candidates, i.e. étant donné deux solutions x1 et x2, est ce que f(x1) est plus grand ou plus petit que f(x2). En conséquence ils optimisent de la m^eme façcon une fonction f : Rn ! R ou n'importe quelle fonction g o f où g : f(Rn) ! R est une fonction strictement croissante: ils sont invariants à la composition à gauche par une fonction monotone strictement croissante. L'algorithme CMA-ES est reconnu comme la méthode état de l'art pour l'optimisation stochastique numérique. Il est utilisé dans de nombreuses applications dans l'industrie ou dans le monde académique. Pour des raisons historiques, les algorithmes ESs ont été développés dans la communauté EC où la mise au point d'un algorithme est la plupart du temps découplée du soucis de prouver un théorème de convergence sur la méthode et repose essentiellement sur l'utilisation de modèles mathématiques approximatifs simplifiés et de simulations numériques sur des fonctions tests. Bien que ce découplage entre mise au point pratique et théorie puisse ^etre vu comme un inconvenient, il présente l'avantage que le développement d'une méthode n'est pas restreinte (ou bridée) par une contrainte technique liée à une preuve mathématique. Cela a permis à un algorithme comme CMA-ES de voir le jour bien avant que l'on comprenne certains de ses fondements théoriques et bien avant que l'on puisse établir une preuve de convergence. En revanche, cela implique aussi que les études théoriques de convergence par exemple s'avèrent relativement compliquées. Ma recherche se situe dans ce contexte général: je suis particulièrement intéressée par l'étude mathématique d'algorithmes adaptatifs stochastiques comme les algorithmes ESs (en particulier CMA-ES) et par l'établissement de preuves de convergence. Ces algorithmes ont une particularit é attractive: bien qu'introduits dans un contexte où les performances pratiques sont plus importantes que les preuves théoriques, ils s'avèrent avoir des fondements mathématiques profonds liés en particulier aux notions d'invariance et de géométrie de l'information. Par ailleurs, ils s'inscrivent dans le cadre plus général d'algorithmes d'approximation stochastique et ils sont fortement connectés aux méthodes Monte-Carlo par chaînes de Markov (MCMC). Ces deux derniers points fournissent des outils mathématiques puissants pour établir des preuves de convergence (linéaire). La comprehension de ces fondements et connexions est reliée en partie à mon travail comme cela sera illustré dans ce mémoire. J'ai abordé plusieurs facettes de l'optimisation numérique. Bien que l'essentiel de mes travaux porte sur l'optimisation mono-objectif, i.e. minimizer f : X Rn ! R, j'ai également travaill é en optimisation multi-objectif, i.e. où l'on s'intéresse à minimiser une fonction vectorielle f : X Rn ! Rk. Dans ce cas là, la notion d'optimum est remplacée par celle d'ensemble de points de Pareto composé des meilleurs compromis possibles. Mes contributions portent sur l'étude d'algorithmes à base d'hypervolume qui quantifient la qualité d'un ensemble de solutions en calculant le volume compris entre les solutions et un point de reference. Les algorithmes utilisant l'hypervolume sont à l'heure actuelle les algorithmes état de l'art. Nous avons pu établir des caractérisations théoriques de l'ensemble des solutions optimales au sens de l'hypervolume. En optimisation mono-objectif, j'ai travaillé sur l'optimisation bruitée où étant donné un point de l'espace de recherche, on observe une distribution de valeurs de fonction objectif, sur l'optimisation à grande échelle où l'on s'intéresse à l'optimisation de problèmes avec de l'ordre de 104 à 106 variables et sur l'optimisation sous contrainte. Mes travaux s'articulent autour de trois grands axes: théorie / nouveaux algorithmes / applications (voir Figure 3.1). Ces trois axes sont complémentaires et couplés: par exemple, la mise au point de nouveaux algorithmes repose sur l'établissement de bornes théoriques de convergence et est ensuite complémentée par des simulations numériques. Ceci est illustré au Chapitre 6. Par ailleurs le développement d'algorithmes pour l'optimisation en grande dimension repose sur la connexion entre CMA-ES et la géométrie de l'information (voir Chapitre 4). Un autre exemple de complémentarité est le suivant: les applications abordées notamment pour l'optimisation du placement de puits de pétrole ont motivé l'introduction de nouvelles variantes de CMA-ES (voir Chapitre 9). Par ailleurs, une partie non négligeable de mes travaux porte sur le test (benchmarking) d'algorithmes. La motivation principale est d'améliorer les méthodologies pour tester et comparer les algorithmes d'optimisation numériques. Ces travaux ont été accompagnés du développement d'une plateforme, Comparing COntinuous Optimizers (COCO) et ont un impact maintenant sur la mise au point de nouveaux algorithmes mais également sur le test d'hypothèses théoriques.
Type de document :
Thèse
Numerical Analysis [cs.NA]. University Paris Sud, 2016. English
Liste complète des métadonnées

https://hal.inria.fr/tel-01468781
Contributeur : Anne Auger <>
Soumis le : mercredi 15 février 2017 - 17:17:21
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : mardi 16 mai 2017 - 15:20:11

Identifiants

  • HAL Id : tel-01468781, version 1

Citation

Anne Auger. Thèse d'habilitation à diriger des recherches "Analysis of Comparison-based Stochastic Continuous Black-Box Optimization Algorithms" . Numerical Analysis [cs.NA]. University Paris Sud, 2016. English. 〈tel-01468781〉

Partager

Métriques

Consultations de la notice

434

Téléchargements de fichiers

130