Algorithme mémétique guidé par l'apprentissage profond pour des problèmes de coloration de graphes
Olivier Goudet  1@  , Cyril Grelier  2@  , Jin-Kao Hao  3@  
1 : LERIA, Université d'Angers
Université d'Angers : EA2645, Université d\'Angers : EA2645, Université d\'Angers : EA2645
2 : LERIA - Université d'Angers
Université d'Angers : EA2645
3 : LERIA, Université d'Angers
Université d'Angers : EA2645, Université d\'Angers : EA2645, Université d\'Angers : EA2645

Étant donné un graphe G=(V,E) avec un ensemble de sommets V et un ensemble d'arêtes E, un problème de coloration de graphe consiste à trouver une partition des sommets en différents ensembles indépendants. Dans cet article, nous présentons un nouveau cadre de résolution qui combine un réseau de neurones profond avec les meilleurs outils des méta-heuristiques "classiques" pour ces problèmes de coloration. La méthode proposée est évaluée sur deux problèmes populaires de coloration de graphes (k-coloration et coloration pondérée). Les résultats des expériences menées sur des benchmarks de référence montrent que l'approche proposée est capable d'obtenir des résultats compétitifs pour les deux problèmes. Une analyse des valeurs de fitness prédites et effectives après la recherche locale montre que le réseau de neurones peut aider, dans une certaine mesure, à trouver de nouveaux points de départ prometteurs à chaque génération, ce qui facilite la découverte de solutions de haute qualité dans l'espace de recherche.


Personnes connectées : 2 Vie privée
Chargement...