Optimization boîte grise massivement parallèle et large échelle

Abstract

L’optimisation boîte grise se distingue de l’optimisation boîte noire par le fait que desinformations soient disponibles sur la structure du problème que l’on souhaite résoudre.Ces informations permettent de concevoir des approches très efficaces, car adaptéesaux particularités des problèmes considérés ; on peut ainsi, en un temps raisonnable,traiter des problèmes de plus en plus grands et ce très efficacement. À ces avancéesalgorithmiques s’ajoutent l’accroissement de la puissance des supercalculateurs, celle-ciétant principalement le fruit de la multiplication des unités de calcul au sein d’unmême système. Cependant, pour tirer parti efficacement de cette immense puissancede calcul, il faut adapter et/ou concevoir de nouveaux algorithmes. Cette thèse visenon seulement à l’élaboration d’approches boîtes grises massivement parallèles, maiségalement à obtenir une compréhension plus fine de la dynamique et des synergiesdes opérateurs boîtes grises les plus puissants, et ce, dans un environnement parallèle,mais aussi séquentiel.Plus précisément, nous nous concentrons sur les problèmes d’optimisation pseudo-booléens k-bornés modélisables par des paysages Mk et plus particulièrement sur desinstances de très grande taille. La communauté a proposé des algorithmes avancésexploitant les informations disponibles sur la structure de ce type de problèmes génériques. Parmi ceux-ci, on retrouve des recherches locales de type hill climber capablesde trouver les mouvements améliorants en temps constant ; ainsi que des opérateursde croisement recombinant deux optima locaux afin d’en obtenir un nouveau, tout enayant la garantie que ce dernier soit au moins d’aussi bonne qualité que la meilleuredes deux solutions croisées, et ce, en un temps linéaire.Dans ce contexte, nos contributions se regroupent en deux parties. Dans une premièrepartie, nous nous concentrons sur la conception d’approches parallèles. Nous pro-posons d’abord une variante d’un hill climber basée sur la coloration de graphes etfonctionnant en mémoire partagée. Nous proposons ensuite une nouvelle approchecomplètement distribuée, coopérative et massivement parallèle, fonctionnant sur l’undes plus puissants calculateurs au monde, le Fugaku. Dans une seconde partie, nousnous concentrons sur la dynamique de recherche induite par l’utilisation des croisements boîte grise. Nous décrivons deux contributions qui améliorent successivementl’état de l’art existant. La première concerne la conception et l’analyse de nouvellesstratégies d’échappement avancées, tandis que la seconde s’intéresse à l’ajout d’unephase d’initialisation permettant de diriger la recherche vers des zones prometteusesde l’espace de recherche. Nous concluons nos investigations par une étude comparativeapprofondie de la synergie entre les approches proposées et les différents opérateursde croisement de la littérature, permettant ainsi de mieux appréhender la dynamiquede recherche des approches proposées, et de discuter des pistes d’amélioration fondéessur de solides observations empiriques.