Groupe d’études et de recherche en analyse des décisions

Le problème de la coloration des sommets d’un graphe : analyse des principales méthodes et proposition d’une nouvelle heuristique tabou agissant dans un espace des solutions original

Nicolas Zufferey Professeur titulaire, GSEM, Université de Genève, Suisse

Soit \(G=(V,E)\) un graphe dont l’ensemble des sommets est \(V\) et l’ensemble des arêtes est \(E\). Un sous-ensemble de \(V\) est un stable si tous ses sommets sont non adjacents deux à deux. Une \(k\)-coloration légale est une partition de \(V\) en \(k\) ensembles stables, appelés couleurs. Une coloration optimale est une \(k\)-coloration légale avec le plus petit \(k\) possible. Le Problème de la Coloration des Sommets d’un Graphe (PCSG) consiste à trouver une coloration optimale pour un graphe G donné. Ce problème étant NP-dur, de nombreuses heuristiques ont été proposées pour l’aborder : glouton, recuit simulé, tabou, recherche à voisinages variables, algorithmes génétiques hybrides, méthodes à mémoire adaptative, algorithmes de fourmis, recherche par dispersion, etc. Actuellement, les meilleurs algorithmes de coloration sont des méthodes évolutives hybridées par la procédure tabou Tabucol et agissent toutes dans le même espace des solutions que Tabucol.

L’exposé va se dérouler selon les étapes suivantes. Tout d’abord, une introduction au PCSG sera donnée, ainsi que quelques unes de ses applications possibles. Ensuite, les méthodes de coloration les plus connues seront décrites et la structure de leurs espaces des solutions respectifs sera analysée. Enfin, une méthode tabou très simple et ne contenant aucune procédure particulière de diversification sera proposée. Cette méthode va agir dans un espace des solutions qui n’a encore jamais été utilisé par une heuristique de recherche locale de coloration. Un tel espace des solutions peut être adapté à un grand nombre de problèmes. Les résultats obtenus seront comparés à ceux obtenus par les heuristiques de coloration les plus connues. La supériorité de cette nouvelle méthode tabou sur l’algorithme Tabucol sera notamment démontrée.