Quantification de l'incertitude avec un ensemble de substituts pour l'optimisation de boîtes noires

En optimisation sans dérivées et de boîtes noires, les fonctions définissant le problème n'ont pas de forme analytique connue. Les dérivées ne sont notamment pas accessibles, ce qui rend caduc un grand nombre d'algorithmes existants. Une méthode éprouvée en optimisation de boîtes noires consiste à construire des modèles de l'objectif et, le cas échéant, des contraintes, grâce aux valeurs déjà connues. Ces modèles, peu coûteux en temps de calcul comparés aux vraies fonctions, permettent de guider l'optimisation puisqu'ils procurent une information sur le comportement du vrai problème. Une technique connue consiste à utiliser pour une même fonction non pas un seul modèle mais un ensemble de modèles afin de tirer avantage de chacun d'entre eux. Ce mémoire propose une extension aux ensembles de modèles leur permettant de fournir en tout point de l'espace non seulement une prédiction mais aussi une mesure d'incertitude. Les ensembles de modèles ainsi modifiés se comportent comme des modèles stochastiques, ce qui permet d'utiliser des outils de l'optimisation bayésienne. La mesure d'incertitude proposée repose sur les différences de variations entre les modèles, et se décline en deux versions : une pour l'objectif et une pour les contraintes. Pour tester cette approche, de tels ensembles de modèles ont été intégrés dans l'algorithme de recherche directe sur treillis adaptatifs (MADS). À chaque itération, un sous-problème issu de l'optimisation bayésienne et faisant intervenir les ensembles de modèles est résolu afin de trouver des points candidats. Le but est de vérifier que l'approche proposée améliore le choix de points par rapport aux méthodes existantes et en particulier par rapport aux modèles stochastiques. La version de l'algorithme MADS ainsi conçue a été testée sur des problèmes variés : sept problèmes analytiques, deux problèmes d'optimisation multi-disciplinaire et deux problèmes de simulation. L'approche proposée a été comparée à deux autres versions de MADS : une sans étape de recherche globale et une avec des modèles quadratiques ; ainsi qu'à deux autres solveurs d'optimisation de boîtes noires. Les résultats montrent que notre approche est préférable aux autres versions de MADS et aux autres solveurs sur la plupart des problèmes difficiles. De plus, les modèles agrégés conçus sont plus rapides et plus précis que les modèles stochastiques sur les problèmes où ces derniers ont été testés. La méthode proposée est en revanche surpassée sur les problèmes analytiques et sur un problème de simulation dont la plupart des contraintes sont linéaires. Par ailleurs, un des deux solveurs concurrents n'est compétitif avec aucune version de MADS. L'autre solveur produit de bons résultats mais nécessite un temps de calcul bien supérieur, et sur la plupart des problèmes il est préférable d'exécuter plusieurs fois l'algorithme proposé. Étant donnés ces résultats, on peut conclure que les ensembles de modèles construits améliorent les résultats de l'algorithme MADS de référence et sont par ailleurs une alternative sérieuse aux modèles stochastiques.

Abstract

In derivative-free and blackbox optimization, the analytical expression of the problem is unknown. In particular, no derivatives can be used and as a consequence many optimization algorithms are inoperative. In this context, an efficient method is to build models of the objective and constraints of the problem with the values that are already known. These models are cheap to compute compared to the actual functions and enable to guide the optimization since they bring information on the behaviour of the true problem. This master thesis proposes an extension to ensembles of models, a technique that consists in using several models of the same function simultaneously. The extended ensembles of models provide at any point not only a prediction, but also an uncertainty on that prediction. They therefore behave like stochastic models, thus enabling to use efficient tools from Bayesian op-timization. The proposed measure of uncertainty is based on the di˙erences in the variations of the models and is given in two versions: one for the objective and one for the constraints. In order to test the approach, the extended aggregate models have been integrated into the MADS algorithm. At each iteration, a subproblem inspired by Bayesian optimization is solved to find candidate points on which the true problem is evaluated. The purpose is to test whether the proposed approach improves the selection of candidate points compared to existing versions of MADS and especially to stochastic models. The resulting MADS algorithm instance has been tested on various problems : seven ana-lytical problems, two multi-disciplinary optimization problems and two simulation problems. The proposed approach has been compared to two other versions of MADS : one without any search step and one with a search involving the minimization of quadratic models; as well as two other blackbox optimization solvers. The results show that the proposed approach out-performs the other versions of MADS and the other solvers on most of the diÿcult problems. Moreover, the extended aggregate models are faster and more accurate than the stochastic models on all the problems where the latter have been tested. However, the proposed method is outperformed on the analytical problems and on one simulation problem where most of the constraints are linear. Furthermore, one of the two competing solvers is not competitive with any version of MADS, and the other solver takes a large amount of time which is better invested running the proposed method multiple times. Based on these results, the extended aggregate models improve the performance of the base MADS algorithm and constitute an alternative to stochastic models.