• Langue : Anglais
• Discipline : Informatique
• Identifiant : Inconnu
• Type de mémoire : Habilitation à diriger des recherches
• Date de soutenance : 11/12/2017

Résumé en langue originale

Les travaux synthétisés dans ce manuscrit concernent la conception, l’analyse et la compréhension d’algorithmes génériques et de haut-niveau en optimisation mono- et multi-objectif. L’accent est mis sur le rôle crucial des algorithmes parallèles et distribués dans l’exploitation de la puissance offerte par le panorama grandissant des plateformes de calcul haute performance et large échelle, et aussi dans la conception de nouvelles approches pour la résolution de problèmes toujours plus complexes et massifs. Dans ce cadre, nos contributions s’organisent autour de trois axes. Le premier concerne la conception d’algorithmes parallèles pour l’optimisation exacte dans un but de passage à l’échelle. Plus précisément, dans un environnement large échelle hétérogène (grappes, grille), où l’hétérogénéité peut se situer au niveau des nœuds (multi-cœur, multi-GPU) ou au niveau des communications (réseaux, latence), nous étendons les techniques état-de-l’art basées sur le paradigme de ‘vol-de-travail’ afin de distribuer de façon dynamique et adaptative les unités de calcul de l’algorithme Branch-and-Bound, considéré de façon plus générale comme un cas d’étude représentatif d’algorithmes de recherche arborescente hautement irrégulière. Le deuxième axe traite de la conception de techniques ‘online’ pour la sélection adaptative d’opérateurs dans le contexte d’heuristiques de type recherche locale, algorithme évolutionnaire, métaheuristique, etc. En particulier, nous considérons l’étude de nouveaux modèles abstraits pour la conception d’algorithmes adaptatifs distribuées (modèle en îles hétérogènes), ainsi que pour la validation des techniques de sélection étudiées (modèle dit de ’fitness cloud’). Ceci est lié à une problématique plus générale sur laquelle nous travaillons de façon active : la sélection, le paramétrage, et la configuration automatique d’algorithmes d’optimisation, en nous inspirant de techniques issues de l’apprentissage automatique et de l’intelligence artificielle (bandits manchots, portfolio, hyper-heuristiques, tuning, etc). Le dernier axe de nos travaux concerne l’optimisation multi-objectif par algorithmes évolutionnaires. En particulier, nous considérons une approche basée sur le concept de décomposition, considérée comme étant l’état-de-l’art, et nous en étudions les différents composants algorithmiques, ainsi que la conception parallèle et distribuée. Cette approche consiste à transformer, à l’aide de fonctions scalaires, le problème original en un ensemble de sous-problèmes pouvant être résolus en parallèle de façon coordonnée. Nous montrons que le concept de décomposition permet non seulement de concevoir des algorithmes de type “diviser-pour-régner” pouvant être portés de façon naturelle et flexible dans un environnement distribué large échelle, mais il constitue également un ingrédient clé pour augmenter la puissance et l’applicabilité des techniques et des algorithmes évolutionnaires issus de l’optimisation mono- et multi-critères.

Résumé traduit

Our research interest is on the design, analysis and understanding of general-purpose principled single- and multi-objective optimization algorithms, where parallelism and distributed computations are expected to play a crucially important role, both to take full benefit from the ever-increasing growth of high performance and large scale compute facilities, and to accelerate the design of novel effective approaches for tackling increasingly complex and massive optimization problems. In this context, our contributions can be classified following three main axes. The first one is on the design of highly scalable parallel and distributed algorithms for exact (complete) optimization. More precisely, given a large scale heterogeneous environment (clusters, grids), where heterogeneity can occur either at the node level (muli-core, multi-GPU) or at the communication level (network links, latency), we consider to leverage state-of-the-art HPC techniques based on the work-stealing paradigm in order to adaptively and dynamically manage the irregular workload of parallel branch-and-Bound, considered as a representative example of highly unbalanced tree search algorithms. The second axis is on the design of online adaptive operator selection techniques targeting high-level heuristic search algorithms (local search, evolutionary algorithms, metaheuristics, etc.) and focusing on a number of novel abstract distributed models and benchmark optimization scenarios, namely, the so-called heterogeneous island model and the fitness cloud model. This is tightly related to a more general research line that we are actively developing: the selection, parameter setting, and automated configuration of optimization algorithms using machine-learning and artificial intelligence inspired techniques (multi-armed bandits, portfolio design, hyper-heuristics, offline tuning, etc.). The last axis is on evolutionary multi-objective optimization. In particular, we consider a state-of-the-art decomposition-based framework, and we address its core algorithmic components, as well as its distributed and parallel design. Decomposition basically uses some scalarizing functions in order to transform the original problem into a number of sub-problems that are solved cooperatively in parallel. We show that decomposition, besides leading to powerful divide-and-conquer algorithms that can flexibly fit the distributed and large scale nature of a compute platform, is a key concept allowing to leverage previous well-established evolutionary algorithms from single- and multi-objective optimization.