Projet ANR-12-MONU-0009 – NumBBO : Analyse, Amelioration, Evaluation d'algorithmes numériques pour l'optimisation boîte-noire
Programme : Modèles Numériques (MN) 2012
Année de financement : 2012
Coordinateur du projet : Madame Anne Auger (Institut National de Recheche en Informatique et en Automatique)
Partenaires : Laboratoire public; Laboratoire public; Thème Apprentissage et Optimisation; Inria Centre Lille - Nord Europe; TUD Technical University Dortmund
Montant : 606755.0 euros
Date de début : 2012
Durée : 48 mois
Résumé : Les problèmes d'optimisation numériques sont au coeur de nombreux problèmes industriels et inhérents à des enjeux importants de notre société. Les méthodes d'optimisation boîte-noires, qui modélisent la fonction objectif comme une boîte retournant uniquement la valeur de fonction objectif d'un point demandé en entrée, sont les méthodes adaptées pour l'optimisation de fonctions difficiles  qui peuvent être non-différentiables, non-convexes, multi-modales, bruitées ou trop complexes pour être traitées mathématiquement. Les algorithmes robustes en pratique étant trop compliqués pour être analysés théoriquement sur les modèles sur lesquels il est essentiel de comprendre et évaluer les méthodes, il est indispensable de recourir à la simulation numérique pour la mise au point de telles méthodes.
Une méthode standard pour résoudre des problèmes d'optimisation numériques dans le scénario boîte-noire est l'algorithme CMA-ES développé par le partenaire INRIA-TAO. C'est un algorithme adaptatif stochastique qui résout proprement les problèmes non-séparables, mal conditionnés et converge linéairement tout en étant robuste au bruit, aux optima locaux et ne nécessite aucun réglage de paramètre par l'utilisateur. Parallèlement à CMA-ES, beaucoup d'autres méthodes ont été introduites pour résoudre des problèmes d'optimisation numériques difficiles. Il est ainsi difficile pour un utilisateur de savoir quelle méthode choisir. Le benchmarking qui permet d'évaluer les performances de différents algorithmes dans les mêmes conditions permet de comprendre les forces et faiblesses des algorithmes et en conséquence de guider le choix de l'utilisateur parmi la variété d'algorithmes d'optimisation. La plateforme COmparing Continuous Optimizers (COCO) développée par les partenaires TAO et TU Dortmund a été mise au point pour automatiser les tâches de collection, postprocessing et visualisation des données d'optimisation. 
Les algorithmes testés avec COCO (plus de 60) sont restreints à l'optimisation sans contraintes d'un seul critère d'optimisation. Aucun algorithme testé n'est dédié à l'optimisation de fonctions chères où seulement une centaine d'évaluation sont disponibles et il faut faire appel à des fonctions surrogates (expertise du partenaire EMSE). L'optimisation sous contrainte est également un aspect important en pratique qui représente un challenge pour des méthodes adaptatives stochastiques comme CMA-ES. Aussi, de nombreux problèmes d'optimisation impliquent l'optimisation simultanée de plusieurs objectifs contradictoires où il n'existe pas une seule solution mais ou les méthodes multi-objectifs évolutionnaires (EMO) (expertise du partenaire INRIA-DOLPHIN) peuvent trouver des ensembles de points solutions exhibant le compromis entre les objectifs. Comme dans le cas mono-objectif, l'évaluation systématique de EMO est importante pour comprendre, comparer et améliorer les algorithmes.
Ce projet s'appuie sur l'expertise des différents partenaires pour analyser, améliorer et évaluer les algorithmes d'optimisation boîte-noire dans le contexte de l'optimisation mono-objectif (sous contrainte, en grande dimension), multi-objectif, chère avec un accent mis sur la méthode CMA-ES. Il est organisé autour de la plateforme COCO qui sera utilisée pour mieux comprendre les méthodes existantes mais également en tant qu'environnement pour mettre au point de nouveaux algorithmes rapidement. COCO sera étendu à l'optimisation sous-contrainte, multi-objectif en exploitant la similarité des deux sujets et la visualisation des données sera améliorée. Les données collectées via COCO seront utilisées des analyses statistiques poussées pour faire de l'analyse exploratoire de paysage ayant pour objectif la sélection du meilleur algorithme pour un problème donné (partie du projet également soumise auprès du DFG par le partenaire allemand).