La coloration de graphe permet d'attribuer une couleur à chacun des sommets d'un graphe de manière à ce que deux sommets reliés par une arête soient de couleur différente. Dans la majorité des cas on cherche à utiliser un nombre minimal de couleurs, dit nombre chromatique.
Dans la thèse de M-E. Marmion, il a été démontré qu’il était intéressant de s’intéresser aux voisins de même qualité afin d’améliorer la recherche de solutions aux problèmes d'optimisation, ces voisins sont appelés voisins neutres.
Dans de précédents travaux nous avons montré que certaines instances de la coloration de graphe présentaient de la neutralité et que l'utilisation de la neutralité dans les méthodes d'optimisation pouvaient permettre d'améliorer la qualité des résultats obtenus. L'objectif de ce projet est d'incorporer des mécanismes exploitant la neutralité dans des algorithmes déjà performants de la coloration de graphe comme TabuCol et d'étudier leurs comportements avec et sans l'exploitation de la neutralité.
* Le travail se décomposera en différentes tâches :
- Prise en main de l'existant : problème de coloration de graphe, neutralité, algorithmes de la littérature
- Sélection d'algorithmes de la littérature et implémentation sous ParadisEO
- Incorporer la neutralité dans les algorithmes de la tâche 2
- Test et comparaison des algorithmes sur les benchmarks du challenge DIMACS
* Environnement de travail :
C++, ParadisEO
|
