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, non seulement dans l’exploitation de la puissance offerte par le panorama grandissant des plateformes de calcul haute performance et large échelle, mais aussi dans la conception de nouvelles approches pour la résolution efficace de problèmes d’optimisation 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 et distribués 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 (liens 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 quant à lui de la conception de techniques, dites ‘online’, pour la sélection adaptative d’opérateurs dans le contexte d’algorithmes 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 effective 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.
soutenue le 11/12/2017
français
English