Un algorithme mémétique parallèle pour la coloration de graphe

Session : SS16-1 / SS16 : Résolution parallèle des problèmes mono ou multi objectifs (continu et/ou combinatoire)
Mercredi 10 février 11:00 - 12:20 Salle : RP9
Laurent Moalic et Alexandre Gondran

Nous proposons ici un algorithme mémétique parallèle appliqué au problème de coloration de graphe. Il s'appuie sur les principales caractéristiques de $HEAD$, mais en considérant plusieurs populations (de deux individus chacune). Ainsi tous les coeurs d'un ordinateurs sont amenés à fonctionner en parallèle. Les mécanismes que nous avons développés pour permettre aux populations d'interagir ont montré leur pertinence sur de nombreuses instances difficiles du benchmark DIMACS (benchmark de référence pour le problème de coloration de graphe). Ils ont pour but d'accélérer la recherche d'une part, mais aussi de réintroduire de la diversité lorsque les deux individus de la population sont identiques afin d'augmenter les chances d'aboutir à une solution légale.

Mots clés : coloration de graphe, mémétique, TabuCol, HEAD, parallélisation