Algorithmes Heuristiques pour Coloration de Graphe
Algorithmes Heuristiques pour Coloration de Graphe
Thèse de doctorat
Spécialité : Informatique
Le 19 Novembre 2009
À Angers
Par
Tout d’abord, je suis très reconnaissant à l’égard de mes encadrants, Jin-Kao Hao et Pascale
Kuntz, pour m’avoir fait découvrir un domaine de recherche très intéressant, et pour avoir
tout fait afin de me permettre de travailler dans d’excellentes conditions. L’organisation et la
planification de cette thèse ont été parfaites - e.g. j’ai passé 1.5 ans à Nantes (équipe COD
du LINA) et 1.5 ans à Angers (équipe MOA du LERIA). Je les remercie vivement pour tous
les conseils, avis et discussions qui m’ont permis de bien comprendre les idées majeures du
domaine de recherche. Cette thèse a été financée par la région Pays de la Loire et je lui en suis
très reconnaissant.
Mes sincères remerciements s’adressent à Philipe Galinier pour avoir rapporté ce mémoire et
pour son implication dans nos travaux. Je tiens à remercier particulièrement Thomas Stützle
pour avoir accepté de rapporter ma thèse et pour avoir apporté des idées et des questions
très éclairées et réalistes le jour de la soutenance. Je voudrais remercier aussi particulièrement
à Olivier Hudry pour ses observations et questions détaillées qui m’ont permis d’améliorer le
manuscrit. Je suis également très reconnaissant envers Gérard Plateau pour son amabilité et
son engagement actif dans le bon déroulement du processus de soutenance.
Je profite pour exprimer mes vifs remerciements à tout le collectif d’Angers que j’ai trouvé très
flexible et très agréable. En particulier, je remercie Jean-Philippe Hamiez pour avoir partagé avec
moi sa riche expertise sur le problème de coloration. Je ne sais pas si Jean-Michel Richer s’est
rendu compte que les détails techniques dont nous avons discutés m’ont beaucoup aidé ; je profite
pour lui adresser ma profonde gratitude. Je remercie aussi tous les autres enseignant-chercheurs
d’Angers qui ont contribué à la relecture du manuscrit et des transparents, notamment Matthieu
Basseur, David Genest et Adrien Goëffon. Lionel Chauvin a contribué avec des relectures de
détail et je lui en suis très reconnaissant. Je remercie Jorge Maturana et Benoı̂t Da Mota pour
leurs nombreuses aides pratiques au cours de temps. Je remercie par la même occasion à tous les
autres collègues avec qui j’ai partagé de nombreux bons moments dans les pauses de midi et de
café : Sylvain Lamprier, Giglia Gomez, Nadarajen Veerapen, Fabien Chhel, Adila Bouabdallah.
J’ai beaucoup apprécié à Angers la qualité du service technique (merci Eric Girardeau, Stéphane
Vincendeau et Frantz de Germain) et le secrétariat (merci Catherine Pawlonski). Je remercie
aussi Zhipeng Lü pour son aide sur les tests statistiques. Je voudrais rendre hommage à Julien
Robet, un doctorant remarquable qui était probablement déjà en mesure de finir sa thèse dans
sa deuxième année.
Je remercie mes collègues à Nantes pour les bons moments passés avec eux : Claudia Marinica,
Toader Gherasim, Vlad Georgescu, Nicolas Beaume, Pierrick Bruneau et Bruno Pinaud. Merci
Julien Blanchard pour les informations concernant les algorithmes de Multidimensional Scaling.
Merci Petr Pošı́k pour le document sur les stratégies évolutionnistes de diversité à base de
distances. Je remercie Adina Florea pour son support dans mes projets. Je remercie Dragoş
Ghioca pour ses précieux conseils toutes ces années.
Comment aurais-je pu faire passer agréablement les longues journées de travail de recherche
sans Daniela ? En dernier point, mais non le moindre, je te remercie, car c’est avec toi que j’ai
vécu les plus beaux moments durant la thèse.
Permettez moi de dédier cette thèse à la mémoire du mon grand père Nicolae Marica.
Table des matières
Introduction Générale 1
1 Introduction 5
1.1 Problèmes difficiles et algorithmes heuristiques . . . . . . . . . . . . . . . . 6
1.1.1 Techniques d’apprentissage en optimisation combinatoire . . . . . . 7
1.1.2 Extraction d’informations “en ligne” . . . . . . . . . . . . . . . . . . 11
1.2 Coloration de graphe – plateforme d’évaluation expérimentale . . . . . . . . 12
1.2.1 Domaines d’application . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2.2 Définitions formelles et codage de configurations . . . . . . . . . . . 15
1.2.3 Instances DIMACS . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.2.4 Résultats de référence pour l’évaluation et la comparaison des per-
formances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
v
3 Cartographie de l’Espace de Recherche 41
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.1.1 Analyse de l’espace de recherche . . . . . . . . . . . . . . . . . . . . 42
3.2 La recherche locale typique et la vision globale . . . . . . . . . . . . . . . . 43
3.3 Cartographie de l’espace de recherche . . . . . . . . . . . . . . . . . . . . . 45
3.3.1 L’opération de cartographie . . . . . . . . . . . . . . . . . . . . . . . 45
3.3.2 Distribution spatiale des meilleurs optima . . . . . . . . . . . . . . . 47
3.3.3 Distribution spatiale des configurations visitées en série sur une
courte période . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3.4 Distribution spatiale des colorations visitées en série sur une longue
période . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.4 Conclusion du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Publications 134
vii
Introduction Générale
Contexte du travail
Les problématiques étudiées dans cette thèse portent sur l’optimisation combinatoire
et sur les stratégies heuristiques de résolution. Un des écueils bien connus des algorithmes
heuristiques est leur difficulté à sortir de bassins d’attraction d’optima locaux de qualité
plus mauvaise que celle de l’optimum global. Plus généralement, nous observons que les
stratégies heuristiques classiques manquent parfois d’une vue d’ensemble ; il semble plutôt
difficile d’intégrer une “auto-conscience” dans un processus de résolution. Pour illustration,
certaines recherches locales peuvent être comparées à la « recherche du mont Everest dans
un brouillard épais tout en souffrant de l’amnésie » [Russell and Norvig, 2002].
Cette thèse est consacrée à l’élaboration de stratégies pour faire face à ce type de dif-
ficultés. Par exemple, il pourrait être possible de réduire les effets de type “amnésie” en
collectant des informations pertinentes pendant le processus de résolution, afin de guider
plus efficacement l’exploration de l’espace de recherche. Une piste de recherche en plein
essor consiste à combiner des heuristiques de résolution avec des méthodes de fouille de
données et d’apprentissage. L’objectif de la fouille de données concerne « l’extraction d’in-
formations implicites, auparavant inconnues, et potentiellement utiles » [Frawley et al.,
1992] à partir de grands volumes de données. Cet objectif n’est pas si éloigné de celui du
chercheur en optimisation combinatoire confronté au déploiement de méthodes d’explora-
tion dans de très vastes espaces de recherche. Dans cette thèse notre cadre expérimental
a été celui du problème de la coloration de graphes.
Objectifs
L’un de nos objectifs principaux a été de concevoir des techniques pour rendre la
stratégie de recherche plus “informée”, plus “auto-consciente”. Bien que l’apprentissage
automatique semble une bonne piste, il demeure un certain nombre de challenges à relever.
Le plus important concerne le niveau opérationnel et la complexité de calcul : il est essentiel
que toute information supplémentaire intégrée dans un processus de résolution n’introduise
pas d’importants coûts supplémentaires de calcul.
Le cadre conceptuel pour atteindre l’objectif ci-dessus est fondé sur une mesure de
distance qui permet de comparer les solutions candidates (configurations). En analyse de
données, la détection de structures met généralement en œuvre une comparaison : par
exemple, lorsque l’on classifie des données, on cherche à regrouper dans une même classe
les individus qui se ressemblent et dans des classes séparées des individus qui diffèrent.
D’un point de vue opérationnel, cette comparaison est basée sur le concept de distance.
Un challenge particulier pour le problème de coloration a été de concevoir un algorithme
très rapide pour calculer cette distance.
1
Introduction Générale
Un objectif plus général a été d’établir des principes de guidage et d’orientation dans
l’espace de recherche en faisant appel à cette mesure de distance. Par exemple, pour
avoir une vue d’ensemble de la trajectoire d’une recherche locale, il suffit d’enregistrer un
ensemble restreint de sphères – une sphère couvre toutes les configurations jusqu’à une
certaine distance d’une “configuration centre”. Nous avons cherché à utiliser des principes
d’orientation dans l’espace de recherche pour concevoir à la fois des recherches locales et
des algorithmes évolutionnistes. Pour tenter d’évaluer sous différents angles l’apport de
connaissances supplémentaires dans nos heuristiques, nous avons considéré la possibilité
d’introduire de nouvelles fonctions d’évaluation dans un algorithme Tabou.
Les algorithmes que nous avons développés ont été appliqués au cadre de la coloration
mais pourraient être transposés à d’autres problèmes d’optimisation, pourvu qu’il soit
possible de définir une distance entre les solutions candidates du problème.
Principales contributions
Notre apport principal concerne quatre directions majeures :
1. l’analyse de l’espace de recherche (cartographie) permettant de dégager des pro-
priétés structurelles sur les solutions potentielles, afin de guider des stratégies de
recherche locale ;
2. le développement d’un nouvel algorithme évolutionniste avec un croisement “informé”
et une diversité de population garantie par la mesure de distance entre les individus ;
3. l’introduction de fonctions d’évaluation plus informées, spécifiques au problème
traité ;
4. un algorithme exact pour calculer la distance de transfert entre parti-
tions/colorations.
Analyse d’Espace et Recherches Locales Guidées : Nous avons analysé la dis-
tribution spatiale des configurations de grande qualité obtenues par un algorithme de
recherche Tabou. Ces configurations ont été comparées avec une mesure de distance qui
représente le nombre minimal de transitions de voisinage pour passer d’une coloration
à l’autre. Nous avons eu recours à un algorithme d’analyse de données (ici le Multidi-
mensional Scaling) pour établir une “cartographie” de l’espace de recherche. Nous avons
montré expérimentalement que ces configurations ne sont pas distribuées aléatoirement,
mais qu’elles sont regroupées en classes (clusters) qui peuvent être recouvertes par des
sphères de diamètre spécifique.
Cette propriété nous a permis de développer une recherche Tabou (TS–Div) qui en-
registre les sphères visitées lors de son exploration et guide ensuite l’exploration vers des
sphères non encore visitées. De plus, nous avons ajouté un algorithme d’intensification
(TS–Int) qui fait des recherches méticuleuses dans un périmètre limité autour d’une confi-
guration donnée. S’il existe une solution à moins d’une certaine distance de ce point donné,
TS–Int la trouve avec un taux de réussite de 100%. L’article complet a été accepté par
Computers & Operations Research [Porumbel et al., 2010] ; plus de détails et d’idées sur la
2
Introduction Générale
Plan de la thèse
Le manuscrit est organisé comme suit.
– Dans le premier chapitre, nous décrivons brièvement la portée et les objectifs des
algorithmes heuristiques et nous insistons sur les limitations qui sont adressées dans
cette thèse. Nous introduisons la coloration de graphe, notre cadre expérimental, et
nous établissons la terminologie et les notations de base ;
– Dans le deuxième chapitre, nous abordons un premier algorithme de coloration,
une recherche Tabou de base qui servira à plusieurs méthodes de résolution de cette
thèse. Nous nous intéressons ici à améliorer cet algorithme basique avec des fonctions
d’évaluation bien informées et avec une gestion réactive de la durée Tabou. Cela a
3
Introduction Générale
4
Chapitre 1
Introduction
Dans la première partie de ce chapitre nous introduisons le contexte et la
motivation des approches heuristiques en optimisation combinatoire. Nous
portons une attention particulière aux inconvénients des heuristiques qui
pourraient potentiellement être améliorés par apprentissage automatique.
Dans la deuxième partie, nous présentons notre cadre expérimental – le
problème de coloration de graphe ; puis nous décrivons synthétiquement les
algorithmes les plus reconnus introduits ces trois dernières décennies.
Sommaire
1.1 Problèmes difficiles et algorithmes heuristiques . . . . . . . . . 6
1.1.1 Techniques d’apprentissage en optimisation combinatoire . . . . 7
1.1.2 Extraction d’informations “en ligne” . . . . . . . . . . . . . . . . 11
1.2 Coloration de graphe – plateforme d’évaluation expérimentale 12
1.2.1 Domaines d’application . . . . . . . . . . . . . . . . . . . . . . . 13
1.2.2 Définitions formelles et codage de configurations . . . . . . . . . 15
1.2.3 Instances DIMACS . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.2.4 Résultats de référence pour l’évaluation et la comparaison des
performances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5
Chapitre 1. Introduction
1. La classe de complexité P réunit les problèmes de décision qui peuvent être résolus en temps polyno-
mial sur une machine déterministe. La classe N P fait référence aux problèmes de décision Non-déterministes
Polynomiaux qui peuvent être résolus sur une machine non déterministe en temps polynomial. Il est gé-
néralement admis que P 6= N P . Un problème d’optimisation X est dit N P -dur s’il existe un problème de
décision N P -complet Y tel que Y se réduit à X en temps polynomial [Garey et al., 1979].
6
1.1 Problèmes difficiles et algorithmes heuristiques
2. Notons qu’une autre approche en optimisation discrète est représentée par les algorithmes à base
d’énumération implicite (e.g. branch-and-bound, branch-and-cut). Ces algorithmes sont souvent appliqués
lorsque l’espace de recherche peut être énuméré de façon efficace.
3. L’objectif de ce chapitre n’est pas de faire un exposé sur les métaheuristiques ou sur leurs résultats ;
nous renvoyons pour cela le lecteur intéressé à [Hoos and Stützle, 2004].
7
Chapitre 1. Introduction
En effet, l’analyse de données permet de « dégager, derrière une grande masse d’in-
formations, des structures d’organisation entre ces dernières » [Lerman et al., 1981]. Cet
objectif, présent chez les fondateurs du domaine, a été repris par les pionniers de la fouille
de données confrontés au début des années 90 au passage à l’échelle et à l’explosion de
la complexité des données à traiter. Ainsi, la fouille de données a pour objectif de four-
nir des méthodes d’apprentissage automatiques et semi-automatiques pour extraire des
connaissances valides et exploitables à partir de grands volumes de données.
L’espace de recherche représente un exemple classique de grand volume de données,
et ainsi, ce type de méthode statistique pourrait fournir des informations exploitables, i.e.
qui peuvent être utilisées pour rendre la stratégie de recherche “mieux-informée”. Certes, le
croisement des algorithmes génétiques, la liste Tabou ou la phéromone artificielle dans les
algorithmes de fourmis introduisaient déjà une forme d’apprentissage implicite. Toutefois,
les méthodes de fouille de données nous permettent d’analyser des données plus complexes,
pour aller au-delà des méthodes actuelles de la littérature.
Le recours à l’apprentissage en optimisation semble être une piste de recherche très
jeune qui a eu un essor notable au cours de la dernière décennie – de nombreuses ré-
férences sont disponibles dans [Battiti et al., 2008]. Bien que les objectifs des techniques
d’apprentissage puissent varier considérablement par rapport à la communauté d’optimisa-
tion, ils ont été déjà classifiés dans quatre approches importantes (voir [Boyan et al., 2000],
une riche collection de 14 études groupées en quatre classes). Nous n’affirmons pas que
cette classification soit absolue ou sans chevauchement, mais nous la considérons toujours
d’actualité pour les directions de recherche les plus actives :
Analyse de l’espace de recherche Des informations fondamentales peuvent être ex-
traites par des analyses statistiques des espaces de recherche. En fait, toute heuris-
tique efficace tient compte, explicitement ou implicitement, des propriétés structu-
relles de l’espace de recherche. Il existe plusieurs approches pour analyser l’espace
et elles peuvent se focaliser sur les aspects suivants, sans se limiter à ceux-ci : (i) la
forme de la surface de recherche (e.g. convexe ou non convexe, information primor-
diale dans l’optimisation numérique), (ii) des indicateurs de rugosité et de difficulté
(e.g. quelques termes anglo-saxons sont bien représentatifs : ruggedness, smoothness
ou fitness-distance correlation), (iii) les similarités et les variables partagées par les
optima locaux (e.g. le “backbone”), ou (iv) le nombre, la qualité et la distribution
spatiale des optima locaux – voir également [Hoos and Stützle, 2004, Chapitre 5] ou
la Section 3.1.1.
Apprentissage de nouvelles fonctions d’évaluation Cela est une direction active de
recherche, consacrée à des modifications de la fonction objectif qui permettent de
mieux guider l’heuristique à travers l’espace des solutions. Pour toute configura-
tion donnée, une meilleure fonction d’évaluation devrait mieux estimer le potentiel
pour conduire à une solution. Cela est particulièrement utile si de nombreuses confi-
gurations partagent la même valeur de la fonction objectif ; s’il y a une façon de
discriminer ces configurations, il y aurait moins d’optima locaux pour le processus
de recherche. Bien que la fonction d’évaluation soit souvent conçue par le chercheur,
elle peut être aussi ajustée par le processus de recherche en fonction des informa-
8
1.1 Problèmes difficiles et algorithmes heuristiques
tions acquises. L’algorithme Guided Local Search [Voudouris and Tsang, 2003] est
un exemple représentatif issu de cette direction de recherche ; il propose de modifier
la fonction objectif lorsque le processus de recherche est bloqué dans un optimum
local.
Modèles de génération de solutions Cette direction est consacrée à l’exploitation des
informations concernant les optima locaux visités afin de fournir des indications sur
la génération de meilleures solutions. Pour cela, on peut créer un modèle pour pro-
duire de nouvelles solutions avec des opérateurs spécialisés, e.g. en fixant quelques
variables à certaines valeurs (partagées par tous les optima locaux visités), en es-
timant la distribution des optima globaux, ou en déterminant la “probabilité” de
trouver une solution dans une certaine région. Il a été souligné que « les algorithmes
génétiques font exactement ce type de modélisation » [Boyan et al., 2000] : la po-
pulation garde un ensemble de meilleures configurations et les opérateurs génétiques
essaient de les combiner pour construire de meilleures solutions. Dans un certain
sens, au moins pour certains algorithmes mémétiques en optimisation discrète, cette
interprétation des algorithmes génétiques pourrait être plus précise que la théo-
rie Darwiniste. Une présentation pédagogique de model-driven search est disponible
dans le Chapitre 6 de [Battiti et al., 2008], où il est indiqué que l’optimisation par
colonies de fourmis (Ant Colony Optimization) et les algorithmes par estimation de
distribution (Estimation of Distribution Algorithms) sont également fondés sur des
principes similaires.
Sélection d’algorithme et de paramètres Cette direction a pour objectif d’automa-
tiser le processus de sélection et de configuration de la meilleure heuristique pour
un problème – une étape cruciale pour le praticien. Elle porte sur deux aspects
principaux :
– le choix de l’heuristique Habituellement, le choix de la meilleure heuristique
pour un problème est implicitement fait par le chercheur qui utilise son expérience
pour apprécier l’efficacité des différents algorithmes – e.g. pour mieux résoudre
le problème de SAT, il pourrait préférer une recherche locale plutôt qu’une ap-
proche évolutionniste. 4 Cependant, ces décisions peuvent être partiellement au-
tomatisées ; de plus, il est possible d’alterner entre plusieurs heuristiques durant
le processus d’optimisation. Un exemple représentatif est la classe d’algorithmes
hyper-heuristics qui sont des heuristiques pour choisir des heuristiques. 5
– le choix des paramètres Aujourd’hui, une technique assez commune consiste à
utiliser des “mécanismes réactifs” pour adapter automatiquement les valeurs des
paramètres durant le processus de recherche. Le terme “mécanisme réactif” fait
référence à une boucle rétroactive qui modifie un paramètre selon l’état actuel
de la recherche, d’une manière “en ligne”. Reactive Tabu Search [Battiti and Tec-
chiolli, 1994] est une métaheuristique développée autour de ce type de concepts ;
4. Une raison pour cela pourrait être le fait que, les algorithmes évolutionnistes n’ont pas atteint des
performances records dans le passé [Hoos and Stützle, 2004, p. 105].
5. Plus de 100 références sont disponibles, en date d’août 2009, dans G. Ochoa’s Bibliography of Hyper-
heuristics and Related Approaches, voir [Link]/~gxo/[Link]
9
Chapitre 1. Introduction
cependant, d’autres algorithmes peuvent avoir des réactions sur le voisinage, sur le
programme de recuit, ou sur la fonction d’évaluation – voir Chapitres 2–5 de [Bat-
titi et al., 2008]. Le paramétrage automatique a des implications avec les autres
directions de recherche ci-dessus, car un changement de paramètre peut déclen-
cher une transformation complète d’algorithme. Avec un tel changement, on peut
transformer un Recuit Simulé en Descente Pure ou en algorithme de Metropo-
lis ; les opérateurs d’algorithmes génétiques peuvent être aussi choisis de cette
façon [Maturana, 2009].
La première piste de recherche est entièrement abordée dans le Chapitre 3 dans lequel
nous présentons une nouvelle hypothèse de clusterisation pour la coloration de graphe :
les configurations de qualité tendent à se trouver relativement proches les unes des autres,
groupées dans des sphères de diamètre fixe. Bien qu’il soit difficile de prouver théorique-
ment une telle hypothèse, nous la soutenons avec des preuves empiriques issues d’expéri-
mentations numériques. On devrait également se rendre compte que d’autres hypothèses
peuvent être facilement rejetées pour la coloration de graphe. Par exemple, les hypothèses
de type “massif central” ou “grande vallée” [Boese et al., 1994] supposent que les configu-
rations de qualité soient toutes proches de la solution optimale. Cette conjecture semble
valide pour le voyageur de commerce, mais, pour la coloration de graphe, nous avons ob-
servé que la qualité n’est pas corrélée avec la distance jusqu’à la solution. En fait, une
difficulté spécifique au problème de coloration vient du fait que la plupart des solutions
“presque optimales” n’ont aucun optimum global dans leur proximité. Nous avons cou-
ramment rencontré des instances difficiles qui admettent plusieurs solutions globales très
différentes les unes des autres ; il n’y a pas nécessairement de “massif central” dans la
coloration pour les instances difficiles.
La deuxième direction de recherche concerne les deux nouvelles fonctions d’évaluation
introduites au Chapitre 2. Bien que la première fonction soit spécifiée avant d’initialiser
l’exploration, la seconde est construite par le processus de recherche en fonction de cer-
taines informations apprises (le nombre de changements de couleurs de chaque variable).
L’idée est de donner une importance plus grande aux variables qui changent très souvent
d’état (e.g. les sommets qui changent souvent de couleur), afin d’encourager le processus
de recherche à fixer leurs valeurs, et ainsi à déclencher plus de diversification – les variables
restées fixes plus longtemps dans le passé sont encouragées à changer plus souvent dans la
suite.
Le troisième aspect est abordé partiellement par l’algorithme TS–Int de la Section
4.3, un algorithme qui essaie de trouver une solution à partir d’une localisation approxi-
mative. Nous avons empiriquement observé que TS–Int peut systématiquement atteindre
l’optimum global, s’il est situé à moins d’une certaine distance d’une coloration fournie
initialement. En fait, TS–Int explore un périmètre limité autour de plusieurs optima locaux
distants, fournis par un algorithme de diversification TS–Div : il est très probable que la
solution se trouve dans la proximité d’un de ces points.
La dernière approche de recherche est également évoquée dans cette thèse, dans des
contextes différents. Deux exemples sont : (i) la durée réactive Tabou présentée dans la
Section 2.4 et (ii) la dispersion réactive de l’algorithme évolutionniste Evo–Div (Section
10
1.1 Problèmes difficiles et algorithmes heuristiques
11
Chapitre 1. Introduction
Figure 1.1 – Exemple d’un enregistrement à gros grains du chemin d’exploration d’une
recherche locale. Le nombre de sphères est beaucoup plus petit que le nombre total de
points de l’espace de recherche visités. Cet enregistrement nécessite seulement un calcul
de distance par itération.
12
1.2 Coloration de graphe – plateforme d’évaluation expérimentale
nombre chromatique ne peut même pas être approximé en temps polynômial dans un
facteur constant par rapport à l’optimum (sauf si P = N P !). Une preuve pour un facteur
de 2 est donnée depuis [Garey et al., 1979, Théorème 6.11], mais de nouveaux résultats
sur d’autres facteurs sont également disponibles [Lund and Yannakakis, 1994; Bellare et
al., 1998].
La littérature sur la coloration de graphe est très vaste, et ainsi, nous insistons ici
uniquement sur les publications ayant de forts rapports avec cette thèse. En effet, pendant
les cinq dernières années, un nombre considérable de monographies, d’articles de synthèse
et de numéros spéciaux ont été publiés dans des journaux majeurs du domaine [Galinier
and Hertz, 2006; Chiarandini et al., 2007; Malaguti and Toth, in press; Johnson et al.,
2008] avec des références à des centaines de publications – on peut dire, sans exagérer, des
milliers de publications. 6 De plus, pendant la dernière décennie, j’ai relevé au moins sept
thèses ayant une partie majeure consacrée à la coloration heuristique de graphe [Galinier,
1999; Dorne, 1998; Blöchliger, 2005; Zufferey, 2002; Chiarandini, 2005; Devarenne, 2007;
Weinberg, 2004].
13
Chapitre 1. Introduction
14
1.2 Coloration de graphe – plateforme d’évaluation expérimentale
de temps il fallait interdire un mouvement après son exécution [Dorne and Hao, 1998b;
Dorne and Hao, 1998a; Galinier and Hao, 1999; Blöchliger and Zufferey, 2008; Devarenne
et al., 2006]. La chronologie des développements de Tabucol est présentée plus en détail
dans un article de synthèse [Galinier and Hertz, 2006] ; voir également la Section 2.2.
Des progrès essentiels dans la coloration ont été réalisés grâce aux premiers modèles de
croisements fondés sur des groupes (classes), au lieu des couleurs [Dorne and Hao, 1998a;
Galinier and Hao, 1999]. Ces croisements ont permis d’améliorer les meilleurs résultats
pour plusieurs graphes difficiles de l’époque. Depuis leur intégration dans les algorithmes
mémétiques (méthodes évolutionnistes incorporant une recherche locale), les algorithmes à
base de populations sont considérés comme une des meilleures approches pour la coloration
de graphe.
Notons toutefois que, très récemment, deux algorithmes de recherche locale moins
traditionnels ont été très compétitifs [Hertz et al., 2008; Blöchliger and Zufferey, 2008].
Ils ont introduit des structures plus avancées d’espace de recherche et de voisinage, ainsi
qu’un codage sous forme de colorations légales partielles, avec un réglage réactif de la
liste Tabou. Il est utile de mentionner aussi un article plus ancien [Morgenstern, 1996] qui
a joué un rôle important dans la communauté de coloration pour plusieurs raisons. Cet
article a présenté de nombreuses idées, certaines utilisées jusqu’à aujourd’hui ; de plus, il
a aussi introduit plusieurs algorithmes et les résultats globaux – la plupart d’entre eux
récapitulés à la page 357 [Morgenstern, 1996] – constituent toujours un point de référence
pour d’autres algorithmes.
Concernant l’évaluation expérimentale des algorithmes, le deuxième challenge DI-
MACS [Johnson and Trick, 1996] a rassemblé un grand ensemble de graphes qui est
devenu un jeu de tests standard pour les algorithmes de colorations depuis 1996. Ce
challenge, ainsi que d’autres évènements internationaux récents [Johnson et al., 2002;
Johnson et al., 2008] ont intensifié la recherche dans ce domaine très concurrentiel. En
effet, cinq des meilleurs algorithmes de la littérature ont été publiés pendant les der-
niers 18 mois [Malaguti et al., 2008; Hertz et al., 2008; Blöchliger and Zufferey, 2008;
Galinier et al., 2008; Lü and Hao, 2010].
Definition 1.1. (k-coloration) : Étant donné un graphe connexe GV,E et k couleurs repré-
sentées par des nombres {1, 2, . . . , k}, décider s’il existe une k-coloration (une affectation
8. Ou aussi “minimum coloring problem”. Notons que si le graphe n’est pas connexe, le problème revient
à déterminer le nombre chromatique maximum d’une composante connexe.
15
Chapitre 1. Introduction
de ces k couleurs aux sommets) sans conflit, i.e. sans arête avec les deux extrémités de la
même couleur.
Nous disons que C i est la classe i de couleurs, induite par la coloration C, i.e. l’ensemble
de sommets ayant la couleur i dans C. La coloration C est une coloration légale ou sans
conflit (une solution) si et seulement si aucune classe de couleur de C ne contient des
sommets adjacents. Cette définition à base de partitions est particulièrement utile pour
éviter des problèmes de symétrie résultant du codage classique à base de couleurs. Ainsi,
la représentation à base de partitions est employée dans plusieurs parties de la thèse, e.g.
pour définir une distance pertinente entre les colorations (voir Chapitre 6) ou pour définir
l’opérateur de croisement dans l’approche évolutionniste (Section 5.3).
Definition 1.4. Conflits Étant donnée une k-coloration C, l’ensemble des conflits
CE(C) définit les arêtes en conflit, i.e. CE(C) = {{i, j} ∈ E : C(i) = C(j)}. L’ensemble
de sommets en conflit induits par C est CV (C) = {i ∈ V : ∃j ∈ V tel que {i, j} ∈ CE}.
S’il n’y pas de risque de confusion, il est possible d’omettre l’argument (C) et de noter
CE et CV l’ensemble des arêtes en conflit et, respectivement, des sommets en conflit.
16
1.2 Coloration de graphe – plateforme d’évaluation expérimentale
17
Chapitre 1. Introduction
Le Tableau 1.1 montre des instances DIMACS de k-coloration qui ont été résolues
facilement par toutes nos heuristiques ; une solution a toujours été atteinte dans un temps
restreint (secondes ou quelques minutes). Plusieurs d’autres algorithmes ont trouvé des
colorations légales avec le même nombre de couleurs k ∗ , mais il n’y a aucune mention
d’une coloration légale avec moins de couleurs – i.e. en utilisant k ∗ − 1 couleurs, l’instance
devient probablement unSAT, ou incoloriable. Dans ce qui suit, nous nous restreignons aux
cas restants, considérés dans la littérature comme des instances difficiles.
G k∗ G k∗ G k∗ G k∗
dsjc125.1 5 r125.1 5 le450.5a 5 f lat300.20 20
dsjc125.5 17 r125.5 36 le450.5b 5 f lat300.26 26
dsjc125.9 44 r125.1c 46 le450.5c 5 f lat1000.50 50
dsjc250.1 8 r250.1 8 le450.5d 5 f lat1000.60 60
dsjc250.5 28 r250.1c 64 le450.15a 15 school1 14
dsjc250.9 72 r1000.1 20 le450.15b 15 [Link] 14
dsjr500.1 12 le450.25a 25
le450.25b 25
Table 1.1 – Bornes supérieures DIMACS faciles. D’autres articles rapportent exactement
les mêmes meilleures bornes supérieures k ∗ pour ces 27 graphes.
18
1.2 Coloration de graphe – plateforme d’évaluation expérimentale
Rappelons que le problème général de coloration est résolu par une série de problèmes
de k-coloration. Pour chaque graphe G, tous les algorithmes ont rapporté les résultats sous
la forme (G, k) – e.g. indiquant le problème le plus difficile de k-coloration résolu (le plus
petit k). La difficulté de colorier un graphe est strictement corrélée avec la valeur de k.
Passer d’un résultat de k à un résultat de k − 1 n’est pas similaire à décrémenter le nombre
de contraintes violées dans un problème de satisfaction de contrainte min-conflits, i.e. une
couleur en moins n’est pas équivalent avec une contrainte violée en moins. Dans notre cas,
pour résoudre l’instance avec “une couleur en moins”, il faut réduire plusieurs contraintes
violées (conflits). Par exemple, un algorithme qui résout une instance (G, k) avec un taux
de succès de 100%, pourrait être incapable de trouver une (k − 1)-coloration avec moins
d’une dizaine de conflits (cette situation arrive souvent pour les graphes f lat).
Pour ces raisons, dans la section bornes et instances faciles ci-dessus, nous ne parlons
pas de “graphes faciles”; on parle de graphes faciles uniquement quand un k associé est
implicitement référé. Tous les articles de coloration, que nous connaissons, ont toujours
rapporté des résultats sous la forme (G, k), comme une liste d’instances résolues. Dans un
certain sens, comparer des algorithmes de coloration uniquement de cette manière peut
être insuffisant, e.g. si deux algorithmes A1 et A2 ne trouvent pas de solution avec k
couleurs, on ne voit pas de différence si A1 atteint 1 conflit et A2 n’atteint jamais moins
d’une dizaine de conflits.
19
Chapitre 1. Introduction
20
1.2 Coloration de graphe – plateforme d’évaluation expérimentale
Les résultats rapportés par les articles ci-dessus sont également inclus dans une
présentation en ligne des meilleures bornes supérieures pour la coloration de graphe
([Link] Cette présentation a été com-
pilée au cours de cette thèse et contient 20 références, en date de septembre 2009. Une
liste complète d’algorithmes heuristiques de coloration contiendrait probablement des dou-
zaines ou des centaines de références, mais on ne peut pas faire des comparaisons avec
tous. Certains articles introduisant d’excellents développements algorithmiques ne sont
pas listés dans toutes nos comparaisons uniquement pour des raisons très pratiques :
soit ils ne sont pas focalisés sur les meilleurs résultats pratiques, soit ils ont été ac-
ceptés pour publication pendant les derniers mois de cette thèse, quand ce manuscrit
était plus qu’à moitié écrit [Prestwich, 2002; Glover et al., 1996; Hamiez and Hao, 2004;
Hamiez and Hao, 2001; Lü and Hao, 2009; Bouziri et al., 2008; Fotakis et al., 2001;
Lü and Hao, 2010]. Toutefois, notons que toutes les bornes découvertes en 2009 seront
indiquées entre crochets dans tous les tableaux de comparaison de résultats (e.g. Tableaux
2.3, 4.4, 5.4).
21
Chapitre 2
Sommaire
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2 Recherche Tabou de base pour la k-coloration . . . . . . . . . . 25
2.2.1 Le voisinage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.2 Gestion de la liste Tabou . . . . . . . . . . . . . . . . . . . . . . 26
23
Chapitre 2. RCTS : Un Algorithme Tabou avec de Nouvelles Fonctions d’Évaluation et
une Liste Tabou Réactive
2.2.3 Spécification de l’algorithme Tabou de base . . . . . . . . . . . . 27
2.3 Nouvelles fonctions d’évaluation “bien informées” . . . . . . . . 28
2.3.1 Fonction d’évaluation basée sur le degré . . . . . . . . . . . . . . 28
2.3.2 Des informations dynamiques pour définir d’autres fonctions
d’évaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3.3 Idées similaires dans la littérature et remarques sur la complexité 30
2.4 Une technique réactive pour gérer la liste Tabou . . . . . . . . 31
2.5 Résultats et discussions . . . . . . . . . . . . . . . . . . . . . . . . 32
2.5.1 Paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.5.2 Influence des fonctions d’évaluation . . . . . . . . . . . . . . . . . 33
2.5.3 Influence de la liste Tabou réactive . . . . . . . . . . . . . . . . . 37
2.5.4 Résultats complets sur toutes les instances difficiles . . . . . . . . 37
2.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.1 Introduction
Plusieurs études antérieures sur la coloration montrent que, parmi les metaheuristiques
classiques, les algorithmes fondés sur la recherche Tabou (couramment abrégée TS – Tabou
Search) sont parmi les plus simples et les plus efficaces pour colorier des graphes difficiles
de grande taille. Notons que plusieurs algorithmes hybrides plus performants [Fleurent
and Ferland, 1996a; Dorne and Hao, 1998a; Galinier and Hao, 1999; Galinier et al., 2008;
Malaguti et al., 2008; Blöchliger and Zufferey, 2008; Hertz et al., 2008] emploient également
un algorithme Tabou comme procédure d’amélioration locale. Nous observons que les
algorithmes Tabou existants pour la coloration n’emploient pratiquement pas de technique
sophistiquée. Notre premier objectif consiste à améliorer la performance d’un algorithme
de base en rendant certaines composantes plus efficaces, tout en conservant la simplicité
de l’algorithme.
Dans ce chapitre, nous proposons des améliorations pour deux composantes majeures :
la fonction d’évaluation et la gestion de la liste Tabou. En effet, la fonction d’évaluation
est essentielle parce qu’elle définit (avec le voisinage) le paysage de recherche et guide le
processus d’optimisation. La fonction d’évaluation classique pour la k-coloration compte
simplement le nombre de conflits, i.e. le nombre d’arêtes avec les deux extrémités de la
même couleur. L’objectif de l’algorithme Tabou est de se déplacer pas à pas vers la valeur
minimale de cette fonction, pour essayer de trouver une k-coloration sans conflit. Cepen-
dant, cette fonction d’évaluation ne peut pas différencier de nombreuses k-colorations avec
le même nombre de conflits, mais avec un potentiel différent pour conduire à une solution.
Pour cette raison, nous étudions deux nouvelles fonctions d’évaluation qui emploient
des informations supplémentaires. L’objectif de la première fonction est d’intégrer des in-
formations structurales relatives aux degrés des sommets en conflit. La seconde utilise des
informations apprises au cours du processus de recherche : les fréquences des changements
de couleur. De plus, ce chapitre introduit une procédure réactive simple et efficace pour
améliorer la gestion de la liste Tabou. Nous montrons expérimentalement que, tout en
24
2.2 Recherche Tabou de base pour la k-coloration
2.2.1 Le voisinage
L’espace de recherche Ω d’un problème de k-coloration (GV,E , k) comprend toutes les
colorations possibles de G ; comme les configurations sont codées sous forme de vecteurs
de couleurs, on obtient |Ω| = |V |k . Une fonction simple de voisinage N : Ω → 2Ω − {∅}
peut être définie comme suit. Étant donnée une k-coloration C, une k-coloration voisine
C 0 peut être obtenue en changeant simplement la couleur c(i) d’un sommet en conflit i
avec une nouvelle couleur c0 (i). La transition de C à C 0 représente un mouvement (un pas)
dans un processus de recherche, formellement noté par le couple < i, c0 (i) >.
25
Chapitre 2. RCTS : Un Algorithme Tabou avec de Nouvelles Fonctions d’Évaluation et
une Liste Tabou Réactive
Ce voisinage se concentre sur les |CV | sommets en conflit, afin d’aider le processus de
recherche à se focaliser sur des mouvements influents, en évitant les mouvements moins
pertinents. Habituellement, il n’y a pas besoin de changer la couleur d’un sommet non-
conflictuel. La taille de notre voisinage est |N (C)| = (k − 1)|CV |, une taille considérable-
ment plus petite que la taille d’un voisinage dans lequel tout sommet pourrait changer sa
couleur (i.e. (k − 1)|V |).
Pour choisir rapidement la meilleure coloration dans N (C), nous utilisons un tableau
γ avec |V | lignes et k colonnes : un élément γi,j = γi,c0 (i) indique le nombre de conflits que
le sommet i aurait si la couleur j = c0 (i) lui avait été assignée. La différence du nombre
de conflits qui serait induite par un mouvement < i, c0 (i) > est γi,c0 (i) − γi,c(i) . Comme ce
voisinage considère seulement des sommets en conflit, le meilleur mouvement est recherché
en passant par tous les éléments γi,j avec i ∈ CV (i.e. (k − 1)|CV | éléments de γ) ; on peut
dire que la couleur c0 (i) qui sera affectée à i vérifie c0 (i) ∈ arg minj (γi,j − γi,c(i) ).
Après avoir effectué un mouvement < i, c0 (i) >, γ peut être mis à jour en O(|V |)
opérations : il faut modifier uniquement les colonnes c(i) et c0 (i). Cette technique dyna-
mique a été d’abord utilisée dans [Fleurent and Ferland, 1996a] et elle s’avère indispensable
pour une investigation rapide du voisinage complet. Un exposé plus général concernant les
techniques et les structures de données incrémentales est disponible dans [Galinier, 1999,
§6.2]
La liste Tabou est généralement vue comme une structure “first-in-first-out” (une file)
qui contient des configurations ou des mouvements récents. Dans notre contexte, il est
plus pratique de l’implémenter comme un tableau T de dimension |V | × k , où chaque
élément correspond à un mouvement possible. Chaque fois qu’un mouvement < i, c0 (i) >
est exécuté, le sommet i reçoit une nouvelle couleur c0 (i) et l’ancienne couleur de i – i.e.
c(i) – devient interdite (Tabou) pour les prochaines T` itérations (la durée Tabou est Tl ).
Dans la pratique, chaque élément de T indique le nombre courant d’itération plus la durée
Tabou T` . Par conséquent, afin de vérifier si un mouvement < i, c0 (i) > est Tabou ou non,
Ti,c0 (i) est comparé avec l’itération courante.
Dans notre version de recherche Tabou, la longueur classique de la liste Tabou est
T` = α · |CE| + random (0, A), où α et A sont des paramètres calibrés dans des publications
précédentes (voir aussi la Section 2.5.1) ; la fonction random retourne un entier aléatoire
entre 0 et A. Dans ce contexte, random(0, A) représente une longueur Tabou générale (fixe
par rapport à la qualité), et α · |CE| a le rôle d’interdire plus longtemps les mouvements
associés à des configurations de qualité inférieure. Nous introduisons plus tard (Section
2.4) un composant réactif pour ajuster T` en fonction de la fluctuation récente du nombre
de conflits.
26
2.2 Recherche Tabou de base pour la k-coloration
L’algorithme 2.1 décrit la procédure Tabou de k-coloration avec toutes les composantes
présentées ci-dessus. Pour une instance de k-coloration donnée (G, k), notre algorithme
Tabou génère d’abord une première k-coloration aléatoire C pour lancer la recherche.
Ensuite, les étapes principales d’une itération sont : (i) la sélection du meilleur mouvement
acceptable < i, c0 (i) > dans le voisinage, (ii) la paire < i, c(i) > devient Tabou, (iii)
l’exécution du mouvement c(i) = c0 (i) et (iv) la mise à jour de γ. Le processus s’arrête
quand une coloration légale est trouvée ou quand une limite de temps est atteinte.
27
Chapitre 2. RCTS : Un Algorithme Tabou avec de Nouvelles Fonctions d’Évaluation et
une Liste Tabou Réactive
Definition 2.1. (Degré de conflit des sommets) Soit i un sommet, δi son degré, et C
une coloration. Nous définissons CVi = {j ∈ V |{i, j} ∈ CE(C)} et nous appelons |CV i|
δi le
degré de conflit du sommet i pour la configuration C.
Il est facile de voir que 0 ≤ |CVi | ≤ δi ∀i ∈ V ; la valeur minimum |CVi | = 0 est atteinte
pour des sommets sans conflit, et la valeur maximum |CVi | = δi indique que le sommet
i est en conflit avec tous
P ses voisins. D’ailleurs, la relation suivante est valide pour toute
coloration : 2|CE| = i∈V |CVi | (voir aussi Définition 1.4, Section 1.2.2).
Pour motiver l’introduction de cette fonction, nous considérons l’exemple de la Figure
2.1 qui montre deux 3-colorations C1 et C2 pour un graphe très simple. Les arêtes en
28
2.3 Nouvelles fonctions d’évaluation “bien informées”
Figure 2.1 – Deux 3-colorations C1 et C2 avec un conflit. Le conflit est indiqué avec une
ligne plus épaisse dans les deux cas ; il est plus facile de résoudre le conflit gris (C1 , à
gauche) que de résoudre le noir (C2 , à droite) alors que f (C1 ) = f (C2 ) = 1.
conflit sont {a, b} pour C1 et, respectivement, {a, c} pour C2 . Par conséquent, |CE (C1 ) | =
|CE (C2 ) | = 1 et les deux configurations sont ainsi équivalentes pour f . Cependant, C1
est préférable à C2 .
En effet, comme le degré de b est petit, on peut assigner à b une couleur non utilisée
par ses voisins (i.e. noir ou blanc) pour résoudre le conflit {a, b} sur C1 . Cela peut être
accompli dans une seule étape sans générer d’autres conflits. Mais il est plus difficile de
résoudre le conflit {a, c} de C2 car n’importe quel changement de couleur sur le sommet
a ou c peut perturber ses nombreux voisins. Intuitivement, plus un sommet a des voisins,
plus il est difficile de changer sa couleur sans perturber le reste de la configuration.
Plus généralement, pour chaque sommet en conflit, nous pouvons utiliser son degré
pour définir un terme de pénalité : les arêtes en conflits doivent peser plus lourdement
dans la fonction d’évaluation si les deux sommets de l’arête ont un degré plus élevé. Afin
de prendre en considération tous les sommets en conflit, nous définissons l’heuristique
suivante h1 pour associer une pénalité à chaque k-coloration C :
1 X |CVi |
h1 (C) = (2.2)
2|E| δi
i∈CV
Dans ce contexte, nous voyons que h1 (C) indique la somme des degrés de conflits de
tous les sommets de C. Notre première fonction d’évaluation basée sur les degrés peut
maintenant être définie comme suit :
29
Chapitre 2. RCTS : Un Algorithme Tabou avec de Nouvelles Fonctions d’Évaluation et
une Liste Tabou Réactive
Certains détails d’implémentation pourraient être utiles ici. À chaque itération, la re-
cherche Tabou de base doit choisir aléatoirement un voisin qui minimise le nombre de
conflits. L’implémentation de ce choix aléatoire n’est pas trivial, parce qu’il est assez
inefficace de simplement collectionner et enregistrer tous les voisins pour en choisir un
finalement. Nous proposons de tirer une valeur aléatoire rC 0 dans l’intervalle [0, 1] et de
l’affecter au voisin C 0 dès que C 0 est découvert ; à la fin, le C 0 avec la plus grande valeur
rC 0 est sélectionné. Cette procédure n’enregistre pas tous les voisins et le choix aléatoire
résultant n’est pas biaisé. Vers la fin de la thèse, nous avons réalisé que de meilleurs résul-
tats expérimentaux peuvent être obtenus en couplant les nouvelles fonctions d’évaluation
dans ce procédé. Soit hmin et hmax la valeur minimum et maximum atteinte par la fonc-
tion h. De meilleurs résultats peuvent être réalisés si on tire la valeur rC 0 dans l’intervalle
h(C 0 )−hmin
h i
0, hmax −hmin .
En principe, le degré δi (de fe1 ) est remplacé par un coefficient de fréquence dans cette
fonction. En conséquent, étant données deux colorations avec le même nombre de conflits,
fe2 préfère celle où les sommets en conflit ont de plus petites fréquences de changement
de couleur – cela implique qu’elle préfére résoudre en priorité les sommets de plus haute
fréquence de changement. La nouvelle fonction encourage le processus de recherche à ré-
soudre prioritairement les conflits de ces sommets, avant ceux avec de petites fréquences
de changement de couleur. En pratique, on peut dire que les sommets avec des hautes
fréquences de changement de couleur sont considérés plus critiques. Nous avons observé
que fe2 conduit à des changements des couleurs plus fréquents sur les sommets qui étaient
“moins modifiés” pendant la première étape ; elle a un effet implicite de diversification.
30
2.4 Une technique réactive pour gérer la liste Tabou
dépendants” (i.e. de petit degré) dans une dernière étape, après la coloration des autres
sommets. L’algorithme Impasse [Morgenstern, 1996] s’appuie sur un codage différent (co-
lorations partielles), mais il prévoit également de colorier d’abord les sommets de degré
élevé, laissant les sommets de petit degré dans une classe non coloriée. Cette idée a été
également reprise dans [Malaguti et al., 2008].
Concernant la fonction fe2 , dans [Devarenne et al., 2006], les sommets “fréquemment”
changés pendant N/2 itérations” sont également considérés pour obtenir de la diversité. Des
fonctions d’évaluation complètement différentes sont aussi proposées dans la littérature,
i.e. [JohnsonP et al., 1991
]
P ont défini dans leur algorithme de recuit simulé la fonction
fˆdsjc = − ki=1 |Ci | + ki=1 2|Ci ||CEi |, où Ci est l’ensemble de sommets ayant la couleur
i et CEi est l’ensemble de conflits de la couleur i.
1
où hi est la pénalité/poids associé au sommet i, i.e. hi = pour la première fonction,
2|E|·δi
X
1
ou hi = f req(i) pour la deuxième. En conséquent, comme f (C) = |CE| = 1, il
{i,j}∈CE
est possible de calculer la valeur d’une nouvelle fonction fˆ(C) en faisant la somme de
1 − (hi + hj ) pour chaque conflit {i, j}. Avant de lancer la recherche, nous construisons
un tableau E tel que fˆ = {i,j}∈CE Eij . La seule différence au niveau du calcul entre les
P
trois fonctions d’évaluation est la valeur initiale de E. Ainsi, Eij est toujours égale à 1
1 1
pour la fonction classique, mais Eij peut être également définie par 1 − f req(I) − f req(j)
pour calculer fe2 . Concernant la première fonction, il est important de noter qu’elle peut
être également écrite comme :
X 1 1
fe1 (C) = 1− − (2.5)
2|E|δi 2|E|δj
{i,j}∈CE(C)
31
Chapitre 2. RCTS : Un Algorithme Tabou avec de Nouvelles Fonctions d’Évaluation et
une Liste Tabou Réactive
quelles deux configurations peuvent être reliées par des mouvements à l’intérieur du pla-
teau. Une liste Tabou de longueur inférieure à n n’est pas suffisante pour couper un cycle
de longueur n : C1 → C2 · · · → Cn → C1 . Notre longueur classique Tabou est bornée (i.e.
T` est toujours inférieure à α · |CE| + A) et les tests numériques confirment que cela peut
être insuffisant pour éviter certains cycles sur des grands plateaux.
Pour surmonter cette difficulté, nous considérons une liste Tabou réactive : quand
le nombre de conflits reste constant pendant un nombre donné d’itérations Mmax , nous
incrémentons la longueur de la liste Tabou pour toutes les itérations suivantes. Autrement
dit, dès qu’il y a Mmax transitions consécutives C1 → C2 · · · → CMmax tels que f (C1 ) =
f (C2 ) = · · · = f (CMmax ), la liste Tabou devient T` + 1 pour les prochaines itérations. Si le
nombre de conflits reste toujours constant pendant encore Mmax itérations, la liste Tabou
devient T` + 2 ; ensuite, après encore Mmax itérations, elle devient T` + 3, etc. La durée
Tabou est continuellement incrémentée tant qu’il n’y a pas de variation dans le nombre
de conflits. Comme la liste est remise à la valeur originale dès que le nombre de conflits
change, nous garantissons que, tôt ou tard, la liste croı̂t jusqu’à une valeur qui peut couper
un cycle de n’importe quelle longueur n.
Notons que l’utilisation d’une longue liste Tabou pendant tout le processus de recherche
aurait eu un effet très négatif ; en dehors des grands plateaux, cela pourrait encourager
l’algorithme à abandonner trop tôt des régions prometteuses. Dans notre cas, l’algorithme
apprend de sa propre évolution, et il utilise une liste Tabou plus grande seulement quand
cela est nécessaire. Ce mécanisme simple a permis à l’algorithme de se débloquer dans des
situations critiques sans affecter la recherche en dehors des plateaux. En conclusion, notre
durée Tabou peut être exprimée par la formule :
Mcst
T` = α|CE| + random(0, A) + , (2.6)
Mmax
où Mcst est le nombre des dernières itérations avec un nombre de conflits constant.
Pour rapporter la contribution actuelle à des travaux de recherche antérieurs, cette
stratégie Tabou s’inscrit dans le cadre d’algorithmes “Reactive Tabou Search” [Battiti et
al., 2008]. D’autres stratégies réactives basées sur la détection de bouclage ont été in-
dépendamment étudiées dans d’autres algorithmes récents de coloration [Blöchliger and
Zufferey, 2008; Devarenne et al., 2006]. L’idée la plus similaire a certainement été présentée
dans [Blöchliger and Zufferey, 2008] : le processus de recherche est considéré “bloqué” si
la fluctuation de la fonction objectif reste en dessous d’un certain seuil pour une longue
période. Cette méthode nécessite trois paramètres qui sont réglés dans une phase spéciale
de calibrage. Les auteurs de [Devarenne et al., 2006] considèrent des idées différentes et
ils se concentrent sur l’identification des sommets causant des boucles. De détails sup-
plémentaires sur l’influence pratique de notre réglage réactif sont donnés dans la partie
expérimentale (Section 2.5.3).
32
2.5 Résultats et discussions
principal est d’évaluer l’influence des nouvelles fonctions d’évaluation, mais aussi l’effet de
la liste Tabou réactive.
L’ensemble complet des graphes DIMACS a été présenté dans la Section 1.2.3 (p.
17). Nous rappelons que les algorithmes de coloration traitent des instances (G, k), où
k est donné pour chaque graphe. Le niveau de difficulté pour trouver une k-coloration
légale peut varier de trivial à très difficile. D’abord, notons que RCTS a pu résoudre
assez facilement (i.e. avec un taux de réussite de 100% en quelques minutes au maximum)
toutes les instances faciles de la section [Link], ainsi que l’instance (r1000.1c, k = 98).
Dans ce qui suit, nous nous concentrons seulement sur le reste des instances, celles qui
sont réellement difficiles pour RCTS.
2.5.1 Paramètres
Rappelons que l’algorithme RCTS nécessite seulement trois paramètres : A, α et Mmax .
Les deux premiers sont hérités des algorithmes Tabou précédents, et le dernier est employé
par la nouvelle liste Tabou réactive (Section 2.4) :
– A et α : ils sont utilisés pour calculer la longueur de la liste Tabou (T` = α · |CE| +
random(0, A), voir la Section 2.2.2). Nous affectons à ces paramètres des valeurs déjà
présentées dans la littérature [Galinier and Hao, 1999; Dorne and Hao, 1998b] :
A = 10 et α = 0, 6. Nos propres tests expérimentaux de calibrage confirment que
cette combinaison constitue un bon choix ;
– Mmax : après Mmax itérations avec nombre de conflits |CE| constant, le processus de
recherche est considéré coincé, et ainsi, la composante réactive est activée (cf. Sec-
tion 2.4). Dans nos tests expérimentaux, Mmax est toujours fixé à 1000 pour toutes
les instances, mais ce choix est robuste : il existe de nombreuses autres valeurs Mmax
qui conduisent aux mêmes résultats. Nous avons empiriquement observé que, si |CE|
reste constant pour 1000 itérations, |CE| reste constant indéfiniment (avec la liste
Tabou classique). Si une valeur plus grande Mmax est utilisée, la seule différence est
que la réaction est moins prompte. Des valeurs Mmax plus petites peuvent déclen-
cher des réactions plus rapidement que nécessaire, influençant alors le processus de
recherche sans raison.
33
Chapitre 2. RCTS : Un Algorithme Tabou avec de Nouvelles Fonctions d’Évaluation et
une Liste Tabou Réactive
prouve que fe1 − RCTS reste le plus souvent à un nombre inférieur de conflits. Ce type de
profil est observé sur plusieurs graphes, fournissant un argument préliminaire que fe1 peut
mener la recherche vers des configurations de meilleure qualité.
80
60
Nr. de conflits
4020
0
Figure 2.2 – Évolution typique du nombre de conflits (profile d’exécution) avec f (en
ligne pointillée) et fe1 (en ligne continue) de l’itération 200 jusqu’à l’itération 25.000. fe1
guide la recherche vers de meilleures colorations.
Le Tableau 2.1 confirme cette remarque : il montre le nombre moyen de conflits après
1.000.000 d’itérations avec chaque fonction sur plusieurs graphes représentatifs de diffé-
rentes familles. Les différences entre ces moyennes ont été confirmées par un test statistique.
Nous avons considéré l’hypothèse nulle selon laquelle la moyenne du nombre de conflits
obtenus avec fe1 (ou fe2 respectivement) est égale à la moyenne obtenue avec f . Utilisant
un niveau de confiance de α = 0.1%, cette hypothèse a été rejetée dans la plupart des
cas, confirmant que les différences de moyenne ne sont pas dues au hasard – voir les deux
dernières colonnes du Tableau 2.1.
Le Tableau 2.1 montre que le nombre moyen de conflits est statistiquement plus petit
pour fe1 que pour fec ; en fait, la différence est statistiquement significative pour tous les
graphes sauf pour f lat300 28. Dans le meilleur des cas, la moyenne du nombre de conflits
pour fe1 -RCTS peut être égale à la moitié de la moyenne pour f -RCTS. La deuxième
fonction fe2 montre également une amélioration sur deux-tiers des instances, mais avec une
plus petite amplitude.
Pour le problème de coloration, il n’y a aucune garantie théorique que la probabilité
d’atteindre une solution optimale soit strictement corrélée avec la qualité moyenne des
solutions visitées tout le long de la recherche. Cependant, particulièrement pour les re-
cherches locales, presque tous les algorithmes essayent toujours de guider le processus vers
des configurations de plus grande qualité (i.e. avec moins de conflits).
34
2.5 Résultats et discussions
Table 2.1 – Moyenne du nombre de conflits après 1.000.000 itérations avec chaque fonc-
tion. En général, les fonctions modifiées, en particulier fe1 , mènent la recherche vers des
colorations avec (statistiquement) moins de conflits.
Nous sommes convaincus que l’intérêt d’une fonction d’évaluation plus discriminante
n’est pas limitée à l’algorithme Tabou ou à un certain réglage de la liste Tabou. Nous avons
donc effectué un autre test expérimental avec un algorithme de Descente Pure (DP) sans
paramètres, plus neutre. Techniquement, l’algorithme DP est la même recherche Tabou
de la Section 2.2, mais avec une liste Tabou toujours vide (i.e. T` = 0). Cette descente
pure est initialisée par une coloration aléatoire et elle est guidée seulement par la fonction
d’évaluation : DP choisit itérativement le meilleur voisin selon cette fonction. Un nombre
très petit d’itérations (i.e. moins que quelques milliers) est généralement suffisant pour
faire converger la recherche dans des optima locaux. Comme une étape d’apprentissage
de quelques milliers d’itérations serait insuffisante pour fe2 , ce test ne peut être effectué
qu’avec fe1 et f .
Nous avons lancé 1000 descentes indépendantes (chacune avec une coloration initiale
différente) et nous avons comparé le nombre de conflits des k-colorations finalement ob-
tenues avec fe1 et f . La Figure 2.3 montre les distributions de ces nombres de conflit (i.e.
l’axe x indique le nombre de conflits et l’axe y indique la fréquence de ce nombre – le
nombre de descentes qui sont arrivées à ce nombre) : la performance avec fe1 est nette-
ment supérieure et même la plus mauvaise descente avec fe1 est souvent meilleure que la
meilleure avec f . Nous avons observé ces distributions pour plusieurs graphes de toutes
les familles. La nouvelle fonction permet à cette descente rudimentaire d’atteindre une
solution pour G = le450 25a et k = 25, tandis que la même descente avec f ne trouve
jamais de coloration avec moins de 10 conflits.
35
Chapitre 2. RCTS : Un Algorithme Tabou avec de Nouvelles Fonctions d’Évaluation et
une Liste Tabou Réactive
Nr. éxecutions
G= dsjc250.5 , k= 28 G= dsjc500.5 , k= 49
0 150
0 100
G= dsjc1000.1 , k= 20 G= dsjc1000.5 , k= 83
150
0 150
0
150 200 250 300 350 250 300 350 400 450
Nr. de conflits Nr. de conflits
Nr. éxecutions
G= le450_25a , k= 25 G= le450_25c , k= 25
150
0 200
0 5 10 15 20 25 60 80 100 120
Nr. de conflits Nr. de conflits
Figure 2.3 – Histogrammes du nombre de conflits obtenus avec 1000 descentes pures
indépendantes, utilisant fe1 (barres simples) et f (barres hachurées). La descente pure
mène toujours à un plus petit nombre de conflits avec fe1 que avec f .
Nous avons également observé que l’influence favorable de la nouvelle fonction fe1 est
plus évidente sur certaines instances que sur d’autres. En principe, les meilleures amé-
liorations sont réalisées sur des instances difficiles de certaines classes spécifiques. Une
amélioration impressionnante est observée sur les graphes géométriques aléatoires (i.e.
dsjrX.Y et rX.Y ) pour lesquels fe1 domine fortement f sans exception – voir le Tableau
2.1 et également le Tableau 2.2 avec des résultats complets.
Cette variation de performance est due à la structure des graphes, plus exactement
à la variation de degrés de sommets. Par exemple, pour les graphes géométriques (e.g.
dsjr500.5), le degré maximum peut être d’un ordre de grandeur plus grand que le de-
gré minimum, et ainsi toute différentiation fondée sur le degré est très efficace. En effet,
l’amélioration des performances apportée par fe1 peut être classée en concordance avec la
variation des degrés, du plus haut au plus bas : 1) graphes géométriques aléatoires, 2)
graphes de Leighton, 3) graphes aléatoires, 4) graphes flat. Un cas extrême est le graphe
36
2.5 Résultats et discussions
du carré latin latin square qui est régulier (i.e. avec degré constant) ; la nouvelle fonction
d’évaluation basée sur le degré n’apporte pas de nouvelle distinction entre les sommets de
ce graphe.
37
Chapitre 2. RCTS : Un Algorithme Tabou avec de Nouvelles Fonctions d’Évaluation et
une Liste Tabou Réactive
de 10 heures (e.g. 40000 secondes dans [Malaguti et al., 2008, p.310]). Nous trouvons
également des articles rapportant plusieurs jours de calcul (e.g. [Dorne and Hao, 1998a;
Morgenstern, 1996]).
Table 2.2 – Résultats détaillés de RCTS avec un temps limite de 10 heures avec les trois
fonctions d’évaluation. fe1 - RCTS trouve de meilleures solutions (k plus petit) que f -
RCTS sur 25% de graphes et il obtient un taux de succès amélioré sur 25% des autres
instances. La différence entre fe2 - RCTS et f - RCTS est plus nette sur les grands graphes,
qui nécessitent plus de 5h de calcul.
Le Tableau 2.2 présente les résultats détaillés de RCTS sur tous les graphes DIMACS
difficiles. Les deux premières colonnes indiquent l’instance de k-coloration, i.e. le graphe
et le nombre de couleurs k. Pour chaque fonction d’évaluation, nous fournissons le taux de
réussite (colonnes 3,6,9) et l’effort moyen de calcul nécessaire pour résoudre l’instance : le
nombre moyen d’itérations en millions (colonnes 4, 7, et 10) et le temps de calcul en heures
(colonnes 5, 8, 11). Le nombre d’itérations est une mesure indépendante de la machine et
le temps est indiqué pour avoir une idée de l’ordre de grandeur ; le symbole “-” indique
38
2.6 Conclusions
2.6 Conclusions
Nous avons présenté une Recherche Tabou Renforcée de Coloration (RCTS) qui amé-
liore les algorithmes Tabou précédents avec deux nouvelles fonctions d’évaluation et avec
une liste Tabou réactive. En enrichissant la fonction d’évaluation conventionnelle f , les
nouvelles fonctions prennent en considération des informations supplémentaires relatives
à la structure du graphe (degrés de conflit des sommets) ainsi que des informations dy-
namiques acquises au cours de la recherche (la fréquence de changement de couleur). De
plus, la gestion réactive de la liste Tabou permet à l’algorithme d’éviter le bouclage ; ainsi,
il peut effectivement profiter d’un temps de calcul plus long. Nous avons montré que l’al-
gorithme résultant, en dépit de sa simplicité, est suffisant pour atteindre, à de nombreuses
reprises, les meilleurs résultats de la littérature.
Le Tableau 2.3 compare les résultats de RCTS avec les meilleurs algorithmes de la
littérature – cinq d’entre eux sont basés sur une recherche locale et six sont des algorithmes
39
Chapitre 2. RCTS : Un Algorithme Tabou avec de Nouvelles Fonctions d’Évaluation et
une Liste Tabou Réactive
Table 2.3 – Résultats du RCTS et des meilleurs algorithmes les plus performants dans
la littérature sur tous les graphes DIMACS difficiles. Les colorations trouvées par RCTS
sont publiquement disponibles à l’adresse : [Link]/pub/porumbel/
graphs/rcts/.
a. Les acronymes des algorithmes se trouvent dans la Section 1.2.4 (p. 19). Comme précisé dans cette
section, on indique entre crochets les bornes publiés au cours de la rédaction de ce manuscrit.
hybrides. Même si une comparaison détaillée est au-delà des objectifs de ce chapitre, ce
tableau de comparaison donne une vision générale indiquant une bonne performance de
RCTS sur l’ensemble des instances DIMACS.
40
Chapitre 3
Cartographie de l’Espace de
Recherche
Ce chapitre est consacré à l’analyse de l’espace de recherche : nous nous
focalisons sur la distribution spatiale des configurations de qualité. Les in-
formations apprises dans cette étape sont intégrées dans nos heuristiques
afin de leur fournir d’avantage d’information : les recherches locales du Cha-
pitre 4 peuvent s’auto-guider vers des régions non-explorées, l’algorithme
évolutionniste du Chapitre 5 utilise une population avec un écart approprié
entre les individus. En utilisant une mesure de distance entre les colorations,
nous présentons l’hypothèse de clusterisation des solutions candidates de
l’espace de recherche : les configurations de grande qualité ne sont pas dis-
tribuées aléatoirement, mais elles sont plutôt groupées en clusters, dans des
sphères de diamètre spécifique. Tout d’abord, nous fournissons des argu-
ments très intuitifs en projetant un échantillon d’optima locaux dans un
espace 3D. Puis, nous étudions formellement la distribution de la distance
entre les meilleures configurations visitées par une recherche locale pendant
une longue période : les valeurs de distance sont soit très petites (distances
à l’intérieur d’un clusters), soit très grandes (distances entre les cluster).
Ce chapitre développe des idées d’un article accepté par Computers and
Opperations Research [Porumbel et al., 2010] ; une partie de l’état de l’art
sur l’analyse d’espace provient d’un article présenté à la conférence LION
(Learning In OptimizatioN) [Porumbel et al., 2009d].
Sommaire
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.1.1 Analyse de l’espace de recherche . . . . . . . . . . . . . . . . . . 42
3.2 La recherche locale typique et la vision globale . . . . . . . . . 43
3.3 Cartographie de l’espace de recherche . . . . . . . . . . . . . . . 45
3.3.1 L’opération de cartographie . . . . . . . . . . . . . . . . . . . . . 45
41
Chapitre 3. Cartographie de l’Espace de Recherche
3.1 Introduction
3.1.1 Analyse de l’espace de recherche
Il est bien connu que l’évolution de tout algorithme heuristique est fortement influencée
par la structure de l’espace de recherche. En fait, pour concevoir une heuristique efficace,
il est essentiel d’exploiter (implicitement ou explicitement) les propriétés de l’espace de re-
cherche [Streeter and Smith, 2006]. Par exemple, plusieurs structures différentes d’optima
locaux peuvent être exemplifiées pour le problème de satisfaisabilité en logique proposi-
tionnelle (SAT) [Du and Pardalos, 2007, pp. 425–427] : optima locaux isolés, plateaux,
structures de vallées, bassins d’attraction, etc. Pour de nombreux algorithmes, la situation
la plus difficile n’est pas le minimum local classique, mais le “piège” (trap, en anglais) : le
groupement de plusieurs optima locaux dans un “puits” profond – on peut voir un “puits”
comme un trou dans la surface déterminée par la fonction objectif (“fitness surface” en
anglais). Une fois piégée dans une telle structure, une recherche locale classique va boucler
en permanence entre les minima locaux à l’intérieur du puits bien qu’elle puisse avoir les
capacités d’échapper à tout optimum local individuel.
Il existe plusieurs pistes de recherche concernant l’analyse des espaces de solutions –
voir aussi la classification de [Streeter and Smith, 2006, §2] qui est bien reliée à nos inté-
rêts. Pour illustration, dans le contexte de calcul évolutionniste, une direction de recherche
active est centrée sur des indicateurs statistiques pour estimer la difficulté du problème
– i.e. convexité, rugosité, “smoothness”, “fitness-distance correlation” [Jones and Forrest,
1995] ; on peut se référer à [Kallel et al., 2001; Merz, 2004] pour un résumé de tels indica-
teurs et de discussions connexes. D’autres types d’analyses d’espace de recherche traitent
des similitudes structurales entre les optima locaux (i.e. “backbone structures”), ou leur
distribution spatiale – comme nous le faisons dans ce chapitre.
Chaque problème d’optimisation peut avoir un nombre différent d’optima locaux
et de plateaux – chacun d’entre eux avec sa propre forme, taille, profondeur, etc.
De plus, ces optima locaux peuvent être groupés d’après des modèles spécifiques
(bassins d’attraction, vallées, puits) et ils peuvent être concentrés dans quelques ré-
gions [Merz, 2004]. On peut trouver de nombreuses études relatives à des propriétés
spécifiques pour plusieurs problèmes représentatifs : le problème SAT [Zhang, 2004;
Gerber et al., 1998], le voyageur de commerce [Stadler and Schnabl, 1992], le sac-à-dos en
0–1 [Ryan, 1995], la coloration de graphe [Hertz et al., 1994; Hamiez and Hao, 2004;
Culberson and Gent, 2001], le bi-partitionnement de graphe [Merz and Freisleben,
2000b], l’affectation quadratique [Merz and Freisleben, 2000a], l’ordonnancement de tâches
42
3.2 La recherche locale typique et la vision globale
[Reeves and Yamada, 1998; Streeter and Smith, 2006], la minimisation de croisements pour
la trace de graphes [Kuntz et al., 2004]. Les caractéristiques de l’espace de recherche (le
nombre d’optima, leur distribution, la topologie de leurs bassins d’attraction, etc.) se sont
révélées en effet assez différentes d’un problème à l’autre, et même d’une instance à l’autre
pour le même problème. Néanmoins, toutes ces études concluent que l’analyse de l’espace
peut apporter un impact très positif sur le comportement des algorithmes.
Comme nous l’avons discuté en Section 1.1.2, il est plus difficile de faire une ana-
lyse complexe “on the fly” (apprentissage en ligne) que de la faire en pré-optimisation,
avant l’étape principale de recherche. L’inconvénient de toute analyse d’optima locaux
en pré-optimisation est évident : cela exige de connaı̂tre les optima locaux en préa-
lable – la localisation des optima locaux de grande qualité est en fait l’objectif final
de la recherche principale. Avant l’étape principale d’optimisation, très peu d’informa-
tions sont habituellement disponibles sur l’espace de recherche du problème. Une ap-
proche possible serait d’utiliser de petites instances afin de localiser facilement tous les
optima locaux pour les analyser ensuite [Hertz et al., 1994]. Une autre approche très
populaire consiste à analyser le comportement des heuristiques sur des paysages de re-
cherche artificiels, e.g. le modèle NK [Kauffman and Levin, 1987; Tomassini et al., 2008;
Jones and Forrest, 1995], des problèmes “one-max” ou “long k-path” [Horn et al., 1994].
L’apprentissage au cours du processus d’optimisation et l’application “en-ligne” (en
marche) des informations apprises demeure un problème difficile. Pour y aboutir, un pro-
cessus d’optimisation doit apprendre à prendre de meilleures décisions locales (e.g. le
choix du voisin suivant à un instant donné) en utilisant uniquement des informations glo-
bales, acquises le long de la recherche. Pour surmonter ce type de difficultés, l’intégration
d’une phase d’apprentissage dans le processus d’optimisation (“learning while optimizing”)
semble très prometteuse. Notre approche, utilisant des idées de réactivité [Battiti et al.,
2008], vise à développer un algorithme capable de se guider et de s’orienter tout seul dans
l’espace de solutions.
43
Chapitre 3. Cartographie de l’Espace de Recherche
entre des configurations visitées à des moments différents dans une longue recherche. De
plus, les études qui analysent la structure des espaces de recherche (voir [Hertz et al., 1994;
Hamiez and Hao, 2004; Culberson and Gent, 2001] pour la coloration de graphe) sont
souvent orientées vers des informations théoriques plutôt que sur leur application dans un
algorithme.
Étant donné un processus de recherche traversant l’espace des solutions, quelques ques-
tions importantes pourraient être posées :
– à quoi ressemble son chemin d’exploration ?
– quelles régions seront le plus souvent explorées ?
– le processus de recherche, explore-t-il beaucoup plus que quelques régions ?
– quelle est la distribution spatiale des meilleures configurations visitées ?
– ces meilleures configurations sont-elles aléatoirement dispersées ?
– le processus de recherche, peut-il être guidé vers un optimum global ?
L’hypothèse de clusterisation En fait, l’étude qui suit est consacrée principalement
à ces questions. En utilisant une mesure de distance dans l’espace de recherche (voir Section
[Link] ci-dessous, ou Chapitre 6 pour une description détaillé), nous définissons la notion
de sphère : l’ensemble de configurations situées à moins d’ une certaine distance (le rayon)
d’une configuration centrale. L’hypothèse de clusterisation est la suivante : les optima
locaux découverts par la recherche ne sont pas aléatoirement dispersés dans l’espace, mais
ils forment des clusters de points qui peuvent être confinés dans des sphères de diamètre
spécifique.
Dans ce chapitre, nous considérons la recherche locale de la Section 2.2, i.e. l’algorithme
Tabou de base sans critère d’aspiration mais avec une liste Tabou réactive. Par souci
de lisibilité, nous rappelons très brièvement dans ce paragraphe ses composantes et sa
construction. Essentiellement, la recherche Tabou se déplace itérativement d’une coloration
à l’autre en modifiant la couleur d’un sommet en conflit jusqu’à ce qu’une coloration
légale soit trouvée, ou qu’une condition d’arrêt soit atteinte. Chaque mouvement effectué
(i.e. chaque nouveau changement de couleur) est marqué Tabou pour un certain nombre
d’itérations, i.e. la durée Tabou T` .
Cet algorithme est en effet capable d’éviter un optimum local indépendant (et même
des plateaux de taille raisonnable) avec une simple liste Tabou. Cependant, les ques-
tions ci-dessus sont toujours ouvertes, et restent essentielles. Y a-t-il une garantie que
l’algorithme explore plus de régions en une semaine qu’en une heure ? Malheureusement,
comme pour la plupart des algorithmes de recherche locale, la réponse est Non !. Plu-
sieurs tests expérimentaux dans d’autres articles prouvent que les résultats ne peuvent
pas être améliorés en augmentant la limite de temps au-delà d’un certain seuil (i.e. plu-
sieurs heures pour la coloration). On peut vérifier dans [Blöchliger and Zufferey, 2008;
Hertz et al., 2008] que l’amélioration de performance réalisée grâce à l’augmentation de
temps de calcul (en passant d’une heure à dix !) est tout à fait limitée ; de plus, nous dou-
tons qu’en employant 100 ou 1000 heures ce type d’algorithmes Tabou puissent atteindre
de nombreuses nouvelles bornes.
44
3.3 Cartographie de l’espace de recherche
45
Chapitre 3. Cartographie de l’Espace de Recherche
thèse, nous utilisons une fonction basique de voisinage : les voisins d’une coloration sont
essentiellement obtenus en effectuant un changement de couleur (voir Section 2.2.1 pour
la définition formelle).
De plus, nous disposons déjà d’une méthode de calcul bien étudiée pour déterminer
la distance de transfert. Cette méthode utilise une réduction au problème d’affectation,
qui est résolu par la méthode hongroise – voir Section [Link]. La description formelle
et complète de la distance de transfert est disponible au Chapitre 6, mais dans ce qui
suit il suffit de dire que d(C, C 0 ) représente le nombre minimum de pas (i.e. changements
de couleurs) nécessaires pour aller de C à C 0 . Une cartographie très similaire pourrait
être effectuée pour d’autres problèmes, avec d’autres distances, associées à des voisinages
spécifiques (voir des exemples dans la section 4.5).
1. Un logiciel libre de plus en plus populaire, voir [Link]. Nous avons utilisé gnuR pour
produire tous les graphiques dans cette thèse.
46
3.3 Cartographie de l’espace de recherche
sP
1≤i,j≤p (Dij − dij )2
sfit = P 2
1≤i,j≤p Dij
Selon les indications fournies par Kruskal dans son article séminal de MDS [Kruskal,
1964], la représentation MDS est : a) mauvaise si sfit > 0.2, b) juste si sfit ≤ 0.1, c) bonne
si sfit ≤ 0, 05, d) excellente si sfit ≤ 0, 025 et e) parfaite si sfit = 0. Dans nos analyses,
même si le nombre total de points est très grand, nous ne présentons aucune représentation
mauvaise (i.e. avec sfit > 0.2).
47
Chapitre 3. Cartographie de l’Espace de Recherche
200
Y Axis
0
0
0
Étant donnée une instance (G, k) ainsi qu’ une première coloration de grande qualité
C0 , nous lançons l’algorithme Tabou à partir de C0 . Le processus de recherche visite
une série de colorations et nous notons C0 , C1 , C2 , . . . les configurations de grande qualité,
48
3.3 Cartographie de l’espace de recherche
satisfaisant f (Ci ) ≤ f (C0 ) – i.e. nous considérons le seuil de qualité Bf = f (C0 ). Dans tous
nos tests, le nombre de configurations de grande qualité représente seulement une petite
fraction du nombre total de colorations visitées le long de la recherche ; nous ignorons les
colorations plus mauvaises que C0 parce qu’elles sont largement distribuées et elles peuvent
être facilement trouvées. En effet, des configurations de basse qualité peuvent être trouvées
plus facilement dans l’espace – i.e. même dans la proximité de l’optimum local initial C0 ,
il devrait y avoir de nombreuses colorations plus mauvaises.
Par exemple, pour l’instance (le450.25c, 25) : (i) il est vraiment difficile de trouver des
colorations sans conflits 2 , (ii) il est assez facile de trouver des colorations avec 1 conflit
en lançant la recherche à partir d’une première coloration à 1 conflit, (iii) de nombreuses
colorations à 2 conflits sont dispersées partout autour de la configuration initiale à 1 conflit.
Pour ce graphe, et pour une coloration initiale C0 avec un conflit, nous considérons les
autres configurations à 1 conflit comme de grande qualité, et les configurations à 2 conflits
comme de basse qualité. Si on considère également les configurations de basse qualité dans
cette analyse, on trouverait des points très uniformément distribués dans l’espace.
600 c onfig ura tions de d sjc 1000.1 240 c onfig ura tions de le450.25c
200
100
Z Axe
Z Axe
200 100
Y Axe Y Axe
0 0
0
Figure 3.2 – Colorations de grande qualité (avec f (C) ≤ 4) visitées pendant 60000
itérations par la recherche Tabou pour G = dsjc1000.1 et k = 20 (à gauche) et colorations
de grande qualité (avec f (C) ≤ 1) visitées pendant 25000 itérations par la recherche
Tabou pour G = le450.25.c et k = 25 (à droite). Les valeurs de stress (déformation) sont
sfit = 0.19 et sfit = 0.15, respectivement.
La Figure 3.2 montre des représentations MDS résultant de ce test expérimental. Deux
instances sont considérées : (a) le graphe aléatoire dsjc1000.1 (k = 20) avec la recherche
lancée à partir d’une coloration à 4 conflits (b) le graphe de Leighton le450.25c (k = 25)
avec la recherche initiée par une coloration avec 1 conflit. Afin de limiter le nombre de
points (et ainsi assurer la fiabilité des représentations MDS), nous considérons chaque série
2. Avant 2008, il y avait un seul algorithme publié [Morgenstern, 1996, p. 353] qui pouvait résoudre
(le450.25, k = 25).
49
Chapitre 3. Cartographie de l’Espace de Recherche
50
3.4 Conclusion du chapitre
flat300.28 dsjc250.5
8e+05
1500000
Nombre de distances
Nombre de distances
4e+05
0 500000
0e+00
0% 22 % 44 % 67 % 0% 27 % 53 % 80 %
Valeur de Distance Valeur de Distance
dsjc1000.1 le450.25c
0.0e+00 1.5e+07 3.0e+07
4e+07
Nombre de distances
Nombre de distances
0e+00 2e+07
0% 17 % 33 % 50 % 0% 7% 15 % 22 %
Valeur de Distance Valeur de Distance
Figure 3.3 – Histogrammes des distances entre chaque couple de configurations de grande
qualité (notées C0 , C1 , C2 , . . . , C40000 ) visitées par la recherche Tabou ; f (Ci ) est inférieur
à : a) f (C1 ) = 4 pour G = f lat300.28 et k = 30, b) f (C1 ) = 3 pour G = dsjc250.5 et
k = 28, c) f (C1 ) = 4 pour G = dsjc1000.1 et k = 20, et d) f (C1 ) = 1 pour G = le450.25c
et k = 25.
51
Chapitre 3. Cartographie de l’Espace de Recherche
est très utile en pratique : il est assez facile d’exploiter le fait que deux configurations de
1
grande qualité distantes de plus de 10 |V | sont dans des clusters différents. On considère
que leur “backbone” (affectation de couleurs aux sommets essentiels, non-périphériques)
est relativement différente.
Nous supposons que cette hypothèse est satisfaite pour toutes les séries de colorations
visitées par la recherche locale Tabou. L’application la plus importante de cette hypothèse
est développée dans le Chapitre 4, où nous présentons un algorithme guidé pour assurer la
diversification, et un algorithme guidé pour assurer l’intensification. Les deux algorithmes
1
considèrent que l’espace de recherche est organisé dans des sphères de rayon 10 |V |. De
plus, comme la procédure de recherche Tabou est également utilisée dans l’algorithme
évolutionniste Evo–Div du Chapitre 5, la même hypothèse est exploitée afin de garder
un écart minimum au sein de la population, i.e. les individus de la population devraient
1
toujours être distants de plus de 10 |V |.
52
Chapitre 4
Sommaire
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.1.1 Motivation et objectifs . . . . . . . . . . . . . . . . . . . . . . . . 54
4.2 TS–Div : recherche continue de régions inconnues . . . . . . . . 55
4.2.1 Description formelle de TS–Div . . . . . . . . . . . . . . . . . . . 56
4.2.2 Vitesse de TS–Div . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.3 TS–Int : un parcours en largeur de l’espace des solutions . . . 62
53
Chapitre 4. Recherches Locales Guidées : TS-Div et TS-Int
4.1 Introduction
4.1.1 Motivation et objectifs
La recherche locale classique dispose de peu de mécanismes globaux et, par rapport
aux algorithmes évolutionnistes ou à l’optimisation en essaim, elle manque souvent de
vision d’ensemble. En effet, toutes les décisions prises par une recherche locale typique
sont souvent fondées uniquement sur des informations au niveau microscopique (i.e. le
voisinage de la configuration courante, et/ou une histoire courte), sans vision de niveau
macroscopique. Par conséquent, ces algorithmes risquent de ne pas couvrir correctement
l’espace de recherche, i.e. ils peuvent visiter les mêmes régions à plusieurs reprises, ou ils
peuvent simplement rester bloqués dans des bassins d’attraction.
Ce chapitre est centré sur des stratégies qui intègrent des informations macroscopiques
sur l’espace de recherche afin de guider le processus de recherche. Ainsi, nous allons d’abord
présenter synthétiquement les principes de deux nouveaux algorithmes : TS–Div et TS–Int.
Notons qu’une notion centrale dans les deux cas est la sphère introduite dans le chapitre
précédent : l’ensemble de configurations situées à moins d’une distance R (rayon) d’une
configuration centre.
Le premier algorithme (TS–Div) est fondé sur un processus de recherche Tabou et sur
une composante d’apprentissage qui mémorise les sphères visitées, afin de guider ensuite le
processus de recherche. Comme la mémorisation d’une sphère nécessite uniquement l’en-
registrement d’une seule configuration (le centre), nous avons expérimentalement montré
que, bien que le nombre de configurations visitées soit toujours très grand, le nombre de
sphères visitées peut rester dans des limites très raisonnables (voir également la Figure
1.1, p. 12). Afin de guider le processus de recherche vers des sphères encore inconnues, la
composante d’apprentissage conserve en permanence la distance R de tout centre enregis-
tré.
TS–Int (Section 4.3) est centré sur l’exploitation d’un périmètre limité très prometteur.
À partir d’une configuration d’entrée, TS–Int effectue des investigations méticuleuses dans
sa proximité. D’abord, la sphère de la configuration d’entrée est soumise à une phase
d’investigation qui lance plusieurs processus Tabou, autorisés à explorer seulement dans
54
4.2 TS–Div : recherche continue de régions inconnues
cette sphère. Chaque processus Tabou peut arriver à un “point de sortie de sphère”, qui est
enregistré par TS–Int ; des processus Tabou sont lancés ensuite jusqu’à ce qu’il ne soit plus
possible de trouver des “points de sortie” suffisamment distants. Lorsque cette condition
est satisfaite, la sphère est considérée “vérifiée” (sans optima globaux). Ensuite, la phase
d’investigation de sphère est répétée avec les sphères des “points de sortie”, i.e. chaque
“point de sortie” découvert devient le centre d’une nouvelle sphère à vérifier ultérieurement.
Les centres de ces sphères sont enregistrés dans une file d’attente ordonnée, et ainsi, les
sphères sont traitées dans l’ordre de leur qualité.
Tous les tests expérimentaux fournis dans ce chapitre font appel à un processus ex-
plorateur fondé sur un algorithme Tabou de coloration – voir Section 2.2. Tandis que les
connaissances spécifiques du problème peuvent toujours être essentielles pour atteindre de
meilleurs résultats pratiques, les idées principales de TS–Div et de TS–Int sont indépen-
dantes du concept de coloration. Cependant, grâce à l’utilisation des informations macro-
scopiques, les recherche locale présentés dans ce chapitre peuvent effectivement concurren-
cer des algorithmes évolutionnistes plus complexes et plus raffinés.
Le reste du chapitre est organisé comme suit. Dans la Section 4.2 et la Section 4.3, nous
présentons ces deux algorithmes : TS–Div (assurant la diversification) et TS–Int (assurant
l’intensification). Des résultats, suivis d’une discussion sont présentés en Section 4.4.
55
Chapitre 4. Recherches Locales Guidées : TS-Div et TS-Int
Liste Tabou
Normale
Liste Tabou
Normale
Liste Tabou
Augumentée
56
4.2 TS–Div : recherche continue de régions inconnues
57
Chapitre 4. Recherches Locales Guidées : TS-Div et TS-Int
ALGORITHME TABUSEARCH-DIV
Entrée : l’espace de recherche Ω
Valeur de retour : Cbest , la meilleure configuration jamais visitée
C : la configuration courante
DÉBUT
1. C = configuration aléatoire de Ω
2. Cp = C /*le pivot, i.e. dernier centre de sphère enregistré*/
3. Taug = 0 /*l’augmentation de liste Tabou déclenchée par TS-Div*/
4. Tant que condition d’arrêt non atteinte
(a) C = le meilleur voisin non-Tabou en N (C)
(b) Si d(C, Cp) > R
i. Cp = C
ii. Si ALREADY-VISITED(Cp ) Alors
- Incrémenter Taug
Sinon
- Taug = 0
- Enregistrer Cp
(c) Marquer C Tabou pour T` + Taug itérations
/*T` =durée interne utilisée par l’Alg. Tabou de base*/
/*Taug = durée de diversification induite par l’alg. TS-Div*/
(d) Si (f (C) < f (Cp ))
- remplacer Cp avec C dans l’archive
- Cp = C /*i.e. “re-centrer” la sphère courante*/
(e) Si (f (C) < f (Cbest ))
- Cbest = C
5. Renvoyer Cbest
FIN
Pour récapituler, la variation de la durée Tabou (via le facteur Taug ) contrôle la balance
entre la diversification et l’intensification : plus grande est la valeur Taug , plus il y a
de la diversification. De cette façon, un contrôle approprié de Taug garantit que TS–Div
découvre de nouvelles régions à tout moment. En effet, notre réglage de Taug garantit que
le processus ne peut pas se coincer en (ré)explorant uniquement des sphères déjà visitées.
Si cela arrivait, la liste Tabou pourrait croı̂tre indéfiniment – Taug ne décroı̂t que lorsque
le processus de recherche trouve une nouvelle sphère. Une valeur suffisamment élevée de
Tl + Taug sera capable de diversifier (plus tôt ou plus tard) et d’arrêter tout bouclage entre
des sphères déjà-visitées.
Notons qu’il existe de nombreuses manières de créer de la diversité au moment où TS–
Div détecte qu’il re-visite une sphère. Par exemple, on aurait pu simplement appliquer un
opérateur de marche aléatoire, ou une perturbation classique de recherche locale itérée.
58
4.2 TS–Div : recherche continue de régions inconnues
59
Chapitre 4. Recherches Locales Guidées : TS-Div et TS-Int
le même temps de calcul qu’une itération de la recherche Tabou : une itération a besoin de
O(|V | + |CE| × k) > O(|V |). La prochaine section décrit une méthode pour maintenir le
nombre d’itérations et le nombre de calculs de la distance dans le même ordre de grandeur
pendant de longues exécutions de TS–Div. Ainsi, notre procédure de calcul de distance
garantit que le ralentissement provoqué par la composante d’apprentissage peut rester
dans des limites acceptables.
60
4.2 TS–Div : recherche continue de régions inconnues
acceptable.
Concernant la distance calculée au Pas 4.(b), cela exige un seul calcul par itération
et ne pose donc pas trop de problèmes. De plus, ce calcul de distance n’est pas toujours
nécessaire : si d(Cp , C) < R, TS–Div a besoin d’au moins R − d(Cp , C) pas pour sortir
de la sphère de Cp . Ainsi, après avoir calculé une fois la distance dans ce pas, TS–Div
peut l’éviter pendant les prochaines R − d(Cp , C) itérations sans aucun risque. Nous avons
expérimentalement observé que plus de 90% de calculs de distance (dans ce pas) peuvent
être économisés de cette manière.
Certains détails simples d’optimisation peuvent encore réduire le nombre de calculs de
distances. Bien que nous n’ayons pas employé cela pour la coloration de graphe, notons
qu’il est possible d’accroı̂tre le rayon R pour réduire le nombre de sphères considérées. Un
autre mécanisme simple consiste à transformer l’archive en une file d’attente qui enlève
l’élément le plus ancien à chaque opération d’insertion. Dans ce cas-là, TS–Div devient
une Recherche Tabou de Niveau Supérieur à Double Liste : (1) la liste traditionnelle des
dernières configurations visitées qui sont interdites, (2) la liste Tabou des sphères, em-
ployée pour éviter de revisiter des sphères visitées dans le passé récent. La signification
de l’expression “passé récent” dépend de la taille de la file d’attente qui devrait être réglée
selon le ralentissement introduit par la composante d’apprentissage.
Bf (f ixe) 0 5 6 7 8 9
Nbre. calculs de distance (×106 ) 0 1.5 31.7 877.7 13743 128932
Temps (heures:min) 120:56 120:51 120:37 122:32 149:17 312:43
Nbre. configurations dans l’archive pas archive 523.8 6244.6 37810 154462 602523
Mémoire (MB) 0 0.523 6.2 37 154 6025
Table 4.1 – Les ressources consommées par la recherche Tabou (colonne 2) et par TS–Div
(colonnes 3–7) avec plusieurs valeurs fixes de Bf , entre 5 et 9 pour (dsjc250.5, 27). Toutes
les valeurs rapportées représentent la moyenne sur 10 exécutions de 16 × 109 itérations.
Dans le Tableau 4.1, nous présentons (2ème et 3ème ligne, respectivement) le nombre
de calculs des distances et le nombre d’heures exigées (en moyenne) par une exécution
61
Chapitre 4. Recherches Locales Guidées : TS-Div et TS-Int
TS–Div. La colonne TS montre que la recherche Tabou de base a besoin d’environ 120
heures pour finir les 16 × 109 itérations. Si Bf ≤ 6, le ralentissement de la composante
d’apprentissage est négligeable, parce que le nombre de calculs de la distance est trop petit
(par rapport aux 16 milliards d’itérations). Pour Bf ∈ {7, 8}, la différence de temps est
toujours acceptable (i.e. inférieure à un quart du temps de base 120h) mais elle devient
trop grande pour Bf = 9 – dès que le nombre de calculs de la distance devient trop grand
par rapport au nombre d’itérations (128 milliards 16 milliards). La mémoire consommée
(5ème ligne) par l’archive est proportionnelle avec le nombre de configurations stockées dans
l’archive (4ème ligne), car chaque configuration exige |V | × 4 ' 1000 octets. 1
62
4.3 TS–Int : un parcours en largeur de l’espace des solutions
63
Chapitre 4. Recherches Locales Guidées : TS-Div et TS-Int
Configuration
de Départ
R=10%|V|
~
?
Solution à Atteindre.
Figure 4.2 – Illustration (Multidimensional Scaling) d’une évolution réelle de TS–Int pour
(G = le450.25, k = 25). Tous les points représentent des configurations avec f = 1 (dans
l’espace |V |-dimensionnel). Ils ont été découverts dans l’ordre des nombres : 1 est le point
de départ, les points 2, 3, . . . , 7 sont découverts par des processus Tabou lancés à partir du
point 1, etc. L’indicateur de distorsion (stress) est acceptable, i.e. sfit = 0.05, voir Section
[Link] (p. 46).
le nombre de nouveaux centres R-distants atteints à partir de Cs – rappelons que tous les
centres des sphères enregistrés en Q sont R-distants. Des processus Tabou sont lancés à
partir de Cs tant qu’il y a des chances de découvrir de nouveaux centres R-distants.
Pour l’illustration, la Figure 4.2 trace une exécution TS–Int simplifiée. La solution est
située à distance 23%|V | < 3R du sommet 1 (i.e. la configuration de départ) et elle est
toujours atteinte après une exploration d’arbre en profondeur 3 (sur 3 niveaux). Norma-
lement, le degré moyen de cet arbre pour cette instance est environ 20, mais nous avons
utilisé des valeurs plus petites de X et Y pour rendre chaque investigation de sphère plus
rapide. Dans la réalité, toute solution sur un rayon de 3R peut être atteinte par TS–Int
après avoir exploré environ 203 = 8000 sommets. Nous avons expérimentalement observé
aussi sur d’autres graphes que TS–Int trouve toujours la solution s’il commence à partir
d’un point situé à moins de 41 |V | de la solution (voir aussi la Section 4.4.3).
L’algorithme proposé dans cette section (TS–Int) peut être lancé à partir d’une colo-
ration d’entrée unique Cs , mais il peut accepter comme entrée une file de configurations
complètement différentes – i.e. la file Q peut être donnée comme entrée. Pour illustra-
tion, il est possible de prendre l’archive enregistrée par TS–Div, de garder uniquement
un ensemble des meilleures colorations complètement différentes et de construire une file
d’attente pour TS–Int. Ainsi, TS–Int est capable de faire une recherche intensifiée autour
des points les plus prometteurs découverts par un autre algorithme. Notons que TS–Int
64
4.4 Résultats et discussions
65
Chapitre 4. Recherches Locales Guidées : TS-Div et TS-Int
Table 4.2 – Les résultats de TS–Div avec une limite de temps de 50 heures. Pour chaque
instance de k-coloration (indiquée par Colonnes 1–3), la Colonne 4 rapporte le taux de
succès, i.e. le nombre d’exécutions réussies sur 10 ; les Colonnes 5 et 6 indiquent le nombre
moyen d’itérations et le temps moyen nécessaire pour réussir (atteindre une solution).
Le Tableau 4.3 présente les résultats de TS–Int sur plusieurs instances ; pour chaque
instance, TS–Int explore la proximité d’une configuration d’entrée fournie par TS–Div.
Les Colonnes 1–3 indiquent l’instance (comme les Colonnes 1–3 dans le Tableau 4.2), la
Colonne 4 montre l’amplitude de l’amélioration (le nombre de conflits de la configuration
de départ et de la configuration de fin – la meilleure trouvée par TS–Int), la Colonne 5
présente le taux de succès pour arriver à cette amélioration et les Colonnes 6–7 indiquent
l’effort moyen de calcul (en itérations et en heures, respectivement).
66
4.4 Résultats et discussions
Table 4.3 – Instances pour lesquelles TS–Int améliore une coloration d’entrée dans une
limite de temps de 50 heures. Les colorations d’entrée sont fournies par TS–Div ; les cellules
marquées ∗ indiquent que TS–Int trouve une solution à k couleurs uniquement à partir
d’une solution à (k + 1) ou (k + 2) couleurs.
TS–Int peut atteindre une solution avec un taux de succès de 100% (voir la Colonne
5 du Tableau 4.3) s’il est lancé à partir d’une coloration adéquate (i.e. pas trop loin
d’une solution, voir également la Section 4.4.3). De cette manière, TS–Int trouve pour la
première fois une coloration légale avec 223 couleurs pour le graphe dsjc1000.9 qui a été
bien étudié dans la littérature – notons que, très récemment, [Lü and Hao, 2010] vient de
rapporter aussi une solution. Tandis que TS–Div assure la diversification, TS–Int est un
algorithme d’intensification qui peut être systématiquement exécuté après TS–Div pour
explorer presque exhaustivement un périmètre limité autour des meilleures configurations
trouvées par TS–Div.
Il est important de noter que certaines configurations d’entrée fournies au TS–Int (dans
le Tableau 4.3), peuvent être très facilement accessibles : sauf dsjc1000.5, dsjc1000.9 (et
les cellules marquées ∗ ), toutes les configurations d’entrée ont été trouvées en une seule
exécution TS–Div. Par exemple, nous avons résolu (dsjc1000.1, k = 20) pour la première
fois avec TS–Int, et non-pas avec TS–Div. La première exécution de TS–Div n’a pas trouvé
de solutions, mais elle a trouvé trois colorations complètement différentes avec 1 conflit ;
l’une d’entre elles peut systématiquement conduire TS–Int à la solution (taux de succès
100%). Des conclusions similaires peuvent être tirées pour les graphes de Leighton. Pour
ces graphes, il est possible de trouver systématiquement une solution en appliquant TS–Int
sur une première coloration avec un conflit trouvée par TS–Div (voir ci-dessous).
67
Chapitre 4. Recherches Locales Guidées : TS-Div et TS-Int
68
4.4 Résultats et discussions
semble plus facile de résoudre l’instance le450.25c en localisant d’abord une coloration à
1 conflit et en appliquant TS–Int sur celle-ci.
69
Chapitre 4. Recherches Locales Guidées : TS-Div et TS-Int
aléatoires où ils combinent des configurations complètement différentes pour atteindre de
nouvelles régions. 2
70
4.5 Vers des applications à d’autres problèmes d’optimisation combinatoire
– un espace de recherche (dans notre cas, il comprend toutes les colorations possibles) ;
– une fonction de voisinage (dans notre cas, défini par des changements de couleur) ;
– une fonction objectif (dans notre cas, le nombre de conflits f ) ;
– et une distance de l’espace de recherche (dans notre cas, la distance de transfert
entre partitions).
Essentiellement, les deux algorithmes sont construits comme des extensions de la re-
cherche Tabou. La condition nécessaire pour pouvoir les mettre efficacement en application
est de trouver une mesure de distance : (i) avec une complexité de calcul raisonnable par
rapport à une itération Tabou et (ii) qui reflète la proximité selon le voisinage utilisé – la
recherche Tabou ne doit pas avancer sur une longue distance en une seule itération. Plus
formellement, la distance entre deux configurations doit indiquer le nombre minimum de
transitions de voisinage nécessaires pour aller d’une configuration à l’autre. Comme pour
tout algorithme générique, le succès de TS–Div ou TS–Int dépend aussi de quelques fac-
teurs dépendants du problème, i.e. un choix adéquat du rayon R, ou une méthode pour
bien définir les configurations de grande qualité.
Par conséquent, s’il est possible de trouver une telle mesure de distance dont le temps
moyen de calcul n’est pas trop élevé par rapport à l’exécution d’une itération Tabou, les
deux algorithmes peuvent être appliqués. TS–Int est moins sensible à la vitesse de calcul
de distance, et ainsi, il peut plus facilement être appliqué à tout problème. Il pourrait
être très utile lorsqu’il y a une méthode quoi que ce soit de “conjecturer” la localisation
approximative de la solution. Cependant, la mesure de distance devrait toujours regrouper
dans une R-sphère tous les optima locaux avec le même “backbone” – partageant une
sous-structure commune importante. On peut trouver plusieurs exemples de distances qui
peuvent être définies de cette manière, en employant quelques voisinages spécifiques :
– la distance de Hamming pour les problèmes avec représentation de type chaı̂ne (ta-
bleau unidimensionnel) utilisant un voisinage 1-Flip (i.e. des problèmes de satisfac-
tion de contraintes avec un voisinage qui change simplement la valeur d’une variable),
– le distance de Kendall Tau [Kendall, 1938] pour des problèmes avec une représenta-
tion basée sur des permutations, utilisant un voisinage fondé sur des transpositions
adjacentes (i.e. le voyageur de commerce avec un voisinage qui inverse deux villes
adjacentes),
– la distance de Levenshtein pour des problèmes avec représentation de chaı̂ne et avec
un voisinage défini en utilisant des opérations d’édition (i.e. supprimer, insérer ou
remplacer une position du chaı̂ne)
En ce qui concerne le temps élevé du parcours d’archive, il peut être réduit significa-
tivement si besoin avec au moins trois méthodes : (i) en faisant le parcours uniquement
sur les configurations de qualité (dans les couches “profondes” de l’espace de recherche),
(ii) en augmentant le rayon R et (iii) en transformant l’archive dans une file qui enlève
le plus ancien élément à chaque opération d’insertion. Dans le dernier cas, l’algorithme
TS–Div deviendrait une Recherche Tabou Double, i.e. avec deux listes : (1) la liste Ta-
bou traditionnelle contenant des configurations récemment visitées qui sont interdites, (2)
une nouvelle liste de sphères récentes qui sont utilisées pour que TS–Div évite les sphères
visitées dans “le passé récent”. La portée de l’expression “passé récent” dépendrait de la
taille de la file qui devrait être réglée selon le ralentissement induit par la composante
71
Chapitre 4. Recherches Locales Guidées : TS-Div et TS-Int
d’apprentissage.
72
4.6 Conclusions de chapitre
73
Chapitre 5
Contrôle de Diversité et
Croisement Informé dans
L’Approche Évolutionniste
Sommaire
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.2 Présentation générale de l’algorithme évolutionniste . . . . . . 77
5.2.1 Terminologie du calcul évolutionniste . . . . . . . . . . . . . . . . 77
5.2.2 L’algorithme mémétique . . . . . . . . . . . . . . . . . . . . . . . 78
75
Chapitre 5. Contrôle de Diversité et Croisement Informé dans L’Approche Évolutionniste
5.1 Introduction
Comme nous l’avons souligné dans l’introduction de cette thèse (voir Section 1.2.1), les
algorithmes évolutionnistes hybrides ont traditionnellement atteint de très bons résultats
pratiques et ils font partie des approches les plus efficaces pour la coloration de graphe (voir
aussi Section 1.2.4). Dans ce chapitre, nous nous concentrons sur deux facteurs cruciaux
dans le calcul évolutionniste : la diversité de la population et l’opérateur de croisement.
En effet, une difficulté connue des algorithmes évolutionnistes concerne la diversité et
le risque de convergence prématurée. Pour tenter de réduire ce risque, nous utilisons la
mesure de distance dans l’espace de recherche et nous montrons comment l’employer pour
assurer un écart adéquat entre les individus. Nous présentons une stratégie générique pour
gérer la population afin d’imposer une distance minimum entre tout couple d’individus. La
nouvelle stratégie permet d’éviter la convergence prématurée, tout en conservant la qualité
de population. Cette procédure permet également de réduire un autre risque spécifique
pour les petites populations : celui de ne pas couvrir de manière adéquate l’espace de
recherche [Reeves, 1997].
Une autre question délicate dans les algorithmes évolutionnistes est de concevoir un
opérateur de croisement pertinent pour le problème en question, i.e. qui préserve les bonnes
caractéristiques des parents et perturbe les mauvais [Radcliffe, 1994]. Pour la coloration
de graphe, il est très utile de considérer une coloration comme une partition [Dorne and
Hao, 1998a; Galinier and Hao, 1999]. En effet, les meilleurs croisements pour la coloration
choisissent certaines classes des deux parents et celles-ci sont considérées comme blocs
constitutifs (gènes ou groupes [Falkenauer, 1998]) à transmettre à l’enfant. Une question
essentielle consiste à bien choisir les meilleures classes à utiliser pour engendrer un nouvel
individu. Pour cela, à chaque classe est affecté un score qui évalue sa qualité. Tandis que
les approches classiques considèrent uniquement la taille des classes ou leur nombre de
conflits, nous présentons une mesure plus informée pour évaluer et trier les classes des
76
5.2 Présentation générale de l’algorithme évolutionniste
parents et, ainsi, pour mieux sélectionner l’information qui est transmise à la génération
suivante.
Nous cherchons également à identifier les plus importantes caractéristiques qui rendent
un individu très adapté (ou de grande qualité). Cette information est très utile pour
déterminer un nombre approprié de parents, ainsi que pour la fonction d’évaluation dans
la recherche locale. En utilisant l’hypothèse de clusterisation (i.e. on considère que les
individus les plus adaptés sont regroupés dans des sphères de rayon R), nous définissons une
frontière entre “individus proches” et “individus distants”. Un principe important de notre
stratégie de diversité consiste à travailler uniquement avec des individus distants (de plus
de R). Notre algorithme (Evo–Div) atteint la plupart des meilleures bornes supérieures de
la littérature et trouve aussi des solutions non connues avant la thèse. Enfin, la contribution
de chaque nouvelle composante introduite par Evo–Div est clairement évaluée.
Dans la prochaine section, nous rappelons le modèle général de l’algorithme mémétique,
ainsi que les définitions de base. Le nouveau croisement informé est détaillé dans la Section
5.3. La méthode de contrôle de diversité/écart est discutée en Section 5.4. La Section 5.5 est
consacrée à des résultats expérimentaux et nous terminons ce chapitre par des conclusions.
Afin de présenter notre approche, notons que le vocabulaire lié à la communauté évolu-
tionniste est différent de celui de la recherche locale. Nous préférons suivre la terminologie
des algorithmes évolutionnistes :
– individu Les individus représentent les configurations (les solutions candidates) utili-
sées dans le cadre de la recherche locale. Par conséquent, nous disons qu’un ensemble
d’individus forme la population P OP = {I1 , I2 , . . . I|P OP | } ;
– fonction d’évaluation informée fg eval Notre algorithme hybride emploie aussi une re-
cherche locale qui utilise une fonction d’évaluation plus informée que la fonction ob-
jectif. Dans la Section 2.3 nous avons introduit deux nouvelles fonctions d’évaluation
fe1 et fe2 ; dans ce chapitre, nous allons utiliser fg
eval = f1 .
e
77
Chapitre 5. Contrôle de Diversité et Croisement Informé dans L’Approche Évolutionniste
78
5.3 Croisement “bien informé”
79
Chapitre 5. Contrôle de Diversité et Croisement Informé dans L’Approche Évolutionniste
Ainsi, un opérateur de croisement doit choisir k classes de couleur des parents et les as-
sembler pour construire l’enfant. Afin de pouvoir générer des enfants de qualité, le but est
d’hériter les k meilleures classes de couleur, i.e. celles qui apportent la contribution la plus
importante sur la qualité. Par exemple, si l’on peut choisir k classes sans conflit (ensembles
indépendants) qui couvrent V , elles peuvent être employées pour construire une colora-
tion légale. Cela n’est habituellement pas possible, et nous devons aborder une question
essentielle : comment choisir les k meilleures classes dans plusieurs parents ? Pour cette
question, nous proposons d’affecter des scores aux classes en employant une procédure
informée, fondée sur plusieurs critères de valeur. Notons que nous introduisons un cadre
généralisé qui détermine un nombre approprié de parents pour chaque instance.
Le premier critère pour noter une classe est fondé sur la qualité et repose sur le principe
qu’une classe avec moins d’arêtes en conflit est toujours préférable à une classe avec plus de
conflits. Cependant, on rencontre souvent des classes sans conflit car Evo–Div converge as-
sez vite vers des colorations “presque optimales”. Un deuxième critère est donc nécessaire :
si l’on doit choisir entre deux classes avec le même nombre de conflits, on préfère la classe
la plus grande. Enfin, pour les instances où les tailles des classes sont assez homogènes
un troisième critère est employé pour davantage de discrimination : la somme des degrés
des sommets. L’idée de ce troisième critère est qu’un sommet de haut degré serait plus
contraignant et ainsi plus difficile à colorier correctement (voir également Section 2.3.1) ;
en conséquence, une classe (bien colorée) avec des sommets de plus haut degré a plus de
valeur.
Formellement, l’opérateur de croisement – dorénavant appelé WIPX (Well Informed
Partition Crossover) – est spécifié dans l’Algorithme 5.2. D’abord, il cherche (étape 2.A et
2.B) dans tous les parents la classe avec le meilleur (minimum) score. Après l’affectation
de celle-ci à l’enfant en cours de construction (étape 2.C), WIPX choisit la meilleure classe
suivante et il itère ce procédé. À chaque étape, tous les scores de classe sont calculés en
ignorant les sommets qui ont déjà reçu une couleur dans l’enfant (voir l’étape 2.A.1).
WIPX s’arête quand k classes de couleurs sont affectées ; tout sommet restant non colorié
reçoit la couleur k (étape 3).
Un risque potentiel de ce croisement est d’hériter la plupart des classes d’un seul
parent, notamment s’il y a un parent très adapté avec des classes qui éclipsent les autres.
Cependant, la similarité entre l’enfant et les parents est implicitement vérifiée dans une
seconde étape par la stratégie de contrôle de diversité qui rejette l’enfant s’il est trop
similaire à n’importe quel individu existant de la population.
80
5.3 Croisement “bien informé”
5. score[Iij ] = conflicts − 1
|V |
(classSize + degreeCls
|E|×|V |
)
En moyenne, chaque parent donne nk classes, et ainsi, un plus grand n détermine un plus
petit nombre de classes sélectionnées dans chaque parent – une plus forte perturbation
de l’agrégation existante dans chaque parent. Notre but revient à décider de ce qui est le
plus important : préserver l’agrégation de classes ou maximiser la probabilité d’hériter des
classes de qualité ?
Certaines instances ont des solutions avec de nombreuses classes de très petite taille
(e.g. classes de 3–4 sommets pour djsc1000.9 avec |V | = 1000 et k = 223). Il n’est pas
difficile de trouver un ensemble indépendant de cette taille, mais il est difficile d’agréger
de petites classes d’une manière optimale (sans chevauchement excessif). Cette situation
apparaı̂t typiquement pour les graphes denses, pour lesquels on a besoin d’un grand nombre
de couleurs k. Ainsi, la taille moyenne de classe (i.e. |Vk | ) est très faible. Dans cet exemple,
il vaut mieux employer deux parents afin de préserver l’agrégation des classes existantes
dans les parents.
D’autres instances (e.g. des graphes “creux”) nécessitent un très petit nombre de cou-
leurs, mais la taille moyenne des classes est très grande, e.g. 50 sommets pour le graphe
dsjc1000.1 avec |V | = 1000 et k = 20. Pour une telle instance, la valeur d’une coloration
de bonne qualité réside dans de grands ensembles indépendants, plutôt que dans leur agré-
gation. En utilisant 4 parents, on obtient 4k = 80 classes Iij d’entrée dans l’Algorithme 5.2.
C’est nettement moins que 4k ∼ = 1000 classes que l’on obtenait pour le graphe dscj1000.9
évoqué plus haut. Ainsi, la recombinaison ne devient pas trop chaotique en employant
plus de parents pour dsjc1000.1. De cette façon, la règle générique est d’employer deux
parents pour des instances avec de petites classes, trois pour des instances avec des classes
81
Chapitre 5. Contrôle de Diversité et Croisement Informé dans L’Approche Évolutionniste
moyennes, ou quatre pour de très grandes classes. Plus précisément, notre règle est la
suivante :
|V |
1. n = 2 si k <5
|V |
2. n = 4 si k > 15
3. n = 3 sinon.
82
5.4 Préservation et création continue de diversité
83
Chapitre 5. Contrôle de Diversité et Croisement Informé dans L’Approche Évolutionniste
R-sphère d’un individu existant). Par conséquent, si un enfant O est situé à une distance
inférieure à R d’un individu existant I, la procédure de rejet détecte ce problème (la rou-
tine acceptEnfant retourne False en Algorithme 5.1) et, de plus, elle effectue une des
actions suivantes :
1. rejeter O, si f (O) > f (I) – i.e. si O est plus mauvais que I ;
2. remplacer directement I avec O, si f (O) ≤ f (I).
Toutefois, dans les deux cas, nous considérons que O n’est pas satisfaisant car il n’ap-
porte pas de diversité à la population. Dans cette situation, Evo–Div ne passe pas à la
génération suivante et reprend tout le processus de reproduction – voir la boucle Repeat-
Until à l’étape 2.B. d’Algorithme 5.1. Ce processus de reproduction est répété jusqu’à
ce que l’enfant résultant soit suffisamment distant de tous les individus existants, voir
également la Section [Link].
84
5.4 Préservation et création continue de diversité
85
Chapitre 5. Contrôle de Diversité et Croisement Informé dans L’Approche Évolutionniste
86
5.4 Préservation et création continue de diversité
Dans le cas standard où d(Ia , Ib ) > R ∀Ia , Ib ∈ P op, la routine indivRemplacé n’est
pas censée assurer l’écart minimum cible. Son objectif est d’augmenter l’écart moyen. Pour
cela, elle doit fortement décourager l’existence de petites distances entre les individus de
la population. De plus, elle doit aussi faire respecter le principe “survie des meilleurs”.
Puisque le choix des parents est aléatoire, l’étape de remplacement est essentielle pour
maintenir l’écart ainsi que pour assurer une qualité suffisante.
La procédure de remplacement standard (voir Algorithme 5.3 ci-dessous) sélectionne
deux individus proches comme candidats pour l’élimination, et le moins adapté est éliminé.
Pour choisir le premier candidat C1 , Evo–Div utilise une sélection pseudo-aléatoire guidée
par certains critères de qualité (via la fonction AcceptCandidat). Le deuxième candidat
C2 est choisi en introduisant le critère d’écart suivant : C2 est le plus proche individu de
C1 respectant les mêmes critères de qualité que C1 . 2
87
Chapitre 5. Contrôle de Diversité et Croisement Informé dans L’Approche Évolutionniste
qui est une sous-population axée sur la diversité et qui change très rapidement. Cela pour-
rait rappeler les principes du “Scatter Search”, une métaheuristique utilisant un ensemble
d’intensification et un ensemble de diversification – voir [Hamiez and Hao, 2001] pour une
implémentation pour la coloration de graphe.
Des stratégies permettant d’assurer la diversité peuvent être trouvés dans de nom-
breuses directions de recherche. Dans les algorithmes génétiques “diversity-guided” ou
“diversity-controlling” [Ursem, 2002; Shimodaira, 1997; Zhu, 2003], on emploie un indi-
cateur global de diversité afin de choisir les opérateurs génétiques et leur probabilité d’ap-
plication. Par exemple, [Zhu, 2003] utilise un indicateur basé sur la distance moyenne
de Hamming afin de régler les taux de mutation et de croisement. [Ursem, 2002] em-
ploie des opérateurs d’intensification (sélection et recombinaison) quand un indicateur de
diversité est élevé, ou des opérateurs de diversification (mutation) quand la diversité est
faible. Dans cette piste de recherche, il n’y a pas vraiment besoin d’une mesure de distance
entre les individus, mais seulement d’un indicateur global de diversité de la population.
Par exemple, [Ursem, 2002] utilise un indicateur de dispersion statistique autour de la
valeur moyenne sur chaque variable. Cela s’est révélé particulièrement efficace en optimi-
sation continue. En général, la diversité de population peut être mesurée par de nombreux
indicateurs, selon le champ d’application (voir les références dans [Zhu, 2003, p. 1]).
Une étude à base de distances est l’algorithme MA|PM [Sörensen and Sevaux, 2006],
qui utilise aussi une procédure de rejet d’enfants. Dans MA|PM, si un enfant ne respecte
pas les critères de diversité, il est immédiatement muté. Pour Evo–Div, l’approche est
différente : nous préférons répéter le processus naturel de reproduction jusqu’à ce qu’il
apporte une diversité “naturelle” à la population. Dans Evo–Div, la qualité n’étant pas
sacrifiée au profit de la diversité, notre approche permet aussi de faire de la concurrence
aux meilleurs algorithmes pour notre problème de coloration.
Nous mentionnons aussi que, dans les algorithmes mémétiques, il est classique d’accor-
der de l’attention au fait que l’enfant doit être suffisamment différent de ses parents. Puis-
qu’une recherche locale est employée, il y a un risque élevé que la combinaison de deux pa-
rents proches mène à des solutions semblables. Pour éviter cela, une idée pertinente consiste
à toujours croiser des parents suffisamment éloignés. De plus, on peut également souhai-
ter générer l’enfant à égale distance de ses deux parents – voir [Galinier and Hao, 1999;
Tagawa et al., 1999] pour des applications de ce principe en coloration. Des techniques de
ce type peuvent être trouvées dans de nombreux problèmes d’optimisation combinatoires,
e.g. le problème de voyageur de commerce, voir le Distance Preserving Crossover [Freis-
leben and Merz, 1996]. Cependant, notre croisement n’est pas prévu pour assurer des
distances égales entre l’enfant et ses parents.
La “distance crowding” introduite dans [Deb et al., 2002] est utilisée pour trier les
individus en optimisation combinatoire multi-objectif. Une différence essentielle est que
cette “distance crowding” est mesurée dans l’espace de la fonction objectif, i.e. elle est
88
5.4 Préservation et création continue de diversité
fondée sur les différences entre les valeurs de la fonction d’adaptation [Deb et al., 2002;
Coello et al., 2004; Rajagopalan et al., 2008].
89
Chapitre 5. Contrôle de Diversité et Croisement Informé dans L’Approche Évolutionniste
induit également des niches, les niches stables ne sont pas recommandées dans un espace
discret. Le remplacement standard d’Evo–Div choisit l’individu éliminé indépendamment
de la position de l’enfant dans l’espace de recherche ; la distribution de la population
encourage de niches en niches à évoluer en permanence .
Pour conclure, le contrôle explicite de population utilisant des mesures de distance
semble avoir reçu relativement peu d’attention en optimisation discrète mono objectif.
Cependant, cette idée peut être très utile pour améliorer les algorithmes mémétiques
avec de petites populations. Cette approche est déjà considérée parmi les plus efficaces
pour de nombreux problèmes d’optimisation combinatoire. Le calcul de |P op|2 distances
par génération est une limitation dans les algorithmes de niche [Miller and Shaw, 1996;
Smith et al., 1993], mais cela ne pose pas de problèmes dans l’approche mémétique, où la
recherche locale est la phase qui consomme le plus de temps. Dans un algorithme multi-
modal, les techniques de niche sont également utilisées pour faire de l’intensification (car
on garde des sous-populations stables sur les niches), mais, dans l’algorithme mémétique,
l’intensification peut être assurée efficacement par la recherche locale. Dans notre cas, la
politique de diversification peut se concentrer uniquement sur le guidage de la recherche
vers de nouvelles régions.
[Link] Paramètres
Le réglage des paramètres est une tâche relativement simple pour Evo–Div : une valeur
appropriée peut être affectée à chaque paramètre à partir de quelques considérations théo-
riques assez génériques. En recherchant une valeur plus optimale pour chaque paramètre,
on pourrait certainement encore améliorer Evo–Div, mais vraisemblablement insuffisam-
ment pour bouleverser nos conclusions principales. Les valeurs des principaux paramètres
sont résumés dans le Tableau 5.1 et nous présentons ci-dessous les motivations qui nous
ont conduits vers ces valeurs.
– Paramètres génétiques majeurs : (i) la taille de population est |P OP |=20, (ii) le
nombre de parents n est entre 2 et 4, et (iii) l’écart minimum cible est R = 10%|V |.
Notre stratégie d’écart est prévue pour une petite population, et ainsi, toute taille de
population entre 10 et 30 produirait probablement des résultats similaires. Le nombre
de parents est par défaut n = 2 dans les travaux précédents, mais nous avons montré
90
5.5 Résultats et discussions
91
Chapitre 5. Contrôle de Diversité et Croisement Informé dans L’Approche Évolutionniste
Table 5.2 – Résultats détaillés d’Evo–Div avec un temps (CPU) limite de 300 minutes
sur toutes les instances difficiles. L’algorithme trouve la plupart des meilleures solutions
avec un taux de succès élevé (Colonne 3) – la meilleure borne supérieure k ∗ est indiquée
entre parenthèses dans la Colonne 1.
(C4000.5, K = 271) en trente jours et également pour (C4000.5, K = 272) en dix jours.
Bien qu’une limite de temps de 5 heures ne soit pas très élevée pour la coloration, Evo–
Div trouve la plupart des meilleures solutions – voir également les autres algorithmes dans
le Tableau 5.4. Si l’on considère l’ensemble de 47 graphes DIMACS de la Section 1.2.3 (i.e. y
compris les instances faciles de la Section [Link]), Evo–Div atteint en 5 heures la meilleure
borne connue pour 42 graphes sur 47, et trouve deux bornes inconnues avant cette thèse :
(dsjc1000.9, k = 223) et (C4000.5, k = 271). Il n’atteint pas la meilleure borne connue
uniquement pour 3 graphes sur 47. Notons qu’une de ces trois bornes, (latin square, k =
98), peut être atteinte avec une autre version d’Evo–Div (voir ci-dessous).
Nous avons utilisé une limite de temps comme condition d’arrêt parce que, dans notre
cas, les indicateurs plus génériques (i.e. nombre d’itérations) sont moins significatifs et ils
peuvent être facilement mal interprétés. Par exemple, une limite de générations fixée ne
prendrait pas en considération le ralentissement causé par un nombre variable de rejets
d’enfant et de calculs de distance. De plus, la complexité théorique d’une génération,
d’un croisement, ou d’une itération peut être différente d’un algorithme à l’autre ; une
comparaison de tels indicateurs pourrait être également biaisée. La plupart des algorithmes
récents [Malaguti et al., 2008; Blöchliger and Zufferey, 2008; Hertz et al., 2008; Galinier
92
5.5 Résultats et discussions
et al., 2008] utilisent également un temps limite comme condition d’arrêt ; les meilleurs
résultats sont habituellement atteints en moins de 10 heures. Les temps que nous avons
rapportés sont obtenus sur un processeur Xeon à 2.8GHz, avec le langage C++ compilé
avec l’option d’optimisation -O2 (gcc version 4.1.2 sous Linux).
Table 5.3 – Les résultats d’Evo–Div avec deux limites de temps. En 30 minutes, Evo–Div
trouve plusieurs solutions que d’autres algorithmes ne trouvent pas. Sur le long terme (12
heures), la politique de diversité assure un taux de réussite de 100% pour de nombreuses
instances difficiles.
a. Dans ce cas, 15 heures ont été nécessaires pour atteindre un taux de réussite de 10/10.
Plusieurs conclusions intéressantes peuvent être tirées du Tableau 5.3. Evo–Div peut
encore trouver de nombreuses solutions en 30 minutes ; cela est très rapide, car les temps
93
Chapitre 5. Contrôle de Diversité et Croisement Informé dans L’Approche Évolutionniste
de calcul pour la coloration sont généralement donnés en heures ou même en jours. À notre
connaissance, la plus petite limite de temps précédemment rapportée dans la littérature est
de 60 minutes dans deux articles publiés en 2008 – voir les Tableaux 1-4 dans [Blöchliger
and Zufferey, 2008] et les tableaux 1-3 dans [Hertz et al., 2008]. Evo–Div trouve en 30
minutes de nombreuses solutions non atteintes par aucun algorithme de ces sept tableaux :
(DSJC1000.5, k = 85), (f lat1000.76, k = 83), (le450.25c, k = 25) et (le450.25d, k = 25).
Cela montre d’abord l’efficacité de l’opérateur de croisement, car la stratégie de diversité
est moins active à court terme.
L’efficacité de la stratégie de diversité est attestée par les résultats sur le long terme. En
effet, les algorithmes d’optimisation combinatoire ont souvent des difficultés à améliorer
la performance en poussant le temps limite au-delà d’un certain seuil. Cela est dû au fait
qu’il est difficile de sortir d’un plateau ou d’arrêter de boucler sur un ensemble limité
de plateaux. Notre stratégie de préservation et de création continue de la diversité est
capable de surmonter ces difficultés. Les résultats sur le long terme donnent des preuves
que Evo–Div peut assurer une large couverture de l’espace.
Ainsi, Evo–Div atteint un taux de réussite de 100% si il a suffisamment de temps de
calcul. En règle générale, si Evo–Div peut résoudre une instance, il la résout systémati-
quement. Cette règle n’a que deux exceptions : l’instance (DSJC1000.9,223) qui est une
instance qui demande plutôt une forte intensification (elle peut être résolue même sans
stratégie de diversité, voir No-Div dans la Section 5.5.4), et aussi latin square qui est l’un
des rares points faibles d’Evo–Div.
Le Tableau 5.4 montre une comparaison entre les résultats d’Evo–Div et l’état de l’art,
i.e. les meilleurs résultats des algorithmes discutés dans la Section 1.2.4. Evo–Div trouve
des solutions non rapportées dans la littérature avant la thèse, et, à l’exception de très
rares points faibles, il atteint les meilleures bornes supérieures avec un fort taux de réussite.
De plus, le temps nécessaire pour obtenir ces résultats est assez faible – voir l’en-tête du
Tableau 5.4 (Lignes 4 et 5) qui donne le temps maximum requis par d’autres algorithmes,
ainsi que leur année de publication – cela fournit des informations sur la génération de la
machine utilisée.
En principe, nous présentons les résultats principaux d’Evo–Div en utilisant une seule
version de l’algorithme et avec une configuration fixe des paramètres. Seules les graphes
C2000.5 et C4000.5 ont nécessité plus de 300 minutes à Evo–Div, mais tous les algo-
rithmes ont fait une exception pour ces graphes immenses qui nécessitent habituellement
des jours ou semaines de calcul. Les trois meilleures bornes supérieures atteintes avec des
versions différentes d’Evo–Div sont clairement indiquées. Notons que plusieurs colonnes
individuelles du Tableau 5.4 rapportent en fait la meilleure performance de plusieurs al-
gorithmes, ou, au moins, de plusieurs versions d’un même algorithme.
94
5.5 Résultats et discussions
Table 5.4 – Les meilleures colorations trouvées par Evo–Div en moins de 5 heures et les
résultats des meilleurs algorithmes. Les colorations d’Evo–Div sont publiquement dispo-
nibles à [Link]
a. Les acronymes des algorithmes sont disponibles dans la Section 1.2.4, p. 19.
b. Pour ces graphes, k peut être réduit en utilisant des versions différentes d’Evo–Div : (R1000.5,k=237)
a été résolu avec un croisement qui utilise que des classes sans conflits ; (flat300.28, k = 29) et (latin square,
k = 98) ont été résolus avec une recherche Tabou plus longue – voir Section 5.5.4.
c. Pour ces deux graphes très grands C2000.5 et C4000.5, nous avons utilisé une limite de temps de
3 et 30 jours, respectivement. Notons que les bornes supérieures entre crochets ont été rapportées très
récemment (quand ce manuscrit était à moitié fini) dans [Lü and Hao, 2010].
Le but de cette section est d’analyser l’influence des concepts les plus importants ex-
ploités par Evo–Div. L’algorithme pourrait obtenir de bons résultats même en excluant
certaines composantes. Par exemple, si l’on utilise un croisement moins diversifiant, cette
faiblesse peut être partiellement compensée par la stratégie d’écart. Pour cette raison,
plusieurs instances ne sont pas très sensibles à de petits changements théoriques. Cepen-
dant, nous avons choisi dix instances représentatives, avec la plus importante variation de
performance, et nous examinons plusieurs versions d’Evo–Div sur ces instances.
Le Tableau 5.5 montre le taux de réussite et le temps de résolution obtenus avec Evo–
Div et avec cinq versions de l’algorithme obtenues en désactivant certaines composantes.
95
Chapitre 5. Contrôle de Diversité et Croisement Informé dans L’Approche Évolutionniste
#hits Min #hits Min #hits Min #hits Min #hits Min #hits Min
DSJC1000.1 20 10/10 29 0/10 – 4/10 211 9/10 37 10/10 31 10/10 26
DSJC1000.5 83 9/10 136 0/10 – 6/10 246 8/10 80 10/10 132 9/10 99
DSJC1000.9 223 2/10 245 1/10 110 2/10 220 2/10 183 0/10 – 0/10 –
DSJR500.1c 85 9/10 93 0/10 – 10/10 55 0/10 – 10/10 21 3/10 76
DSJR500.5 122 8/10 36 1/10 4 10/10 25 1/10 4 7/10 65 2/10 108
r1000.5 238 9/10 99 1/10 19 1/10 250 2/10 27 6/10 76 0/10 –
f lat1000.76.0 82 10/10 110 2/10 90 7/10 236 8/10 99 7/10 159 7/10 84
le450.25c 25 10/10 90 0/10 – 0/10 – 2/10 107 10/10 62 9/10 89
le450.25d 25 10/10 45 1/10 42 0/10 – 1/10 16 10/10 86 10/10 87
latin square 100 1/10 42 0/10 – 0/10 – 0/10 – 0/10 – 1/10 211
Table 5.5 – Comparaison entre la version standard d’Evo–Div et cinq versions obtenues
en excluant certains composantes d’algorithme. Pour chaque version, nous fournissons le
taux de succès (Colonnes “#hits”) et le temps en minutes (Colonnes “Min”). Les moyennes
sont calculées sur les exécutions réussies (la limite de temps est toujours de 5 heures).
Le temps limite est toujours de 300 minutes, le processeur et la machine sont identiques
et le code source est le même – sauf la ligne pour l’activation/désactivation de la compo-
sante investiguée. Les résultats confirment les considérations théoriques sur les éléments
correspondants aux versions Evo–Div suivantes :
1. No-Div (Colonnes 5 et 6) : Evo–Div sans stratégie de diversité – i.e. tout enfant
est accepté et l’individu le plus mauvais est éliminé à l’étape de remplacement.
En comparaison avec Evo–Div (Colonnes 3 et 4), No-Div est significativement plus
mauvais. Bien qu’il puisse encore trouver quelques solutions, les taux de réussite
stables d’Evo–Div sont perdus parce que la diversité n’existe plus ;
2. Basic-Cross (Colonnes 7 et 8 ) : Evo–Div avec un croisement de base, similaire avec
GPX [Galinier and Hao, 1999] (voir Section 5.3.2). Bien que Basic-Cross puisse
trouver 70% des solutions atteintes par Evo–Div, son plus grand problème est qu’il
rend l’algorithme plus lent. Même en ignorant les 30% d’échec, Basic-Cross exige
environ dix fois plus de temps de calcul (voir DSJC1000.1) et c’est pour cette raison
qu’il obtient des taux de réussite inférieurs. Cependant, ce croisement reste encore
efficace pour l’instance difficile (DSJC1000., k = 223) ;
3. R-5% (Colonnes 9 et 10) : Evo–Div avec un écart minimum cible fixe R0 = 5%|V |.
L’Evo–Div standard obtient des résultats systématiquement meilleurs que cette ver-
sion. Cela confirme l’hypothèse de clusterisation qui recommande de garder une
distance minimum de R = 10%|V | entre tout couple d’individus ;
4. R-20% (Colonnes 11 et 12) : Evo–Div avec un écart minimum cible fixe R00 = 20%|V |.
Cette version échoue sur deux instances et obtient des taux de réussite inférieurs
96
5.6 Conclusions
sur encore trois instances. Les résultats sont bons, parce que R00 > R et, ainsi,
cette version d’Evo–Div ne souffre pas d’un manque de diversité. En revanche, elle
force une diversification excessive et ne réalise pas assez d’intensification. Ainsi, elle
ne résout pas (DSJC1000.9, k = 223) qui a besoin d’une forte intensification –
rappelons qu’elle était résolue même par No-Div. Cela confirme de nouveau nos
considérations théoriques liées à l’écart minimum cible de R = 10%|V | ;
5. No-fg eval (Colonnes 13 et 14) : Evo–Div avec une recherche locale utilisant la fonc-
tion d’évaluation classique f au lieux de la fonction fg eval à base de degrés (Sec-
tion [Link]). L’effet positif de la nouvelle fonction feval est plus visible sur les
g
graphes avec une grande variation de degré – en particulier les graphes géométriques
(r1000.5, DSJR500.5 et DSJR500.1c), pour lesquels le degré maximum peut être
d’un ordre de grandeur plus élevé que le degré minimum. Il est naturel que la différen-
ciation de fg eval soit moins significative sur les graphes avec des degrés plus homogènes
(les graphes de Leighton ou la plupart des graphes aléatoires). Notons que fg eval a une
influence positive aussi sur (DSJC1000.9, k = 223), car ce graphe a des degrés très
élevés. Toutefois, à l’exception de ce cas et des graphes géométriques, Evo–Div est
toujours en mesure d’obtenir des résultats similaires en utilisant la fonction classique
d’évaluation (le nombre de conflits).
5.6 Conclusions
Nous avons décrit un nouvel algorithme mémétique (Evo–Div) qui se distingue par l’in-
troduction d’une stratégie d’écart qui permet à la fois de préserver et de créer continuelle-
ment de la diversité. De plus, le croisement multi-parent (WIPX) exploite un grand nombre
d’informations pour mieux choisir les classes de couleurs utilisées dans la construction de
l’enfant. Nous avons montré expérimentalement que ce croisement assure une convergence
rapide vers des solutions (Section [Link]). D’autre part, la convergence prématurée est
empêchée par la stratégie d’écart ; à l’aide de plusieurs mécanismes complémentaires de
dispersion, Evo–Div assure une couverture très large de l’espace de recherche. Les résultats
97
Chapitre 5. Contrôle de Diversité et Croisement Informé dans L’Approche Évolutionniste
98
Chapitre 6
Sommaire
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.1.1 Contexte et travaux connexes . . . . . . . . . . . . . . . . . . . . 100
6.1.2 Pourquoi un nouvel algorithme ? . . . . . . . . . . . . . . . . . . 101
6.2 Définition formelle de la distance . . . . . . . . . . . . . . . . . . 102
6.3 Calcul de la distance . . . . . . . . . . . . . . . . . . . . . . . . . 103
6.3.1 Matrice de similarité T en O(|S|) . . . . . . . . . . . . . . . . . 104
6.3.2 Affectation maximale en O(|S|) . . . . . . . . . . . . . . . . . . 105
6.4 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.5 Une étude de cas pour la coloration de graphe . . . . . . . . . . 109
6.6 Remarques finales . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
6.6.1 Pseudocode de l’algorithme . . . . . . . . . . . . . . . . . . . . . 110
99
Chapitre 6. Distance de Transfert : Calcul Rapide et Interprétation Spécifique à la
Coloration
6.1 Introduction
Soit k un entier positif et S un ensemble. 1 Une k-partition de S (équivalente à une
k-coloration d’un ensemble V de sommets) est un ensemble de k classes (sous-ensembles,
parties, ou cellules) deux à deux disjointes, qui forment un recouvrement de S. Plusieurs
applications pratiques de partitionnement ou de clusterisation de données font fréquem-
ment appel à des calculs de distance entre partitions. Des études précédentes ont montré
qu’il est possible de faire ce calcul en temps polynomial – minimum O(|S|+k 2 ) et maximum
O(|S| + k 3 ) – en utilisant une réduction directe au problème d’affectation.
Nous décrivons plusieurs conditions qui permettent à un nouvel algorithme de calculer
la distance en O(|S|) opérations. En pratique, ces conditions sont associées à des partitions
relativement proches/similaires. Nous allons donner des arguments pour montrer que, sauf
cas exceptionnel (i.e. partitions spécialement construites), toute distance inférieure à |S|
5
peut être calculée en O(|S|). De plus, cet algorithme peut également être employé pour
identifier un ensemble maximal de classes très similaires (entre deux partitions distantes,
mais avec des classes communes).
100
6.1 Introduction
ce calcul ne devrait pas appliquer directement l’algorithme hongrois. Bien qu’il existe des
algorithmes pour résoudre le problème d’affectation sur des matrices creuses [Carpaneto
and Toth, 1983], la possibilité de réduire la complexité en dessous de O(k 2 ) n’a pas été
considérée.
D’un point de vue théorique, la distance de transfert satisfait plusieurs propriétés inté-
ressantes. Par exemple, il est déjà connu qu’elle constitue une métrique dans l’espace des
partitions [Cardoso and Corte-Real, 2005]. Des études plus avancées [Charon et al., 2006]
montrent que, bien que la distance s’étende
l m de 0 à |S|, elle ne peut jamais atteindre cer-
|S|
taines bornes supérieures (e.g. |S| − k ). Une comparaison entre la fonction de distance
et d’autres indices similaires (e.g. l’indice de Rand) est également disponible [Denœud
and Guénoche, 2006] ; elle montre la distribution de plusieurs indices entre des partitions
proches. La distribution des distances entre des partitions aléatoires est également bien
étudiée, et permet de mieux interpréter les valeurs de distance [Denœud, 2008]. Il y a aussi
des généralisations de cette mesure de distance dans la littérature [Berman et al., 2007;
Berger-Wolf et al., 2007].
Une récente étude [Denœud, 2008] pourrait être particulièrement utile pour la co-
loration de graphe parce qu’elle montre empiriquement que la distance moyenne entre
deux partitions aléatoires est autour de 69%|S| (avec une petite déviation standard) pour
|S| = 100 [Denœud, 2008, Table 1] 2 . Cela fournit des repères pour pouvoir interpréter
les valeurs de distance entre colorations. Par exemple, une conséquence directe est que
deux colorations situées à une distance de 50%|V | ne peuvent pas être considérées comme
complètement indépendantes. De plus, il est certain que le rayon R = 10%|S| utilisé pour
définir nos sphères représente une valeur très petite.
2. Bien que pour |S| = 100 la distance moyenne entre deux partitions aléatoires soit de 69%|S|, elle est
66%|S| pour |S| = 75, 64%|S| pour |S| = 50, etc. Il nous semble que pour |S| = 1000 la distance moyenne
est d’environ 80%|S|.
101
Chapitre 6. Distance de Transfert : Calcul Rapide et Interprétation Spécifique à la
Coloration
biologie, cette distance est employée pour estimer la différence (erreur) entre une partition
connue d’une population (une structure phylogénique de famille) et une reconstruction
bâtie à partir des données génétiques [Konovalov et al., 2005; Berger-Wolf et al., 2007].
Dans le partitionnement de données, on obtient souvent des partitions différentes avec
plusieurs algorithmes de clusterisation et il faut trouver un consensus entre ces parti-
tions. Pour cela, on détermine une partition centrale, i.e. une partition qui réduit au
minimum la distance moyenne à toutes les autres partitions [da Costa and Rao, 2004;
Berman et al., 2007]. S’il n’y pas trop de désaccord entre les algorithmes de clusterisa-
tion, les partitions produites seront suffisamment proches pour être manipulées par notre
algorithme.
Dans la prochaine section, nous présentons les définitions de base. La Section 6.3
discute des conditions qui permettent de calculer la distance en O(|S|). La Section 6.4
fait une extension de l’algorithme proposé pour le cas où certaines de ces conditions ne
sont que partiellement satisfaites. La Section 6.5 discute de l’application de cet algorithme
aux calculs de distance entre les colorations de graphe. On termine le chapitre par des
conclusions et un exemple de pseudo-code d’algorithme O(|S|).
102
6.3 Calcul de la distance
Notons que la distance est toujours strictement inférieure à |S|, et ainsi, on aurait pu
également la normaliser par rapport à d’autres valeurs, par exemple la distance maximum
[Charon et al., 2006]. Cependant, la normalisation simple ci-dessus suffit dans cette thèse.
T(Mat. de Similarité)
P1: |1 2 3 4 | 5 6 7 | 8 9| 4 0 0
Similarité = 7
=> 0 1 2 =>
P2: |1 2 3 4 8 | 5 9 | 6 7| Distance = |S| - 7 = 2
1 1 0
Figure 6.1 – Un exemple de calcul de distance. Il faut transférer au moins deux éléments
(car d(P1 , P2 ) = 2) entre les classes d’une partition pour la transformer en l’autre.
103
Chapitre 6. Distance de Transfert : Calcul Rapide et Interprétation Spécifique à la
Coloration
Bien que la matrice T ait k × k éléments, notre algorithme n’utilise effectivement que
|S| valeurs au maximum : les valeurs Tij = |P1i ∩P2j | avec i = P1 (x) et j = P2 (x), pour tous
les x ∈ S. Pour les autres i et j (s’il n’y a pas de x ∈ S tel que i = P1 (x) et j = P2 (x)),
la valeur |P1i ∩ P2j | est forcement nulle. La construction de T se fait en trois étapes :
Dorénavant, les valeurs aux positions TP1 (x),P2 (x) (pour tout x ∈ S) s’appelleront des
éléments actifs. En fait, la structure matricielle est employée uniquement pour pouvoir
indexer ces éléments actifs, pour adresser rapidement les positions TP1 (x),P2 (x) avec x ∈ S.
Les autres éléments du T ne sont jamais utilisés, ni pour lire, ni pour écrire. On a tout de
même besoin d’une structure de matrice, parce que on ne connaı̂t pas préalablement les
positions des éléments actifs.
Concernant l’allocation de la matrice T , cela nécessite de trouver un bloc de mémoire
qui contient k 2 entiers, mais sans initialisation de valeur. La plupart des systèmes d’ex-
ploitations peuvent faire cela en temps constant – il n’y a aucune contrainte théorique
qui impose de parcourir chaque octet du bloc. Nous avons utilisé l’instruction malloc(k2 ·
sizeof(int)), qui recherche un bloc plus grand que la taille demandée (i.e. au moins k 2 ·
sizeof(int) octets) dans la liste des blocs RAM libre 3 . La complexité de cette opération
dépend de la fragmentation de la mémoire RAM, et non pas du nombre d’octets demandés.
Le lecteur intéressé peut vérifier une implémentation de malloc – une des plus populaires
est celle de Doug Lea, voir “A memory allocator by Doug Lea”. En Windows, la même
opération peut se faire via la routine HeapAlloc(), avec le drapeau HEAP_ZERO_MEMORY
désactivé. 4
3. Il ne faut surtout pas utiliser calloc, car cette fonction fait aussi l’initialisation.
4. Nos heuristiques calculent des millions de distances. Même si on fait une allocation-avec-initialisation
de complexité O(k2 ), cette opération est nécessaire une seule fois, parce que la même matrice peut être
(re-)utilisée pour tous les calculs de distance (après chaque calcul, on remet à 0 les éléments actifs).
104
6.3 Calcul de la distance
Les inégalités de ce théorème doivent être strictes, car "sinon, il# n’est pas toujours
2 1
possible de déterminer une fonction bijective σ̄, e.g. si T = . Le cas résolu par
2 1
ce théorème peut être vu comme le dual d’un cas particulier d’algorithme hongrois où
le premier pas découvre k zéros mutuellement indépendants (i.e. ne se situant pas sur la
même ligne ou colonne). Cependant, nous calculons la distance de transfert sans convertir
le problème en un problème de minimisation (l’algorithme hongrois ne résout que des
problèmes de minimisation) et sans exécuter les réductions de complexité O(k ×k) requises
par l’algorithme hongrois.
Une condition similaire pourrait être exprimée d’une façon plus générique, sans men-
tionner la matrice T .
|P1i |
Corollaire 6.2. Si ∀i ∈ {1, 2, . . . , k},∃j ∈ {1, 2, . . . , k} tel que |P1i ∩ P2j | > 2 et |P1i ∩
|P2j |
P2j | > 2 , alors la distance de transfert peut être déterminée en O(|S|).
Démonstration. Les conditions de cette hypothèse représentent
P un cas particulier des
conditions du Théorème 6.1. En utilisant (6.3), nous obtenons 1≤`≤k Ti` = 1≤`≤k |P1i ∩
P
105
Chapitre 6. Distance de Transfert : Calcul Rapide et Interprétation Spécifique à la
Coloration
P2` |. Comme tous les classes P2` sont disjointes et ont comme union S, 1≤`≤k |P1i ∩ P2` | =
P
|P1i ∩ S| = |P1i |. Par conséquent, pour chaque ligne i ∈ {1, 2, . . . k}, les équations suivantes
sont valides :
X
Ti` = |P1i |. (6.4)
1≤`≤k
T`j = |P2j |.
X
(6.5)
1≤`≤k
En utilisant les conditions de l’hypothèse, il s’en suit que Tij > Tij1 et Tij > Ti1 j , ∀j1 6=
j, i1 6= i et l’algorithme peut être construit avec le Théorème 6.1.
Théorème 6.3. Si pour une ligne i ∈ {1, 2, . . . , k}, il y a une colonne j ∈ {1, 2, . . . , k}
telle que Tij ≥ Tij1 + Ti1 j ∀j1 6= j, i1 6= i, il existe une affectation maximale σ̄ telle
p que
σ̄(i) = j. Si le nombre de lignes i qui ne satisfont pas cette condition est majoré par 3 |S|,
alors la distance de transfert peut être déterminée en O(|S|).
106
6.3 Calcul de la distance
107
Chapitre 6. Distance de Transfert : Calcul Rapide et Interprétation Spécifique à la
Coloration
6.4 Extensions
Dans le cas où les conditions de l’hypothèse du Théorème 6.3 ou du Corollaire 6.4 sont
satisfaites seulement par un ensemble restreint de lignes i ∈ {1, 2, . . . , k}, il est toujours
possible d’effectuer d’importantes réductions de complexité. Nous prouvons d’abord la
proposition suivante :
|P1i ∪ P2j | 2
|P1i ∩ P2j | ≤ ∀i, j ∈ {1, 2, . . . , k} =⇒ s(P1 , P2 ) ≤ |S|. (6.7)
2 3
Démonstration. Soit σ̄ 0 une affectation maximale et j = σ̄ 0 (i), où i est une ligne quel-
|P i ∪P j | |P i |+|P j |−|P i ∩P j |
i j
conque. On peut écrire Tij ≤ 1 2 2 comme Tij ≤ 1 2
2
1 2
Pij ≤ |P1 | + |P2 |.
, ou 3T
En faisant la somme pour toutes les lignes i ci-dessus, on obtient 3 1≤i≤k Tiσ̄0 (i) ≤
P i
P j
1≤i≤k |P1 | + 1≤j≤k |P2 | = 2|S|, et cela prouve (6.7).
Nous avons utilisé les conditions du Corollaire 6.4 seulement pour une plus grande
lisibilité, mais le même résultat peut être déduit des conditions du Théorème 6.3, car si
|P i ∪P j |
Tij < Tij1 + Ti1 j ∀j1 6= j, i1 6= i, alors |P1i ∩ P2j | ≤ 1 2 2 est également satisfaite – voir
(6.4) et (6.5).
Maintenant, nous présentons la réduction effective du calcul de s(P1 , P2 ) : nous divi-
sons S en sous-ensembles A et B tels que seul le calcul sur B exige un algorithme d’une
complexité plus élevée. Notons I l’ensemble des lignes i tel qu’il existe ji ∈ {1, 2, . . . , k}
j
|P1i ∪P2 i |
tel que |P1i ∩ P2ji | > 2 . Notons J = {j ∈ S : ∃i ∈ I tel que j = ji } et soit :
P1i ∪ P2ji ,
[
A= (6.8)
i∈I
et B = S − A.
En utilisant A dans le raisonnement du Théorème 6.4 ou 6.3, on trouve qu’il y a une
affectation maximale σ̄ qui satisfait σ̄(i) = ji , ∀i ∈ I. Comme J est l’image de I par
la fonction bijective σ̄, alors {1, 2, . . . , k} − J est l’image de {1, 2, . . . , k} − I. Le reste
de σ̄ peut être construit en utilisant uniquement les lignes et les colonnes de ces deux
ensembles, qui contiennent des valeurs produites uniquement par des classes de B (i.e. des
classes P1i , P2j ⊆ B). 5
Notons s(P1 , P2 )|X la similarité entre les partitions P1 et P2 limitées à l’ensemble
X ⊂ S. Nous obtenons s(P1 , P2 ) = s(P1 , P2 )|A + s(P1 , P2 )|B . Comme aucune confusion
n’est possible, nous pouvons simplement écrire : |S| · sP1 ,P2 = |A| · sP1 ,P2 |A + |B| · sP1 ,P2 |B
et il est même possible d’omettre l’indice P1 ,P2 :
|A| |B|
sS = sA + sB ,
|S| |S|
108
6.5 Une étude de cas pour la coloration de graphe
109
Chapitre 6. Distance de Transfert : Calcul Rapide et Interprétation Spécifique à la
Coloration
et 880 pour k = 86 ) paires (P1 , P2 ) telles que d(P1 , P2 ) < |S| 5 et la condition d’hypothèse
du Corollaire 6.4 n’est pas satisfaite. Si nous considérons des distances encore plus petites
(plus exactement, seulement les paires (P1 , P2 ) telles que d(P1 , P2 ) < |S| 10 ) l’algorithme de
temps O(|S|) a été suffisant pour tous les cas que nous avons rencontrés.
L’explication de ce succès pratique se trouve dans le fait que la similarité limitée
à différentes classes de S présente normalement des valeurs assez homogènes. Ainsi, si la
similarité totale est élevée (e.g. si sP1 ,P2 > 0.9 équivalent à d(P1 , P2 ) < |S|
10 ), alors les valeurs
de type sX sont proches de 0.9, pour presque toutes les classes X d’une des partitions.
Ainsi, l’ensemble B sur lequel sB < 23 = 0.66 (et les conditions de la Section 6.3.2 ne sont
pas satisfaites) est très restreint, généralement vide.
Cependant, théoriquement, il est possible de construire un contre-exemple à cela en
prenant deux partitions telles que P11 = P21 et |P11 | = 0.9|S|. Dans ce cas, sP1 ,P2 ≥ 0, 9,
mais les deux partitions, qui sont très similaires sur A = P11 , peuvent être totalement
différentes sur B = S − A. La partie la plus difficile est le calcul de la similarité limitée à
B ; cela peut exiger entre O(k 2 ) et O(k 3 ) opérations.
110
6.6 Remarques finales
1. Σ = 0
2. k = la valeur maximum dans les vecteurs P1 et P2
3. allocation de matrice T (sans initialisation)
4. init. k−vecteurs M et σ̄ à 0 (le maximum sur chaque ligne et l’affectation
maximale à construire)
5. init. k−vecteurs |P1 | et |P2 | à 0 (cela indique la taille de chaque classe)
6. For x = 1 To |S|
– i = P1 (x) et j = P2 (x)
– Tij = 0
7. For x = 1 To |S|
– i = P1 (x) et j = P2 (x)
– incrémenter Tij , |P1i |, |P2j |
– If (Tij > Mi ) Then Mi = Tij et σ̄(i) = j.
8. For i = 1 To k
– If
Mi = 0, Then Continue /*avec le prochain i dans la boucle*/
i σ̄(i)
– If 3Mi ≤ |P1 | + |P2 | Then Return IMPOSSIBLE
– Σ = Σ + Ti,σ̄(i)
9. Return Σ
en une version similaire qui correspond aux autres théorèmes introduits dans ce chapitre.
Le nombre de classes n’a pas besoin d’être le même pour P1 et P2 , parce que k n’est pas
donné en entrée ; k est calculé comme le nombre maximum des classes dans une des deux
partitions (voir Pas 2).
111
Conclusion Générale
Contributions
Nous avons proposé plusieurs approches algorithmiques pour introduire une forme
d’apprentissage dans les stratégies de recherche, dans le but général de rendre les heuris-
tiques classiques “mieux informées”. Pour cela, nous avons utilisé des techniques de fouille
de données (e.g. Multidimensional Scaling) ; de plus, nous avons toujours tenté de fouiller
et exploiter les informations les plus pertinentes pour tout composant d’un algorithme.
Quatre algorithmes ont été testés dans le cadre expérimental très concurrentiel de la co-
loration de graphe. En effet, la coloration est l’un des plus étudiés et des plus connus des
problèmes N P -complets, et ainsi, une dizaine de nouveaux algorithmes heuristiques a été
publiée uniquement pendant cette thèse de trois ans.
Selon l’ordre chronologique de déroulement de thèse, notre premier apport concerne
un algorithme Tabou de base, qui a été amélioré avec de nouvelles fonctions d’évaluation
“bien informées”. En couplant quelques techniques algorithmiques additionnelles – i.e. une
liste Tabou réactive – cette recherche Tabou non sophistiquée peut atteindre des résultats
très performants par rapport à plusieurs algorithmes plus complexes.
Par la suite, l’analyse de la trajectoire de cette recherche locale nous a conduits (Cha-
pitre 3) à l’hypothèse de clusterisation : les meilleures configurations ne sont pas unifor-
mément dispersées dans l’espace de recherche, mais elles sont groupées en clusters qui
peuvent être confinés dans des sphères de rayon R = 10%|V |. Dans le reste de la thèse,
nous avons considéré que deux colorations distantes de moins de R = 10%|V | sont “trop
proches” – il est très facile de passer de l’une à l’autre. Le rayon R est défini en utilisant la
distance de transfert entre partitions ; cette distance est équivalente au nombre minimum
de transitions de voisinage entre colorations, pour notre problème et pour notre voisinage.
Au quatrième chapitre, nous avons présenté deux recherches locales guidées, fondées
sur cette distance et sur la notion de sphère. Le premier algorithme (TS–Div) “est guidé”
vers la diversification. Il mémorise sa propre trajectoire à travers l’espace de recherche
en enregistrant les sphères visitées. De cette manière, il détecte l’instant où le processus
de recherche entre dans une sphère déjà visitée. Quand cela se produit, TS–Div agit afin
d’induire plus de diversification, ce qui permet de quitter plus rapidement cette sphère, et
d’aller continuellement vers de nouvelles régions. Cela peut garantir que TS–Div n’effectue
pas trop d’explorations redondantes à long terme. Comme la liste Tabou interdit des
explorations redondantes à court terme, TS–Div peut couvrir uniformément l’espace de
recherche.
L’algorithme TS–Int est guidé pour l’intensification, afin d’explorer minutieusement un
périmètre limité donné, une région prometteuse spécifique. À partir d’une configuration de
départ, il lance plusieurs processus de recherche locale qui explorent uniquement l’intérieur
de la sphère de la configuration de départ. Un tel processus est arrêté dès qu’il sort de cette
sphère, et “le point de sortie de sphère” est inséré dans une file contenant des centres des
sphères à explorer plus tard. Quand les processus lancés à partir d’un centre de sphère ne
113
Conclusion Générale
6. Toutes les colorations légales mentionnées dans cette thèse sont disponibles en ligne : info.
[Link]/pub/porumbel/graphs/bestcol/
114
Conclusion Générale
Perspectives
L’idée d’utiliser des distances pour construire une recherche guidée semble, dans une
certaine mesure, négligée dans l’optimisation combinatoire. Des techniques à base des dis-
tances ont été appliquées uniquement pour des taches très spécifiques (e.g. croisements de
type distances-preserving, indices de difficulté ou de corrélation fitness-distance). Cepen-
dant, nous pensons que les distances peuvent être employées d’une manière systématique,
à la fois pour comprendre l’espace de recherche, et aussi pour équiper un processus de
recherche avec une “boussole” de navigation/orientation dans l’espace de recherche.
Bien que ces idées n’aient été mises en œuvre et validées que sur le problème de
coloration de graphe, certaines techniques sont très générales et pourraient également être
testées sur d’autres problèmes. Par exemple, comment peut-on savoir si une recherche
locale d’un problème quelconque couvre uniformément l’espace de recherche, ou si elle
exécute plutôt des explorations redondantes ? L’enregistrement de granularité grossière
effectué par TS–Div offre une solution potentielle : en enregistrant un ensemble restreint
de sphères, on peut effectivement inspecter l’évolution de tout processus de recherche et
clarifier ce type de questions. La seule condition pour réaliser cela est de pouvoir calculer
une distance de voisinage, i.e. une distance qui indique le nombre minimum de transitions
de voisinage entre deux configurations – voir plusieurs exemples dans la Section 4.5.
Concernant l’approche évolutionniste, il serait très intéressant de formaliser une stra-
tégie générique d’écart : nous pensons que les idées de contrôle d’écart peuvent être di-
rectement utilisées dans d’autres algorithmes mémétiques. Évidement, pour arriver aux
meilleurs résultats pratiques, il est toujours essentiel d’étudier les détails et les particu-
larités spécifiques du problème, afin d’adapter l’approche. Cependant, comme cela a été
discuté en Section 5.4.4, des idées similaires ont été déjà testées avec succès dans d’autres
communautés évolutionnistes (e.g. optimisation continue multimodale), et ainsi, nous pen-
sons que d’autres progrès importants sont à prévoir.
De plus, un travail plus en profondeur pourrait coupler les idées concernant l’enre-
gistrement du chemin de la recherche locale avec le contrôle d’écart dans l’algorithme
évolutionniste. Tandis que le contrôle d’écart assure qu’il n’y a pas simultanément deux
individus trop proches dans la population, il n’assure pas de propriété similaire sur des
individus appartenant à des générations différentes – ce type de problème pourrait être
évité en enregistrant les sphères des individus à toutes les générations.
115
Liste des figures
2.1 Deux colorations avec le même nombre de conflits mais avec potentiel différent 29
2.2 Évolution typique du nombre de conflits avec plusieurs fonctions d’évaluation . 34
2.3 Histogrammes du nombre de conflits obtenus avec 1000 descentes pures . . . . 36
117
Liste des figures, tableaux et algorithmes
2.1 Moyenne du nombre de conflits après les 1.000.000 premières itérations avec f ,
fe1 et fe2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.2 Résultats détaillés de RCTS avec un temps limite de 10 heures . . . . . . . . . 38
2.3 Résultats du RCTS et des meilleurs algorithmes les plus performants . . . . . . 40
118
Liste des figures, tableaux et algorithmes
119
Références bibliographiques
121
RÉFÉRENCES BIBLIOGRAPHIQUES
I. Blöchliger and N. Zufferey. A graph coloring heuristic using partial solutions and a
reactive tabu scheme. Computers and Operations Research, 35(3) :960–975, 2008.
[Boese et al., 1994] cité page 10
KD Boese, AB Kahng, and S. Muddu. A new adaptive multi-start technique for com-
binatorial global optimizations. Operations Research Letters, 16(2) :101–113, 1994.
[Bouziri et al., 2008] cité page 20
H. Bouziri, E.G. Talbi, and K. Mellouli. A cooperative search method for the k-coloring
problem. Journal of Mathematical Modelling and Algorithms, 7(2) :125–142, 2008.
[Boyan et al., 2000] cité page 8, 9
J. Boyan, W. Buntine, and A. Jagota. Statistical machine learning for large-scale opti-
mization. Neural Computing Surveys, 3(1) :1–58, 2000.
[Brelaz, 1979] cité page 13, 14
D. Brelaz. New methods to color the vertices of a graph. Communications of the ACM,
22(4) :251–256, 1979.
[Brown, 1972] cité page 13
J.R. Brown. Chromatic scheduling and the chromatic number problem. Management
Science, 19(4) :456–463, 1972.
[Burke et al., 1994] cité page 13
E. K. Burke, D. G. Elliman, and R. F. Weare. A university timetabling system based
on graph colouring and constraint manipulation. Journal of Research on Computing in
Education, 27(1) :1–18, 1994.
[Cardoso and Corte-Real, 2005] cité page 100, 101, 101
J.S. Cardoso and L. Corte-Real. Toward a generic evaluation of image segmentation.
IEEE Transactions on Image Processing, 14(11) :1773–1782, 2005.
[Carpaneto and Toth, 1983] cité page 100
G. Carpaneto and P. Toth. Algorithm for the solution of the assignment problem for
sparse matrices. Computing, 31(1) :83–94, 1983.
[Cedeño and Vemuri, 1999] cité page 89, 89, 89
W. Cedeño and V.R. Vemuri. Analysis of speciation and niching in the multi-niche
crowding ga. Theoretical Computer Science, 229(1) :177, 1999.
[Chaitin, 1982] cité page 13
G. J. Chaitin. Register allocation & spilling via graph coloring. In Proceedings of the
1982 SIGPLAN symposium on Compiler construction, pages 98–105, New York, NY,
USA, 1982. ACM.
[Chams et al., 1987] cité page 14
M. Chams, A. Hertz, and D. de Werra. Some experiments with simulated annealing for
coloring graphs. European Journal of Operational Research, 32(2) :260–266, 1987.
[Charon et al., 2006] cité page 100, 101, 103, 103
I. Charon, L. Denoeud, A. Guénoche, and O. Hudry. Maximum transfer distance bet-
ween partitions. Journal of Classification, 23(1) :103–121, 2006.
122
RÉFÉRENCES BIBLIOGRAPHIQUES
123
RÉFÉRENCES BIBLIOGRAPHIQUES
124
RÉFÉRENCES BIBLIOGRAPHIQUES
[Dorne and Hao, 1998b] cité page 14, 14, 25, 25, 33
R. Dorne and J.K. Hao. Tabu search for graph coloring, t-colorings and set t-colorings. In
S. Voss et al., editors, Meta-Heuristics Advances and Trends in Local Search Paradigms
for Optimization, pages 77–92. Kluwer, 1998.
[Dorne, 1998] cité page 13
R. Dorne. Méthodes heuristiques pour la coloration, la T-coloration et l’affectation de
fréquences. PhD thesis, Université de de Montpellier, France, 1998.
[Du and Pardalos, 2007] cité page 42, 60
D. Du and P.M. Pardalos. Handbook of Combinatorial Optimization. Springer, 2007.
[Falkenauer, 1998] cité page 76
E. Falkenauer. Genetic algorithms and grouping problems. John Wiley & Sons, Inc.
New York, NY, USA, 1998.
[Fleurent and Ferland, 1996a] cité page 14, 14, 14, 24, 25, 25, 26, 77
C. Fleurent and J.A. Ferland. Genetic and hybrid algorithms for graph coloring. Annals
of Operations Research, 63(3) :437–461, 1996.
[Fleurent and Ferland, 1996b] cité page 20, 82
C. Fleurent and J.A. Ferland. Object-oriented implementation of heuristic search me-
thods for graph coloring, maximum clique, and satisfiability. In Cliques, Coloring, and
Satisfiability Second DIMACS Implementation Challenge [Johnson and Trick, 1996],
pages 619–652.
[Fotakis et al., 2001] cité page 20
D.A. Fotakis, S.D. Likothanassis, and S.K. Stefanakos. An evolutionary annealing ap-
proach to graph coloring. Proceedings of EvoWorkshops2001—Applications of Evolutio-
nary Computing, 2037 :120–129, 2001.
[Frawley et al., 1992] cité page 1
W.J. Frawley, G. Piatetsky-Shapiro, and C.J. Matheus. Knowledge discovery in data-
bases : An overview. AI Magazine, 13(3) :57–70, 1992.
[Freisleben and Merz, 1996] cité page 88
B. Freisleben and P. Merz. A genetic local search algorithm for solving symmetric
and asymmetric traveling salesman problems. In Proceedings of IEEE International
Conference on Evolutionary Computation, pages 616–621, 1996.
[Funabiki and Higashino, 2000] cité page 19
N. Funabiki and T. Higashino. A minimal-state processing search algorithm for graph
coloring problems. IEICE Transactions on Fundamentals of Electronics, Communica-
tions and Computer Sciences, 83(7) :1420–1430, 2000.
[Galinier and Hao, 1999] cité page 14, 14, 14, 15, 20, 24, 25, 25, 33, 76, 77, 82, 88, 96
P. Galinier and J.K. Hao. Hybrid evolutionary algorithms for graph coloring. Journal
of Combinatorial Optimization, 3(4) :379–397, 1999.
[Galinier and Hertz, 2006] cité page 13, 14, 25
P. Galinier and A. Hertz. A survey of local search methods for graph coloring. Computers
and operations research, 33(9) :2547–2562, 2006.
125
RÉFÉRENCES BIBLIOGRAPHIQUES
[Galinier et al., 2008] cité page 14, 15, 20, 24, 77, 82, 92, 98
P. Galinier, A. Hertz, and N. Zufferey. An adaptive memory algorithm for the k-coloring
problem. Discrete Applied Mathematics, 156(2) :267–279, 2008.
[Galinier, 1999] cité page 13, 26
P. Galinier. Etude des métahueristiques pour la satisfaction de contraintes et la colora-
tion. PhD thesis, Université de Montpellier, France, 1999.
[Gamache et al., 2007] cité page 13
M. Gamache, A. Hertz, and J.O. Ouellet. A graph coloring model for a feasibility pro-
blem in monthly crew scheduling with preferential bidding. Computers and Operations
Research, 34(8) :2384–2395, 2007.
[Gamst and Rave, 1982] cité page 13
A. Gamst and W. Rave. On frequency assignment in mobile automatic telephone sys-
tems. In Proceedings of the IEEE Global Communications Conference, pages 309–315,
1982.
[Garey et al., 1979] cité page 6, 6, 12
M.R. Garey, D.S. Johnson, et al. Computers and Intractability : A Guide to the Theory
of NP-completeness. Freeman, San Francisco, U.S.A., 1979.
[Gebremedhin et al., 2005] cité page 13
A.H. Gebremedhin, F. Manne, and A. Pothen. What color is your jacobian ? graph
coloring for computing derivatives. SIAM Review, 47(4) :629, 2005.
[Gerber et al., 1998] cité page 42
M.U. Gerber, P. Hansen, and A. Hertz. Local optima topology for the 3-sat problem.
Cahiers du GERAD, G–98–68, 1998.
[Glass and Pruegel-Bennett, 2005] cité page 59, 59
C.A. Glass and A. Pruegel-Bennett. A polynomially searchable exponential neighbou-
rhood for graph colouring. Journal of the Operational Research Society, 56(3) :324–330,
2005.
[Glass, 2002] cité page 13
CA Glass. Bag rationalisation for a food manufacturer. Journal of the Operational
Research Society, pages 544–551, 2002.
[Glover and Laguna, 1997] cité page 23
F. Glover and M. Laguna. Tabu Search. Springer, 1997.
[Glover et al., 1996] cité page 20, 30
F. Glover, M. Parker, and J. Ryan. Coloring by tabu branch and bound. In Cliques,
Coloring, and Satisfiability Second DIMACS Implementation Challenge [Johnson and
Trick, 1996], pages 285–307.
[Glover, 1986] cité page 7, 23
F. Glover. Future paths for integer programming and links to artificial intelligence.
Computers and Operations research, 13(5) :533–549, 1986.
[Goldberg and Richardson, 1987] cité page 89, 89, 89
D.E. Goldberg and J. Richardson. Genetic algorithms with sharing for multimodal
126
RÉFÉRENCES BIBLIOGRAPHIQUES
127
RÉFÉRENCES BIBLIOGRAPHIQUES
[Johnson et al., 1991] cité page 14, 14, 17, 17, 18, 31, 72
D.S. Johnson, C.R. Aragon, L.A. McGeoch, and C. Schevon. Optimization by simulated
annealing an experimental evaluation ; part ii, graph coloring and number partitioning.
Operations Research, 39(3) :378–406, 1991.
[Johnson et al., 2002] cité page 15
D. Johnson, A. Mehrotra, and M. Trick. Computational Symposium on Graph Coloring
and Its Generalizations, COLOR02, Cornell University, Ithaca, NY, 2002. ([Link].
[Link]/COLORING02/).
[Johnson et al., 2008] cité page 13, 15
D.S. Johnson, A. Mehrotra, and M.A. Trick. Special issue on computational methods for
graph coloring and its generalizations. Discrete Applied Mathematics, 156(2) :145–146,
2008.
[Jones and Forrest, 1995] cité page 42, 43
T. Jones and S. Forrest. Fitness distance correlation as a measure of problem difficulty
for genetic algorithms. In L. J. Eshelman, editor, Proceedings of the 6th International
Conference on Genetic Algorithms, pages 184–192, 1995.
[Kallel et al., 2001] cité page 42
L. Kallel, B. Naudts, and C. R. Reeves. Properties of fitness functions and search
landscapes. In Theoretical aspects of evolutionary computing, pages 175–206. Springer-
Verlag, London, UK, 2001.
[Karp, 1972] cité page 12
R.M. Karp. Reducibility among combinatorial problems. In R.E. Miller and J.W.
Thatcher, editors, Complexity of Computer Computations, pages 85–103. Plenum Press,
New York, 1972.
[Kauffman and Levin, 1987] cité page 43
S. Kauffman and S. Levin. Towards a general theory of adaptive walks on rugged
landscapes. Journal of theoretical Biology, 128(1) :11, 1987.
[Kendall, 1938] cité page 71
MG Kendall. A new measure of rank correlation. Biometrika, 30(1/2) :81–93, 1938.
[Konovalov et al., 2005] cité page 100, 101, 103
D.A. Konovalov, B. Litow, and N. Bajema. Partition-distance via the assignment pro-
blem. Bioinformatics, 21(10) :2463–2468, 2005.
[Kruskal, 1964] cité page 46, 47
J.B. Kruskal. Multidimensional scaling by optimizing goodness of fit to a nonmetric
hypothesis. Psychometrika, 29(1) :1–27, 1964.
[Kühn, 1955] cité page 100, 103
H.W. Kühn. The hungarian method for the assignment problem. Naval Research Lo-
gistics Quarterly, 2 :83–97, 1955.
[Kuntz et al., 2004] cité page 42
P. Kuntz, B. Pinaud, and R. Lehn. Elements for the description of fitness landscapes
associated with local operators for layered drawings of directed graphs. In Metaheuristics
128
RÉFÉRENCES BIBLIOGRAPHIQUES
129
RÉFÉRENCES BIBLIOGRAPHIQUES
130
RÉFÉRENCES BIBLIOGRAPHIQUES
131
RÉFÉRENCES BIBLIOGRAPHIQUES
132
RÉFÉRENCES BIBLIOGRAPHIQUES
133
Publications
134
Publications
– Daniel Porumbel, Jin-Kao Hao and Pascale Kuntz, A Search Space “Cartography”
for Guiding Graph Coloring Heuristics. Computers & Operations Research, vol. 37
(2010), pp. 769-778.
– Daniel Porumbel, Jin-Kao Hao and Pascale Kuntz, Reinforced Tabu Search for
Graph Coloring.
– Daniel Porumbel, Jin-Kao Hao and Pascale Kuntz, An Efficient Algorithm for Com-
puting the Partition Distance.
– Daniel Porumbel, Jin-Kao Hao and Pascale Kuntz, An Evolutionary Approach with
Diversity Guarantee and Well-Informed Grouping Recombination for Graph Colo-
ring.
– Daniel Porumbel, Jin-Kao Hao and Pascale Kuntz, Diversity Control and Multi-
Parent Recombination for Evolutionary Graph Coloring Algorithms. Proceedings of
Evocop 2009 (9th European Conference on Evolutionary Computation in Combina-
torial Optimisation, Tübingen, Allemagne), LNCS 5482 : 121-132, Springer, 2009.
[parmi les trois articles nominés pour le prix “best paper award”]
– Daniel Porumbel, Jin-Kao Hao and Pascale Kuntz, Position Guided Tabu Search for
Graph Coloring. Selected papers from LION 3 (Learning and Intelligent Optimiza-
tioN conference, Trento, Italie), LNCS 5851 : 148-162, Springer, 2009.
– Daniel Porumbel, Jin-Kao Hao and Pascale Kuntz, A study of evaluation functions
for the graph K-coloring problem. Selected papers from EA’07 (8th International
Conference on Artificial Evolution, Tours, France), LNCS 4926 : 124-135, Springer,
2007.
135
Publications
Exposé invité
– Daniel Porumbel, Reinforced Tabu Search for Graph Coloring, Exposé à
l’équipe d’optimisation ASAP ([Link]), Université de Nottingham,
Royaume Uni, 2008.
136
Algorithmes Heuristiques et Techniques d’Apprentissage
– Applications au Problème de Coloration de Graphe –
Résumé
Au cours des trois dernières décennies, les algorithmes heuristiques ont permis de réa-
liser des progrès remarquables dans la résolution des problèmes difficiles d’optimisation
combinatoire. Cependant, la conception de ces algorithmes relève encore plusieurs chal-
lenges importants – en particulier, il semble qu’il est toujours difficile d’intégrer dans une
heuristique une vue d’ensemble sur l’évolution de la recherche ou sur sa trajectoire. Pre-
nant comme cadre expérimental le problème bien connu de la coloration de graphe, nous
présentons de nouvelles stratégies qui font appel à certains mécanismes d’apprentissage
pour rendre le processus de recherche plus “auto-conscient”. Nous introduisons un algo-
rithme qui est capable d’enregistrer sa trajectoire et d’interpréter sa propre évolution. Une
analyse de l’espace de recherche a montré que les meilleures configurations visitées sont re-
lativement proches les unes des autres, regroupées dans des sphères de rayon fixe. Avec ce
type d’informations apprises, nous avons conçu : (i) des algorithmes de diversification qui
“prennent garde” à ne pas visiter la même sphère à plusieurs reprises, (ii) des algorithmes
d’intensification qui se focalisent sur l’exploration d’un périmètre limité en utilisant un
parcours en largeur des sphères de ce périmètre, et (iii) des approches évolutionnistes pour
gérer la diversité de sorte que les individus soient à la fois de bonne qualité eu égard à
la fonction objectif et suffisamment distants les uns des autres. En fait, nous présentons
une gamme de techniques (e.g. nouvelles fonctions d’évaluation) qui peuvent rendre la
recherche heuristique “bien informée”.
Mots clés : apprentissage et optimisation, enregistrement de la trajectoire de la re-
cherche, intensification, diversité de la population, distance dans l’espace de recherche