Algorithmes Heuristiques et Techniques d'Apprentissage - Applications au Probleme de Coloration de Graphe

The last couple of decades have seen a surge of interest and sophistication in using heuristics to solve combinatorial optimization problems. However, the theoretical and practical research of these algorithms show there are many important challenges yet to be overcome { e.g. it seems that it is quite dicult to make a heuristic integrate a global vision over its own evolution or over its exploration path. Taking the well-known graph coloring problem as an experimental framework, we develop several new heuristics that integrate certain learning mechanisms so as to render the search process more \self-aware". For instance, we introduce an algorithm that is able to record its trajectory and to interpret its own evolution. A search space analysis showed that the best discovered potential solutions tend to occur relatively close to each other, clustered in spheres of xed radius. Using such learned information, we developed : (i) diversication algorithms that "pay attention" not to visit the same sphere repeatedly, (ii) intensication algorithms assuring an in-depth exploration of a closed perimeter using a breath-rst-search traversal of its spheres, or (iii) evolutionary algorithms that are able to keep the individuals suciently distant at all times, while not sacricing population quality. In fact, we present numerous other techniques (e.g. new evaluation functions) that are able to render the heuristic search more \well-informed". Keywords : search while learning, graph coloring, local search trajectory recording, intensication heuristics, population diversity, search space distanceAu cours des trois dernieres decennies, les algorithmes heuristiques ont permis de realiser des progres remarquables dans la resolution des problemes diciles d'optimisation combinatoire. Cependant, la conception de ces algorithmes releve encore plusieurs challenges importants { en particulier, il semble qu'il est toujours dicile d'integrer dans une heuristique une vue d'ensemble sur l'evolution de la recherche ou sur sa trajectoire. Prenant comme cadre experimental le probleme bien connu de la coloration de graphe, nous presentons de nouvelles strategies qui font appel a certains mecanismes d'apprentissage pour rendre le processus de recherche plus \auto-conscient". Nous introduisons un algorithme qui est capable d'enregistrer sa trajectoire et d'interpreter sa propre evolution. Une analyse de l'espace de recherche a montre que les meilleures congurations visitees sont relativement proches les unes des autres, regroupees dans des spheres de rayon xe. Avec ce type d'informations apprises, nous avons concu : (i) des algorithmes de diversication qui \prennent garde" a ne pas visiter la m^eme sphere a plusieurs reprises, (ii) des algorithmes d'intensication qui se focalisent sur l'exploration d'un perimetre limite en utilisant un parcours en largeur des spheres de ce perimetre, et (iii) des approches evolutionnistes pour gerer la diversite de sorte que les individus soient a la fois de bonne qualite eu egard a la fonction objectif et susamment distants les uns des autres. En fait, nous presentons une gamme de techniques (e.g. nouvelles fonctions d'evaluation) qui peuvent rendre la recherche heuristique \bien informee"