Coloration de graphes par algorithme mémétique à deux individus

National audienceOn propose un nouvel algorithme mémétique (algorithme évolutionnaire dont la mutation est remplacée par une recherche locale) pour le problème de coloration de sommets d'un graphe. Il s'agit d'un problème théorique classique déjà longuement étudié. L'objectif est de colorier les sommets d'un graphe avec le moins de couleurs possible tout en assurant que deux sommets reliés par une arête n'aient pas la même couleur. La population de l'algorithme proposé est réduite à deux solutions candidates seulement. Contrairement aux approches à base de population classiques, ici il n'y a donc pas d'opérateur de sélection des parents (qui sont à tous les coups les deux individus de la population), ni d'opérateur permettant de choisir les individus de la population à remplacer. De ce fait, le contrôle de la balance intensification/diversification en est simplifié. L'algorithme proposé est appliqué sur les instances de graphes DIMACS, benchmark le plus étudié depuis les années 1990. Il s'est révélé très performant, trouvant les meilleures colorations connues à ce sur plusieurs instances et dans des temps très courts. Pour plus de détails sur ce problème : http://www.laas.fr/files/MOGISA/Gondran-20120404.pdf