Massively parallel and large scale graybox optimization
Optimization boîte grise massivement parallèle et large échelle
Résumé
In contrast to blackbox optimization, graybox optimization assumes that some information is available about the structure of the problem to be solved. This information
allows us 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
substantially, 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 as MK-landscapes. In 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 find improving moves in constant time, as well as
evolutionary crossover operators that can successfully recombine two local optima in
linear time in the size of the problem.
In this context, our contributions can be grouped into two parts. In the first part,
we focus on the design of scalable parallel solving approaches. We propose a shared
memory parallel hill climber variant based on graph coloring. We then investigate the
design and analysis of a fully distributed, cooperative and massively parallel approach
running on one of the world’s most powerful computers, the Fugaku. In the 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 contribution 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 findings that should lead to new
improved algorithms
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. 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 des recherches locales de type hill climber capables
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.
Dans ce contexte, nos contributions se regroupent en deux parties. Dans une première
partie, 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 et
fonctionnant en mémoire partagée. Nous proposons ensuite une nouvelle 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 prometteuses
de l’espace de recherche. 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.