Programme > Par intervenant > Gondran Alexandre

Vendredi 28
Heuristiques et méta-heuristiques
Alexandre Gondran
› 12:00 - 12:30 (30min)
› Bât. C - Sigalas
Coloration de graphes par algorithme mémétique à deux individus
Alexandre Gondran  1@  , Laurent Moalic  2@  
1 : Laboratoire de Mathématiques Appliquées, Informatique et Automatique pour l'Aérien  (MAIAA)  -  Site web
Ecole Nationale de l'Aviation Civile - ENAC
ENAC 7 avenue Edouard Belin CS 54055 31055 TOULOUSE Cedex 4 FRANCE -  France
2 : Laboratoire Systèmes et Transports  (IRTES - SET)  -  Site web
Institut de Recherche sur les Transports, l'Energie et la Société - IRTES, Université de Technologie de Belfort-Montbeliard
90010 Belfort cedex -  France

On 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


Personnes connectées : 1