TunnelOpt - Moteur de tunnélisation d’optima locaux pour l’optimisation boîte-grise scalable

Coordinateur : Bilel Derbel, Université de Lille CRIStAL

Équipe : BONUS du Groupe Thématique : OPTIMA

Dates : 2024 - 2028

Résumé :

Les algorithmes d’optimisation combinatoire développés au cours des deux dernières décennies permettent de résoudre un large panel de problèmes. Cependant, les techniques existantes souffrent de nombreuses limitations lorsque confrontées à la complexité sans précédent des problèmes actuels. Par ailleurs, ces problèmes sont souvent multi-objectfs ajoutant un degré de difficulté supplémentaire. Une problématique majeur est de passer à l’échelle, en termes du nombre de variables et d’objectifs ; mais également en terme de la quantité des ressources de calculs distribuées et massivement parallèles. Nous nous intéressons dans ce cadre à la conception et à la compréhension fondamentale d’algorithmes de recherche heuristiques stochastiques, renforcés par des méthodes d’optimisation boite-grise. De nouvelles formulations boite-grise nous permettent en effet de calculer les vecteurs propres du voisinage de recherche pour des méthodes de type recherche locales s’appliquant à une gamme de problèmes fondamentaux tels que la satisfiabilité et le routage. Ceci permet de créer des tunnels entre des optima locaux en temps linéaire. En décrivant l’organisation des optima locaux (Pareto ou pas) en sous-espaces d’hypercubes réguliers formant des réseaux de treillis (non planaires) ; nous proposons de poser les bases d’un moteur de tunnélisation pour naviguer en parallèle sur ces multiples réseaux. Un tel moteur se situe de façon fondamentale à la croisée de l’analyse du paysage de recherche, de la recherche locale hybridée par des opérateurs génétiques boite-grise, des algorithmes de recherche stochastique génériques et adaptatifs, de l’optimisation évolutionnaire multi-objectif, ainsi que de l’optimisation parallèle et distribuée. Le but ultime de ce travail est de développer un cadre flexible, mais puissant et permettant le passage à l’échelle, pour attaquer des problèmes complexes d’optimisation combinatoire boite-grise.

Abstract :

New optimization algorithms developed over the last two decades can efficiently solve a wide-range of combinatorial optimization problems. Nevertheless, existing combinatorial optimization techniques still struggle to efficiently handle the unprecedented complexity of the problems encountered in modern engineering, scientific, and numerical applications. Often these problems are multi-objective ; hence implying other degrees of difficulty. Achieving scalability is a major concern, specifically with respect to the number of variables and the number of objectives ; but also with respect to modern parallel and distributed resources, including massively parallel multi-core and multi-GPU based resources. We here focus on the design and the fundamental understanding of innovative stochastic heuristic search algorithms empowered by graybox optimization methods. In fact, new graybox formulations allow us to compute the eigenvectors of the search neighborhood for local search methods that apply to a range of fondamental combinatorial problems such as logical satisfiability (e.g. MAXkSAT) and routing (e.g. the Travelling Salesman Problem). Furthermore, it becomes possible to tunnel between local optima in linear time. By describing how local optima (Pareto or not) are organized into regular hypercube subspaces that form non-planar lattices ; we propose to set up the foundations of a tunneling engine to navigate in parallel over multiple lattices in an efficient and effective manner. Such a tunneling engine is by-product of fundamental investigations from fitness landscape analysis, local search hybridized with graybox genetic operators, general-purpose adaptive stochastic search heuristics, multi-objective evolutionary optimization, as well as, parallel and distributed optimization models. The ultimate goal of this work is to lead to a flexible, yet powerful and scalable framework for attacking complex graybox combinatorial optimization problems.