L'optimisation boîte grise se distingue de l'optimisation boîte noire par le fait que des informations 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ées aux 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ées algorithmiques 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'un même système. Cependant, pour tirer parti efficacement de cette immense puissance de calcul, il faut adapter et/ou concevoir de nouveaux algorithmes. Cette thèse vise non seulement à l'élaboration d'approches boîtes grises massivement parallèles, mais également à obtenir une compréhension plus fine de la dynamique et des synergies des 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 des instances de très grande taille. Récemment, la Communauté a proposé des algorithmes avancés exploitant les informations disponibles sur la structure de ce type de problèmes génériques. Parmi ceux-ci, on retrouve notamment des recherches locales de type hill climber capable de trouver les mouvements améliorants en temps constant ; ainsi que des opérateurs de croisement recombinant deux optima locaux afin d'en obtenir un nouveau, tout en ayant la garantie que ce dernier soit au moins d'aussi bonne qualité que la meilleure des deux solutions croisées, et ce, en un temps linéaire par rapport à la taille du problème. Dans ce contexte, nos contributions se regroupent en deux parties. Dans la première, nous nous concentrons sur la conception d'approches parallèles. Nous décrivons une première contribution en proposant une variante de hill climber basée sur la coloration de graphes et fonctionnant en mémoire partagée. Nous proposons ensuite une nouvelle contribution décrivant une approche complètement distribuée, coopérative et massivement parallèle, fonctionnant sur l'un des plus puissants calculateurs au monde, le Fugaku. Dans une seconde partie, nous nous concentrons sur la dynamique de recherche induite par l'utilisation des croisements boîte grise. Nous décrivons deux contributions qui améliorent successivement l'état de l'art existant. La première concerne la conception et l'analyse de nouvelles stratégies d'échappement avancées, tandis que la seconde s'intéresse à l'ajout d'une phase d'initialisation permettant de diriger la recherche vers des zones de l'espace plus prometteuses. Nous concluons nos investigations par une étude comparative approfondie de la synergie entre les approches proposées et les différents opérateurs de croisement de la littérature, permettant ainsi de mieux appréhender la dynamique de recherche des approches proposées, et de discuter des pistes d'amélioration fondées sur de solides observations empiriques.
M. Bilel DERBEL Université de Lille Directeur de thèse, M. Cyril FONLUPT Université du littoral côte d'opale Examinateur, Mme Corinne LUCET-VASSEUR Université de Picardie Jules-Verne Examinatrice, M. Giuseppe LIPARI Université de Lille Examinateur, M. Adrien GOËFFON Université d'Angers Rapporteur, M. Lhassane IDOUMGHAR Université de Haute-Alsace Rapporteur.
Thèse de l'équipe BONUS soutenue le 19/12/2023
français
English