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

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-objectifs 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.