• Langue : Français
• Discipline : Informatique et applications
• Identifiant : 2023ULILB037
• Type de thèse : Doctorat
• Date de soutenance : 19/12/2023

Résumé en langue originale

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.

Résumé traduit

In contrast to blackbox optimization, we assume in graybox optimization that some information is available about the structure of the problem to be solved. This information allows one to design highly efficient solving approaches. As a result, increasingly large-size problems can be solved very efficiently, in a reasonable amount of time. In addition to such algorithmic advances, the power of supercomputers continues to increase very substantually, mainly as a result of the increasing number of computing units that can be used. However, in order to make the most effective use of the implied computing power, new algorithms need to be adapted and/or designed. The aim of this thesis is both to develop massively parallel gray-box approaches, and to gain a more fundamental understanding of the dynamics of the latest graybox operators, in both parallel and sequential environments.More precisely, we focus on solving large-size k-bounded pseudo-Boolean optimization problems modeled by MK-landscapes. In the recent years, the community has made a lot of advances in exploiting the information available on the structure of these generic optimization problems. This includes the design of hill climbers, and local search based heuristics, that are able to finding improving moves in constant time, as well as evolutionary crossover operators that can successfully recombine two local optima in a time that is linear in the size of the problem.In this context, our contributions can be grouped into two parts. In a first part, we focus on the design of scalable parallel solving approaches. A first contribution consists in proposing a hill climber shared memory parallel variant based on graph coloring. A second contribution consists in designing and analyzing a fully distributed, cooperative and massively parallel approach running on one of the world's most powerful computers, the Fugaku. In a second part, we focus on the search dynamics induced by the use of graybox crossovers. We describe two contributions improving the existing state-of-the-art solving approaches. The first contributions relates to the design and analysis of novel escape strategies, and the second one focuses on the design of a warming initialisation phase to guide the search towards more promising areas of the search space. We conclude our investigations with a comprehensive in-depth comparative study on the synergy between the proposed approaches and the various crossover operators from in the literature, thereby enabling a better fundamental understanding of the search dynamics of the proposed approaches, and highlighting new empirical observations that should lead to new improved algorithms.