[PDF] UNIVERSITÉ DE MONTRÉAL UN ALGORITHME CONSTRUCTIF

View - Download UNIVERSITÉ DE MONTRÉAL UN ALGORITHME CONSTRUCTIF

Previous PDF

Next PDF

Titre:

Title:Un algorithme constructif eiÌifiÌicace pour le problème de coloration de graphe

Auteur:

Author:Mouhamed Mourchid Adio Adegbindin

Date:2013

Type:Mémoire ou thèse / Dissertation or Thesis

Référence:

Citation:Adegbindin, M. M. A. (2013). Un algorithme constructif eiÌifiÌicace pour le problème

de coloration de graphe [Mémoire de maîtrise, École Polytechnique de Montréal].

PolyPublie. https://publications.polymtl.ca/1136/

Document en libre accès dans PolyPublie

Open Access document in PolyPublie

URL de PolyPublie:

PolyPublie URL:https://publications.polymtl.ca/1136/

Directeurs de

recherche:

Advisors:Martine Bellaïche

Programme:

Program:Génie informatique

Ce ifichier a été téléchargé à partir de PolyPublie, le dépôt institutionnel de Polytechnique Montréal

This ifile has been downloaded from PolyPublie, the institutional repository of Polytechnique Montréal

https://publications.polymtl.ca

UNIVERSITÉ DE MONTRÉAL

UN ALGORITHME CONSTRUCTIF EFFICACE POUR LE PROBLÈME DE COLORATION

DE GRAPHE

MOUHAMED MOURCHID ADIO ADEGBINDIN

DÉPARTEMENT DE GÉNIE INFORMATIQUE ET GÉNIE LOGICIEL

ÉCOLE POLYTECHNIQUE DE MONTRÉAL

MÉMOIRE PRÉSENTÉ EN VUE DE L"OBTENTION

DU DIPLÔME DE MAÎTRISE ÈS SCIENCES APPLIQUÉES (GÉNIE INFORMATIQUE)

AVRIL 2013

© Mouhamed Mourchid Adio Adegbindin, 2013.

UNIVERSITÉ DE MONTRÉAL

ÉCOLE POLYTECHNIQUE DE MONTRÉAL

Ce mémoire intitulé:

UN ALGORITHME CONSTRUCTIF EFFICACE POUR LE PROBLÈME DE COLORATION

DE GRAPHE

présenté par : ADEGBINDIN Mouhamed Mourchid Adio en vue de l"obtention du diplôme de : Maîtrise ès Sciences Appliquées a été dûment accepté par le jury d"examen constitué de :

M. GALINIER Philippe

, Doct., président , Ph.D., membre et directrice de recherche

M. HERTZ Alain

, Doct. ès Sc., membre et codirecteur de recherche

Mme LAHRICHI Nadia

, Ph.D., membre iii

REMERCIEMENTS

Mes sincères remerciements vont à l"endroit de ma directrice de recherche Martine Bellaïche sans

qui ce travail n"aurait jamais vu le jour. Grâce à son aide, sa compréhension, son encadrement à

un moment crucial de ma carrière, cette maîtrise restera pour moi une expérience inoubliable.

Je remercie Alain Hertz, mon co-directeur de recherche dont le support et l"expertise ont joué un

rôle déterminant dans la réalisation de ce modeste travail. C"est un honneur pour moi d"avoir été

son étudiant.

Je tiens à remercier Samuel Pierre avec qui j"ai débuté ma maîtrise. Son expérience et ses

précieux conseils m"ont aidé énormément.

J"exprime ma gratitude à toute l"équipe du service aux étudiants de l"École Polytechnique de

Montréal et spécialement à Jonathan Pallet, Vanessa Casanovas i Michel, Claudette Fortier et

Philippe Razanakolona. Ils font un travail formidable. Je ne saurais oublier mes camarades de laboratoire, surtout Richard : ses compétitions de nuits blanches se sont avérées très efficaces durant la rédaction du mémoire. Merci à mon ami Raimi Rufai pour les sages conseils qu"il ne cesse de me prodiguer. Quelle chance de l"avoir connu. Enfin, je remercie du fond du coeur ma famille et mes amis pour leur amour, leur tendresse et leur soutien inconditionnels. iv

RÉSUMÉ

v

ABSTRACT

The Vertex Coloring Problem (VCP) requires to assign a color to each vertex in such a way that colors on adjacent vertices are different and the number of colors used is minimized. Due to its numerous practical applications (scheduling, resource allocation, etc.) and computational complexity, the VCP is one of the most studied problems in combinatorial optimization. Several methods have been proposed to solve the VCP. They can be classified in three families: exact approaches whose running time increases exponentially with the size of the graph, greedy algorithms which approximate the optimal solution in a short time and metaheuristic methods which are the best performing algorithms, but are more complex and time consuming. In this work, we design a polynomial incremental algorithm which colors the graph, one class at a time by favouring the neighbours of neighbours of already colored vertices. Computational results on the set of DIMACS benchmark instances demonstrate the efficiency of the proposed algorithm which gives the same results as the popular metaheuristic TABUCOL in reasonable running time. vi

TABLE DES MATIÈRES

REMERCIEMENTS ..................................................................................................................... III

RÉSUMÉ ....................................................................................................................................... IV

ABSTRACT ................................................................................................................................... V

TABLE DES MATIÈRES ............................................................................................................ VI

LISTE DES TABLEAUX .......................................................................................................... VIII

LISTE DES FIGURES .................................................................................................................. IX

LISTE DES SIGLES ET ABRÉVIATIONS ................................................................................. X

CHAPITRE 1 INTRODUCTION ............................................................................................... 1

1.1 Le Problème de la coloration de graphe ........................................................................... 1

1.2 Domaines d"applications .................................................................................................. 2

CHAPITRE 2 REVUE DE LITTÉRATURE ............................................................................. 4

2.1 Les méthodes exactes ....................................................................................................... 4

2.2 Les méthodes constructives .............................................................................................. 5

2.3 Les métaheuristiques ........................................................................................................ 6

2.3.1 Les Algorithmes de recherche locale ........................................................................... 6

2.3.2 Les algorithmes génétiques .......................................................................................... 7

2.3.3 Les algorithmes hybrides ............................................................................................. 7

CHAPITRE 3 ALGORITHME PROPOSÉ ................................................................................ 9

3.1 Description de l"algorithme .............................................................................................. 9

3.2 Calcul de la complexité .................................................................................................. 11

3.3 Particularités de l"algorithme NoN ................................................................................ 12

3.4 Exemple illustratif .......................................................................................................... 13

CHAPITRE 4 RÉSULTATS EXPÉRIMENTAUX ................................................................. 15

vii 4.1

Détails de l"implémentation et choix des algorithmes de comparaison ......................... 15

4.2 Plan d"expérience ........................................................................................................... 16

4.3 Contribution de chaque composante de l"algorithme proposé ....................................... 16

4.4 Le temps d"exécution et le multithreading ..................................................................... 19

4.5 Positionnement de l"algorithme proposé dans un contexte général ............................... 20

CHAPITRE 5 CONCLUSION ET PERSPECTIVES ............................................................... 25

BIBLIOGRAPHIE ........................................................................................................................ 27

viii

LISTE DES TABLEAUX

Tableau 4.1 : Contribution de chaque composante de l"algorithme NoN....................................... 17

Tableau 4.2 : Justification de la priorité dans les règles de sélection ............................................. 18

Tableau 4.3 : Le temps d"exécution de l"algorithme NoN .............................................................. 20

Tableau 4.4: Résultats obtenus par TABUCOL, DSATUR et NoN sur les graphes DIMACS ..... 21 ix

LISTE DES FIGURES

Figure 1 : Coloration optimale de G avec 3 couleurs ....................................................................... 2

Figure 2 : Algorithme des voisins des voisins ................................................................................ 11

x

LISTE DES SIGLES ET ABRÉVIATIONS

VCP Vertex Coloring Problem

DIMACS Discrete Mathematics and Theoretical Computer Science 1

CHAPITRE 1 INTRODUCTION

" Aux âmes bien nées, la valeur n"attend point le nombre des années. ». Voilà une assertion de

Corneille qui se vérifie pour la théorie des graphes. Quoique relativement récents, les graphes

sont devenus incontournables en mathématiques discrètes et proposent des méthodes simples et

puissamment efficaces pour la résolution des problèmes concrets de la vie quotidienne dans des domaines multiples, qu"il s"agisse de déterminer le nombre minimal de caméras de surveillance

nécessaires pour la sécurité d"un immeuble, former des équipes de travail en se fondant sur les

affinités des participants, trouver le plus court chemin pour le routage dans un réseau de

communication, déterminer l"ordre dans lequel un candidat à la présidentielle américaine doit

visiter les cinquante états afin de minimiser le trajet, augmenter la recette globale d"une

compagnie aérienne en assignant à chaque vol l"avion le plus adapté, etc. Un graphe est un ensemble de sommets (noeuds, points) reliés entre eux par des arêtes (lignes,

traits) symbolisant une certaine relation. Notre objectif de recherche est de concevoir et

d"implémenter un algorithme constructif efficace et fiable pour résoudre le problème de la

coloration de graphe qui est un classique de la théorie des graphes. En d"autres termes, il s"agit de

proposer un algorithme d"ordre polynomial et déterministe qui donne, en un temps de calcul raisonnable, de meilleurs résultats que les méthodes constructives connues.

Après avoir décrit le problème de coloration de graphe et mentionné ses applications pratiques,

nous nous proposons tout d"abord de résumer les méthodes de résolution existantes en mettant

l"accent sur les plus connues, puis de détailler l"algorithme proposé et enfin de présenter et

commenter objectivement les résultats obtenus.

1.1 Le Problème de la coloration de graphe

Soit ݆ ൩቗ݕǾ݄ቘun graphe simple non orienté où ݕ représente l"ensemble des sommets et %

l"ensemble de ses arêtes. Deux sommets ݮ et ݯ sont adjacents si ݮ et ݯ sont reliés par une arête

de E. Une clique est un ensemble de sommets deux à deux adjacents et un stable est un ensemble de sommets deux à deux non-adjacents. 2

Le problème de coloration de graphe consiste à assigner à chaque sommet une couleur de sorte

que deux sommets adjacents n"aient pas la même couleur, tout en utilisant un nombre minimal de couleurs. Ce dernier est le nombre chromatique χ቗݆ቘ du graphe G.

La figure ci-après illustre la coloration optimale d"un graphe G avec χ቗݆ቘ൩ Β.

Figure 1 : Coloration optimale de G avec 3 couleurs

1.2 Domaines d"applications

La coloration de graphe est très prisée pour la résolution de problèmes complexes d"optimisation

combinatoire. En effet, chaque fois que l"on désire minimiser le nombre de ressources pour

effectuer une série de tâches avec la contrainte que certaines tâches ne doivent pas partager la

même ressource, il suffit de résoudre le problème de coloration pour le graphe dont les sommets

représentent les tâches et où deux sommets sont adjacents si les tâches correspondantes violent la

contrainte.

Ainsi, l"allocation des bandes de fréquences dans un réseau cellulaire où des cellules voisines ne

doivent pas avoir la même bande de fréquences afin d"éviter les interférences [1], la planification

des examens dans une université de sorte qu"un étudiant n"ait pas deux examens au même

moment [2], l"organisation d"un tournoi sur la plus courte durée possible en gardant à l"esprit que

certaines rencontres ne sauraient avoir lieu simultanément [3], la gestion des ressources dans un univers de Cloud Computing [4], sont quelques exemples dans la longue liste des applications pratiques du problème de coloration de graphe. 3 Pour demeurer compétitif et utilisable, un algorithme de coloration de graphe doit trouver une

bonne solution en un temps raisonnable, et ce, pour n"importe quel graphe. C"est pourquoi,

comme nous le verrons dans le chapitre suivant, la coloration a fait l"objet de nombreux travaux de recherche. 4

CHAPITRE 2 REVUE DE LITTÉRATURE

Le problème de coloration de graphe est connu comme étant NP-difficile [5], c"est-à-dire qu"il

n"existe pas à ce jour un algorithme polynomial qui donne la coloration optimale pour tout

graphe. Dès lors, la coloration de graphe a fait l"objet de nombreuses études résultant en une

multitude de méthodes de résolution que l"on pourrait scinder en trois catégories : les méthodes

exactes, les méthodes constructives et les métaheuristiques. Nous présentons dans ce chapitre les

solutions les plus connues. Pour plus de détails, nous recommandons les revues de littérature de

Malaguti et Toth [6] et de Galinier et Hertz [7].

2.1 Les méthodes exactes

La méthode triviale qui vient à l"esprit pour colorer un graphe de ݧ sommets est la méthode

௾ assignations possibles pour chaque nombre de

envisageable lorsque le nombre ݧ de sommets est élevé, le temps d"exécution étant d"ordre

exponentiel. C"est d"ailleurs cette impraticabilité, talon d"Achille des méthodes exactes, qui

justifie leur petit nombre comparativement aux heuristiques proposées dans la littérature. Mentionnons cependant l"algorithme de Randall-Brown [8] qui propose de colorer les sommets

du graphe à l"aide d"un algorithme d"énumération implicite dans lequel chaque sommet est coloré

amélioré cette idée en démarrant l"algorithme par la coloration d"une clique maximale, ce qui

donne une borne inférieure sur le nombre chromatique, et en utilisant des critères de sélection

pour le prochain sommet à colorer. Mehrotra et Trick [11], en traduisant la coloration de graphe

en un problème d"optimisation linéaire en nombres entiers (OLNE), ont développé un algorithme

de génération de colonnes plus connu sous le nom de branch and price. L"objectif est de

minimiser le nombre total de stables nécessaires pour recouvrir tous les sommets du graphe et, en

assignant à chaque stable une couleur différente. Cette approche de résolution s"est révélée très

intéressante et a servi de tremplin à la plupart des algorithmes exacts ultérieurs [12-15]. 5

2.2 Les méthodes constructives

Les méthodes constructives colorent le graphe un sommet à la fois, en choisissant à chaque étape

celui qui semble être le meilleur selon un critère bien défini, sans jamais se remettre en cause.

Elles sont très rapides et donnent la plupart du temps une bonne approximation de la solution

optimale, mais la qualité du résultat dépend fortement des divers paramètres tel l"ordre de

parcours du graphe. L"algorithme DSATUR [9] développé par Brélaz est incontestablement le plus connu en raison

de son efficacité et de sa simplicité. Le principe est le suivant : attribuer la plus petite couleur

disponible aux noeuds par ordre décroissant de degré de saturation - nombre de couleurs

différentes de ses voisins -; en cas d"égalité, prioriser le noeud de degré maximal. L"algorithme

s"arrête lorsque tous les sommets sont colorés.

L"autre algorithme, également très populaire, a été proposé la même année par Leighton [16]. Il

s"agit de l"algorithme Recursive Largest First (RLF) qui construit les classes de couleur, l"une

après l"autre - les sommets d"un stable qui ont la même couleur forment une classe -; pour chaque

couleur k, la construction se fait comme suit, avec ݔ ୒ représentant l"ensemble des noeuds non colorés qui peuvent recevoir la couleur k et ݔ ୓ l"ensemble des noeuds non colorés qui ne peuvent

plus recevoir la couleur k (car ils sont voisins d"au moins un noeud coloré avec la couleur k). Au

début de la création de la classe de couleur k, U

1 est égal à l"ensemble des sommets qui n"ont

aucune des k-1 premières couleurs et U

2 est vide. Puis, tant que ݔ୒൪ ׫

opérations suivantes :

· Assigner la couleur k au noeud v de U

1 qui a le plus de voisins dans U2. En cas d"égalité,

choisir un sommet de U

1 qui a le moins de voisins dans U1. Ôter v de U1.

· Transférer tous les voisins de v qui sont dans U

1 vers U2.

Lorsque la classe de couleur k est construite (U

1 est vide), on passe à la couleur k+1, en

transférant tous les sommets de U

2 vers U1.

Bollobas et Thomason [17] ont suggéré d"assigner de façon récurrente une couleur au stable de

taille maximale dans le graphe formé par les noeuds non colorés, mais cet algorithme peut être

très long vu que la recherche du stable de taille maximale dans un graphe est un problème NP- complet [5]. 6

Signalons dans cette section la méthode de Culberson et de Luo [18] qui présente la particularité

de remettre en cause les couleurs antérieurement assignées aux noeuds. En fait, ils utilisent de

façon itérative un algorithme séquentiel pour colorer le graphe en s"assurant qu"à chaque

itération, le nombre de couleurs utilisées ne peut augmenter.

Même si les algorithmes constructifs ne donnent pas les meilleurs résultats, on s"en sert souvent

comme point de départ dans les métaheuristiques, ou pour avoir une estimation rapide du nombre chromatique d"un graphe.

2.3 Les métaheuristiques

Par opposition aux méthodes constructives qui partent d"un graphe non coloré et attribuent

graduellement une couleur à un sommet ou à un ensemble de sommets pour aboutir à une

coloration totale du graphe, les métaheuristiques débutent par une coloration du graphe choisie

arbitrairement et tentent d"obtenir une meilleure solution en manipulant la coloration courante.

Cette approche de résolution est plutôt payante car les meilleurs algorithmes actuels pour la

coloration de graphe sont indéniablement les métaheuristiques. Elles constituent un domaine

phare de recherche pour les théoriciens des graphes et sont, sans surprise, les algorithmes les plus

nombreux dans la littérature. On peut les subdiviser en trois types : les algorithmes basés sur la

recherche locale, les algorithmes génétiques et les algorithmes hybrides. Nous encourageons le

lecteur à consulter les articles de Malaguti et Toth [6] et de Galinier et Hertz [7] pour une revue

de littérature plus détaillée.

2.3.1 Les Algorithmes de recherche locale

Les algorithmes de recherche locale sont devenus très prisés depuis la publication du très

populaire TABUCOL [19] par Hertz et de Werra en 1987 en s"inspirant de la recherche taboue

[20] de Glover. À partir d"une coloration (solution initiale) du graphe avec conflits - arêtes ayant

la même couleur à leurs extrémités -, TABUCOL tente de minimiser le nombre de conflits

(fonction objectif) en modifiant la couleur d"un sommet intervenant dans un conflit (voisinage).

La couleur changée ne peut être assignée au même sommet qu"après un certain nombre

d"itérations : cette couleur est dite taboue pour ce sommet. La simplicité de TABUCOL et le nouveau type de voisinage suggéré par Morgenstern - Impasse Class neighborhood - en 1996

[21] ont contribué au design de meilleurs algorithmes proposés par la suite : Variable

7 Neighborhood Search (VNS) de Avanthay et al. [22], DYN PARTIACOL et FOO- PARTIACOL

Le recuit simulé est une méthode de recherche locale également très connue. Il se différencie

principalement de la recherche taboue par le critère d"acceptation d"une solution dans le

voisinage. Ce critère est déterministe pour la recherche taboue mais repose sur un processus

probabiliste pour le recuit simulé. Johnston et al. [25] a essayé le recuit simulé sur le problème de

coloration de graphe et a proposé, en plus de trois autres implémentations, un algorithme nommé

XRLF qui généralise l"algorithme RLF décrit à la section 2.2. En effet, XRLF construit une

classe de couleur C en répétant la procédure suivante N1 fois avant de choisir le meilleur résultat.

Au départ C est vide et tous les sommets non colorés sont candidats. Si le nombre de candidats

est inférieur à une valeur seuil S, on utilise une méthode exacte pour colorer le graphe résiduel.

Sinon, Si C est vide, ajouter au hasard un candidat à C et déclarer tous ses voisins non candidats;

si C n"est pas vide, choisir dans un sous-ensemble aléatoire de candidats de taille T, le noeud qui a

le plus de voisins déclarés non candidats. Les valeurs des paramètres N1, S et T doivent fixés

selon le graphe à colorer pour garantir une bonne performance.

2.3.2 Les algorithmes génétiques

Une autre approche de résolution du problème a été suggérée par Davis en 1991 [26]. Il s"agit

d"un algorithme purement génétique qui représente une solution par la permutation des sommets

et leur attribue de façon séquentielle la première couleur disponible. Les résultats obtenus sur les

graphes ne sont pas fameux comparés aux autres métaheuristiques.

2.3.3 Les algorithmes hybrides

La combinaison des algorithmes de recherche locale et des algorithmes génétiques a donné

naissance aux algorithmes hybrides ou mémétiques. Ces derniers fournissent de bons résultats sur

les graphes au prix d"une complexité sans cesse accrue. Le principe consiste à explorer et

diversifier une population de solutions grâce à deux types principaux d"opérateurs : l"opérateur de

mutation qui crée de nouvelles solutions en modifiant l"une des solutions initiales à l"aide d"un

algorithme de recherche locale et l"opérateur de croisement qui crée de nouvelles solutions en combinant des parties de deux ou de plusieurs solutions existantes (Voir [27]). Citons, entre

autres, l"algorithme HCA de Galinier et Hao [28] qui utilise une version améliorée de

8 TABUCOL et un opérateur de croisement appelé Greedy Partitioning Crossover. À partir des solutions parents qui sont des partitions du graphe, l"opérateur Greedy Partitioning Crossover

considère chaque parent et en extrait la classe de cardinalité maximale pour constituer la solution

enfant. En 2008, Malaguti et al. ont proposé le MMT [29] qui adapte l"opérateur de croisementquotesdbs_dbs30.pdfusesText_36

[PDF] coloriage magique avec les puissances correction

[PDF] coloriage numérique isabelle guillot

[PDF] écrire une fraction sous la forme d'un entier et d'une fraction cm2

[PDF] les fractions supérieures ? 1

[PDF] cours cap coiffure la permanente

[PDF] cours coloration cap coiffure

[PDF] boxe anglaise veteran

[PDF] reglement boxe anglaise

[PDF] boxe anglaise technique de base

[PDF] boxe anglaise pdf

[PDF] regle boxe française

[PDF] yvain combat le chevalier de la fontaine

[PDF] yvain un modèle de chevalier

[PDF] saint georges et le dragon histoire

[PDF] la légende de saint michel