Thesis of Guillaume Briffoteaux

Algorithmes parallèles et basés sur méta-modèles pour la résolution de problèmes d'optimisation coûteux

De la combinaison de l'apprentissage automatique, du calcul parallèle et de l'optimisation résultent les algorithmes d'optimisation parallèles et basés sur des méta-modèles (P-SBOAs). Ces algorithmes sont utiles à la résolution de problèmes d'optimisation boîte-noire, coûteux en calculs et basés sur la simulation pour lesquels la fonction à optimiser repose sur un simulateur coûteux en calculs. En plus de la topographie du paysage de recherche, la recherche est limitée par un budget de calculs dû au coût de la fonction objectif. Dans cette thèse, l'attention est focalisée sur la conception des P-SBOAs pour traiter divers caractéristiques du paysage de recherche et budgets de calculs. La distinction entre problèmes très et modérément coûteux est introduite au travers de la définition du budget comme étant un temps limité sur une quantité restreinte de ressources de calculs. Les trois dimensions de l'espace de conception des P-SBOAs considéré dans ces travaux sont le méta-modèle, la définition du degré de promesse des solutions candidates et le couplage entre l'optimisateur et le méta-modèle. D'un côté, l'apprentissage automatique est utilisé pour construire un méta-modèle qui imite le simulateur afin d'évaluer et/ou localiser rapidement de nouvelles solutions prometteuses. D'un autre côté, le calcul parallèle est mis à profit pour réaliser simultanément plusieurs simulations afin de réduire le temps d'exécution. Le challenge général consiste à allouer le budget de façon adéquate aux tâches de simulation, entraînement du méta-modèle et acquisition de nouvelles solutions. Le méta-modèle doit être entraînable rapidement surtout dans le cas des problèmes modérément coûteux où la taille de l'ensemble d'entraînement peut devenir significative. Il doit aussi offrir une capacité prédictive adéquate pour se rapprocher des paysages rugueux et fournir de l'information sur l'incertitude prédictive afin de guider la recherche. Les réseaux de neurones bayésiens (Bayesian Neural Network) approchés par Monte-Carlo Dropout (BNN_MCD) sont étudiés car ils rassemblent toutes les caractéristiques désirées. Premièrement, ils sont utilisés pour construire des algorithmes évolutionnaires parallèles assistés parSurrogate modelsen évaluant et filtrant les solutions candidates. Deuxièmement, ils sont employés avec des processus gaussiens (GPs) pour concevoir de nouveaux algorithmes parallèles guidés par méta-modèles (P-SDAs) où des sous-méta-modèles sont optimisés en parallèle pour produire de multiple nouvelles solutions prometteuses. Le degré de promesse des solutions est défini en changeant dynamiquement le compromis entre exploration et exploitation durant la recherche extit{via} des ensembles de contrôles d'évolution. Des expériences systématiques sont menées sur plusieurs problèmes artificiels ainsi que sur une application réelle de contrôle de l'épidémie de Covid-19 afin de comparer une vaste gamme d'algorithmes. Les résultats démontrent que les P-SAEAs sont beaucoup plus adaptés à la résolution de problèmes modérément coûteux alors que les P-SDAs sont à mettre en avant sur des problèmes très coûteux. Avec les P-SAEAs, la définition du degré de promesse promu par les résultats numériques consiste à favoriser d'abord l'exploration et ensuite l'exploitation au cours de la recherche alors que plus d'intensification est préférée avec les P-SDAs. Le méta-modèle BNN_MCD démontre de bonnes performances sur des paysages multi-modales avec une structure globale peu informante et les GPs sont mis en avant dans les autres cas. Par conséquent, un nouvel algorithme hybride retenant le meilleur des P-SAEAs et P-SDAs est proposé pour offrir plus de robustesse quant aux budgets de calculs. La nouvelle méthode démontre une mise à l'échelle frappante à l'augmentation des unités de calculs et produit les meilleures solutions sur le problème lié à la Covid-19 exposant un paysage multi-modal et une structure global peu informante.

Jury

M. Nouredine MELAB Université de Lille Directeur de thèse M. Amir NAKIB Université Paris Est Créteil Rapporteur M. Frédéric SAUBION Université d'Angers Rapporteur M. Daniel TUYTTENS Université de Mons Co-directeur de thèse M. Mohand MEZMAZ Université de Mons Examinateur M. Grégory COUSSEMENT Université de Mons Examinateur Mme Patricia STOLF Université de Toulouse Examinatrice Mme Imen CHAKROUN IMEC Leuven Examinatrice M. David DUVIVIER Université Polytechnique des Hauts de France Invité

Thesis of the team BONUS defended on 21/10/2022