No d'ordre

De
Publié par

Niveau: Supérieur, Doctorat, Bac+8
No d'ordre : 2534 THÈSE présentée pour obtenir le titre de DOCTEUR DE L'INSTITUT NATIONAL POLYTECHNIQUE DE TOULOUSE Par : Charles-Edmond BICHOT École doctorale : Informatique et Télécommunications Spécialité : Sûreté du Logiciel et Calcul à Haute Performance Laboratoire d'accueil : Laboratoire d'Optimisation Globale (DSNA/ENAC) ÉLABORATION D'UNE NOUVELLE MÉTAHEURISTIQUE POUR LE PARTITIONNEMENT DE GRAPHE : LA MÉTHODE DE FUSION-FISSION. APPLICATION AU DÉCOUPAGE DE L'ESPACE AÉRIEN Soutenu le 9 novembre 2007 devant le jury composé de : MM. Patrick SIARRY Université Paris XII Rapporteur, Président du jury El-Ghazali TALBI Université de Lille I Rapporteur MM. François PELLEGRINI ENSEIRB Membre du jury Jean-Marc ALLIOT DSNA Membre du jury MM. Joseph NOAILLES ENSEEIHT Directeur de thèse Nicolas DURAND DSNA Codirecteur de thèse

  • partitionnement

  • description formelle du problème du partitionnement de graphe

  • approches infructueuses pour le découpage de l'espace aérien

  • direction des services de la navigation aérienne

  • méthodes classiques de partitionnement de graphe

  • blocs entre pays européens

  • dsna

  • découpage


Publié le : jeudi 1 novembre 2007
Lecture(s) : 63
Source : ethesis.inp-toulouse.fr
Nombre de pages : 232
Voir plus Voir moins

oN d’ordre : 2534
THÈSE
présentée pour obtenir le titre de
DOCTEUR DE L’INSTITUT NATIONAL POLYTECHNIQUE DE TOULOUSE
Par : Charles-Edmond BICHOT
École doctorale : Informatique et Télécommunications
Spécialité : Sûreté du Logiciel et Calcul à Haute Performance
Laboratoire d’accueil : Laboratoire d’Optimisation Globale (DSNA/ENAC)
ÉLABORATION D’UNE NOUVELLE MÉTAHEURISTIQUE POUR LE
PARTITIONNEMENT DE GRAPHE : LA MÉTHODE DE FUSION-FISSION.
APPLICATION AU DÉCOUPAGE DE L’ESPACE AÉRIEN
Soutenu le 9 novembre 2007 devant le jury composé de :
MM. Patrick SIARRY Université Paris XII Rapporteur, Président du jury
El-Ghazali TALBI Université de Lille I
MM. François PELLEGRINI ENSEIRB Membre du jury
Jean-Marc ALLIOT DSNA du jury
MM. Joseph NOAILLES ENSEEIHT Directeur de thèse
Nicolas DURAND DSNA Codirecteur de thèseRésumé : Dans cette thèse, nous étudions des méthodes de partitionnement de graphe et les
appliquons au découpage de l’espace aérien, ainsi qu’à d’autres problèmes. L’espace aérien est composé
de volumes limités, appelés secteurs de contrôle, chacun étant sous la responsabilité d’un contrôleur.
Chaque contrôleur est habilité sur un ensemble de secteurs, appelé zone de qualification. Les secteurs
sont également regroupés en centres de contrôle, qui englobent au moins une zone de qualification.
Dans le cadre du ciel unique européen, la Commission européenne a prévu la création de blocs
fonctionnels d’espace aérien. La création de ces blocs entre pays européens entraînera probablement un
redécoupage des centres actuels. Cette thèse propose des outils d’aide à la conception d’un nouveau
découpage de l’espace européen en centres et en zones de qualification. À cet effet, plusieurs méthodes
sont étudiées : des méthodes de partitionnement classiques, comme l’expansion de région, le
multiniveaux ou les algorithmes de type Kernighan-Lin ; des métaheuristiques, comme le recuit simulé, les
algorithmes de colonies de fourmis et les algorithmes évolutionnaires ; et une nouvelle méthode que
nous avons mise au point, la fusion-fission. C’est cette dernière qui permet de trouver les découpages
les plus performants, au sens de la fonction de coût utilisée, pour le découpage de l’espace aérien.
Afin de diversifier ses applications, nous l’avons aussi adaptée à la segmentation d’images et à la
classification de documents. Enfin, la qualité de cette méthode a été éprouvée sur les bancs de tests
classiques du partitionnement de graphe et confrontée aux méthodes concurrentes. Elle a permis de
trouver pour plusieurs problèmes de test des partitions dont le coût est le plus bas obtenu jusqu’à
présent.
Mots clés : Graphe, partition, fusion-fission, contrôle aérien, métaheuristique, multi-niveaux, affinage,
spectrale
Abstract : This thesis studies graph partitioning methods and applies them to airspace partitioning
and other partitioning problems. Each air traffic controller supervises a limited space, called an air
traffic sector. Controllers have qualifications to work only on a set of sectors, called qualification air
zone. Sectors are grouped together into control centers wich include almost one qualification air zone.
The European single sky project intended by the European Commission could involve a new airspace
partitioning into control centers and qualification air zones. In this framework, this thesis proposes
some tools to design the airspace. Classical graph partitioning methods are studied (load-balancing,
region growing and multilevel algorithms), a well as some metaheuristics (simulated annealing, ant
colonies and evolutionary algorithms). A new method is introduced in this thesis : the fusion-fission
method. Compared with the others, this method allows to find the best airspace partitioning for our
objective function. To diversify its applications, the fusion-fission method has also been applied to
image segmentation and documents clustering. Finally, it has been tested on classical benchmarks
and compared with contestant methods. On benchmarks, it finds some new partitions which have the
lowest cut ever found.
Key words : Graph, partition, fusion-fission, airspace control, metaheuristic, multilevel, load
balancing, spectral
LABORATOIRE D’OPTIMISATION GLOBALE
DIRECTION DES SERVICES DE LA NAVIGATION AÉRIENNE
ÉCOLE NATIONALE DE L’AVIATION CIVILE
7 avenue Édouard Belin - BP 54005
31055 Toulouse cedex 4Remerciements
« Je trouve ici que la pensee´ est un attribut qui m’appartient : elle seule
ne peut etreˆ detach´ ee´ de moi. [. . .] Je ne suis donc, precis´ ement´ parlant,
qu’une chose qui pense»
« De cela memeˆ que je suis une substance, je n’aurais pas neanmoins´
l’idee´ d’une substance infinie, moi qui suis un etreˆ fini, si elle n’avait et´ e´
mise en moi par quelque substance qui futˆ veritablement´ infinie.»
Ren´ e´ Descartes. Les meditations´ sur la philosophie premier` e, 1641.
Merci a` tous ceux qui m’ont aide´ et supporte´ pendant ces trois annees´ de these.` Cette experience´
formidable et tellement enrichissante n’aurait pas et´ e´ possible sans eux, sans vous. Mes premiers
remerciements vont donc a` tous ceux, tres` proches ou lointains, qui ont participe´ a` ma vie pendant
cette periode.´ Cependant, des remerciements specifiques´ meritent´ d’etreˆ adresses´ aux personnes qui
ont particulierement` contribue´ au bon deroulement´ de cette these.`
C’est a` Jean-Marc Alliot et a` Nicolas Durand, par l’intermediaire´ de Pascal Brisset, que je dois
l’opportunite´ d’avoir fait cette these.` En effet, ils m’ont tout d’abord propose´ de realiser´ mon stage
de DEA, appele´ maintenant master recherche, au sein du Laboratoire d’optimisation globale, puis ils
ont eu la gentillesse de m’accepter en these,` de me laisser beaucoup d’autonomie, ce qui m’a permis
d’explorer mes propres chemins de recherche, de relire mes papiers et de me permettre d’aller a` de
nombreuses conferences.´ Je leur suis vraiment reconnaissant pour tout cela.
J’ai eu la chance d’avoir pour rapporteurs Patrick Siarry qui ma si souvent utilement conseille´
pendant celle-ci et El-Ghazali Talbi qui a toujours soutenu mes travaux ; je voudrais les remercier tout
particulierement.` Ma gratitude va aussi a` Joseph Noailles, mon directeur officiel de these` et a` Franc ¸ois
Pellegrini pour ses remarques sur ma these` et mon annee´ de post-doctorat dans son equipe.´
Merci aussi a` tous les membres du LOG, de la DSNA/DTI, du LEEA et de l’ENAC avec qui j’ai
et´ e´ en contact et qui m’ont si bien accueilli parmi eux. J’ai une pensee´ toute particuliere` pour Nicolas
Archambault qui doit faire face au terrible accident qu’il a eu. Je voudrais aussi remercier chaudement
Jean-Baptiste Gotteland qui a toujours tres` gentiment supporte´ mes fantaisies en tant que collegue` de
bureau, Pascal Brisset pour ses conseils varies´ allant du Caml au nutritionel, Nicolas Barnier pour
ses debats´ passionnes,´ Thomas Riviere` pour bomberman, David Gianazza pour ses relectures, Estelle
Malavolti pour sa bonne humeur et Kevin´ Guittet pour nos petites soirees´ au London Town. Je souhaite
maintenant beaucoup de bons moments et de persev´ erance´ a` Pierre-Selim´ Huard et Cyril Allignol qui
sont les nouveaux doctorants du laboratoire.Si mes remerciements sont profonds et sinceres` a` tous ceux qui etaient´ pres` de moi sur le plan
professionnel, ils sont tout aussi et sinceres` a` ceux qui m’ont entoures´ sur le plan familial
et amical. Je remercie toute ma famille et specialement´ mes parents pour leur soutient et je souhaite
beaucoup d’endurance a` ma mere` qui est en train de passer sa these.` Je remercie vivement tous mes
´ ´amis, ceux qui ont compris ma mauvaise disponibilite, ceux qui ont eu la patience d’ecouter mes
idees,´ et je remercie en particulier mes amis toulousains qui ont si bien su me supporter pendant cette
periode.´ Enfin, je remercie ma future femme, Caroline, qui a su etreˆ si patiente pendant la duree´ de
ma these` et a` qui je dedie´ celle-ci.Table des matières
Introduction générale 1
1 Introduction au problème du partitionnement de graphe 7
1.1 Notions mathématiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Description formelle du problème du partitionnement de graphe . . . . . . . . . . . 12
1.4 Fonctions objectifs pour le partitionnement de graphe . . . . . . . . . . . . . . . . . 14
1.5 Le partitionnement contraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.6 Le non contraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.7 Généralités liées au partitionnement . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.7.1 Différences entre contraint et non contraint . . . . . . . . . 18
1.7.2 Affinage et répartition de charge d’une partition . . . . . . . . . . . . . . . . 18
1.7.3 Technique de la bissection récursive . . . . . . . . . . . . . . . . . . . . . . 19
1.8 NP-difficulté des problèmes de partitionnement . . . . . . . . . . . . . . . . . . . . 20
1.8.1 Le cas du partitionnement contraint . . . . . . . . . . . . . . . . . . . . . . 20
1.8.2 Le cas du non contraint . . . . . . . . . . . . . . . . . . . . 21
1.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
I Méthodes de partitionnement de graphe 23
2 Méthodes classiques de partitionnement de graphe 25
2.1 Approches infructueuses pour le découpage de l’espace aérien . . . . . . . . . . . . 25
2.1.1 Solution exacte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1.2 Flux maximum - coupe minimum . . . . . . . . . . . . . . . . . . . . . . . 26
2.1.3 Méthodes de classification . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.1.4 Autres approches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2 Les méthodes d’expansion de région . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2.1 Graph growing Algorithm (GGP) . . . . . . . . . . . . . . . . . . . . . . . 28
2.2.2 Greedy graph growing Algorithm (GGGP) . . . . . . . . . . . . . . . . . . 28
2.3 La méthode spectrale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.1 Présentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.2 Quelques résultats d’analyse numérique . . . . . . . . . . . . . . . . . . . . 30
2.3.3 Trouver les valeurs propres de la matrice Laplacienne du graphe . . . . . . . 31
2.3.4 Borne inférieure pour le partitionnement de graphe contraint . . . . . . . . . 32
2.3.5 Méthodes spectrales pour le contraint . . . . . . . . . . . . 33
iii TABLEDESMATIÈRES
2.3.6 Méthodes spectrales pour le partitionnement non contraint . . . . . . . . . . 33
2.3.7 Problèmes et améliorations . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.4 L’algorithme de Kernighan-Lin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.4.1 Principe général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.4.2 L’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.4.3 Améliorations proposées par Brian Kernighan et Shen Lin . . . . . . . . . . 37
2.4.4 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.4.5 Parties de tailles différentes . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.4.6 Sommets de poids différents . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.5 Améliorations de l’algorithme de Kernighan-Lin . . . . . . . . . . . . . . . . . . . 38
2.5.1 L’implémentation de Fiduccia-Mattheyses . . . . . . . . . . . . . . . . . . . 38
2.5.2 Adaptation auk-partitionnement . . . . . . . . . . . . . . . . . . . . . . . . 40
2.5.3 Global Kernighan-Lin refinement . . . . . . . . . . . . . . . . . . . . . . . 41
2.5.4 Algorithme d’affinage de Walshaw-Cross . . . . . . . . . . . . . . . . . . . 42
2.6 La méthode multi-niveaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.6.2 Principe de la méthode multi-niveaux . . . . . . . . . . . . . . . . . . . . . 45
2.6.3 Contraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.6.4 Partitionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.6.5 Affinage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.7 Nouveaux algorithmes issus des méthodes classiques . . . . . . . . . . . . . . . . . 51
2.7.1 La percolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.7.2 Algorithme de répartition de charge . . . . . . . . . . . . . . . . . . . . . . 53
2.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3 Différentes métaheuristiques appliquées au partitionnement de graphe 59
3.1 Introduction générale sur les métaheuristiques . . . . . . . . . . . . . . . . . . . . . 59
3.2 Le recuit simulé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.2.1 Description de l’algorithme du recuit simulé . . . . . . . . . . . . . . . . . . 60
3.2.2 Notre adaptation du recuit simulé au partitionnement de graphe . . . . . . . 62
3.3 Les algorithmes de colonies de fourmis . . . . . . . . . . . . . . . . . . . . . . . . 65
3.3.1 Introduction aux algorithmes de colonies de fourmis . . . . . . . . . . . . . 66
3.3.2 Notre adaptation des colonies de fourmis au partitionnement non contraint . . 67
3.4 Les algorithmes évolutionnaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.4.1 Principe des algorithmes évolutionnaires . . . . . . . . . . . . . . . . . . . 71
3.4.2 Nos adaptations des algorithmes évolutionnaires au partitionnement de graphe 76
3.5 Métaheuristiques hybrides pour le partitionnement contraint . . . . . . . . . . . . . 80
3.5.1 Présentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.5.2 Algorithme évolutionnaire multi-niveaux de Soper-Walshaw-Cross . . . . . 81
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4 Élaboration d’une nouvelle métaheuristique : la méthode de fusion-fission 85
4.1 Quelques notions de physique nucléaire . . . . . . . . . . . . . . . . . . . . . . . . 85
4.2 Les bases de la fusion-fission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.3 Application au partitionnement non contraint . . . . . . . . . . . . . . . . . . . . . 90
4.3.1 Mise en place de la méthode . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.3.2 Le mécanisme de règle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91TABLEDESMATIÈRES iii
4.3.3 Fonction d’adaptation de la fonction de coût . . . . . . . . . . . . . . . . . . 92
4.3.4 Le processus d’initialisation . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.3.5 Le d’optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.3.6 Fonctions de choix entre fusion et fission . . . . . . . . . . . . . . . . . . . 94
4.3.7 Fusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.3.8 Fission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.3.9 Paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
4.4 Application au partitionnement contraint . . . . . . . . . . . . . . . . . . . . . . . . 100
4.4.1 Présentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.4.2 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.4.3 Choix de l’algorithme multi-niveaux . . . . . . . . . . . . . . . . . . . . . . 104
4.4.4 Création de la séquence des nombres de parties . . . . . . . . . . . . . . . . 104
4.4.5 Choix de l’algorithme d’affinage . . . . . . . . . . . . . . . . . . . . . . . . 105
4.4.6 Améliorations apportées à l’algorithme . . . . . . . . . . . . . . . . . . . . 106
4.4.7 Autres améliorations possibles de l’algorithme . . . . . . . . . . . . . . . . 108
4.5 Perspectives futures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
II Découpage de l’espace aérien et autres applications 111
5 Application des méthodes de partitionnement de graphe au découpage de l’espace aérien
européen 113
5.1 Structure de l’espace aérien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.1.1 Le réseau de routes aériennes . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.1.2 Le rôle du contrôleur aérien et la sectorisation de l’espace aérien . . . . . . . 115
5.2 Le problème du découpage de l’espace aérien . . . . . . . . . . . . . . . . . . . . . 120
5.2.1 La création de blocs d’espace aérien fonctionnels en Europe . . . . . . . . . 120
5.2.2 La d’un bloc fonctionnel en Europe centrale . . . . . . . . . . . . . 122
5.3 Modélisation du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.3.1 Charge de contrôle dans un secteur . . . . . . . . . . . . . . . . . . . . . . 123
5.3.2 Un objectif : minimiser la charge de travail des contrôleurs . . . . . . . . . . 123
5.3.3 Deux contraintes : la taille des zones et des centres . . . . . . . . . . . . . . 124
5.3.4 Analyse et traitement des données du trafic aérien européen . . . . . . . . . 126
5.3.5 Graphe du trafic aérien européen et adaptation au partitionnement . . . . . . 127
5.4 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
5.4.1 Comparaison avec les métaheuristiques . . . . . . . . . . . . . . . . . . . . 128
5.4.2 avec des outils « classiques » de partitionnement . . . . . . . . 131
5.4.3 Découpage de l’espace aérien français . . . . . . . . . . . . . . . . . . . . . 135
5.4.4 de aérien du bloc fonctionnel d’Europe centrale . . . . . 138
5.4.5 Découpage de l’espace aérien de la core area européenne . . . . . . . . . . . 143
5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
6 Application de la méthode de fusion-fission à d’autres problèmes de partitionnement non
contraints 151
6.1 La segmentation d’images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
6.1.1 Présentation du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151iv TABLEDESMATIÈRES
6.1.2 Application de la méthode de fusion-fission . . . . . . . . . . . . . . . . . . 152
6.1.3 Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
6.2 La classification de documents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
6.2.1 Présentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
6.2.2 Modélisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
6.2.3 Extraction des mots d’un document et analyse lexicale . . . . . . . . . . . . 157
6.2.4 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
6.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
7 Application de la méthode de fusion-fission au partitionnement contraint 161
7.1 Robustesse de la fusion-fission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
7.2 Gains de performance apportés par la fusion-fission . . . . . . . . . . . . . . . . . . 165
7.3 Améliorations de l’algorithme de . . . . . . . . . . . . . . . . . . . . 168
7.4 Meilleurs résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
7.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
Conclusions et perspectives 185
Annexes 189
A Les principaux outils et bancs de tests pour le partitionnement de graphe 191
A.1 Les outils pour le partitionnement contraint . . . . . . . . . . . . . . . . . . . . . . 191
A.1.1 Chaco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
A.1.2 Metis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
A.1.3 Scotch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
A.1.4 Jostle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
A.1.5 Party . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
A.2 Les outils pour le partitionnement non contraint . . . . . . . . . . . . . . . . . . . . 193
A.2.1 Graclus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
A.3 Performance des différents algorithmes multi-niveaux . . . . . . . . . . . . . . . . . 194
A.4 Archives du partitionnement de graphe de Chris Walshaw . . . . . . . . . . . . . . . 194
B Compléments sur le système de gestion du trafic aérien 203
B.1 Les contrôleurs des centres de contrôle en route . . . . . . . . . . . . . . . . . . . . 203
B.2 La régulation du trafic aérien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
Glossaire 209
Références bibliographiques 212Introduction générale
Cette thèse a pour but d’apporter des méthodes et des outils pour le redécoupage de l’espace aérien
européen. Elle s’est effectuée sous la direction de Nicolas Durand, au Laboratoire d’optimisation
globale de la Direction des services de la navigation aérienne (DSNA) et de l’École nationale de
l’aviation civile (ENAC). Le découpage de l’espace aérien se modélise sous la forme d’un problème
de partitionnement de graphe. Nous avons donc cherché à étudier ce domaine qui a été peu abordé
dans notre laboratoire. Ainsi, le sujet s’est progressivement orienté vers l’étude et la recherche de
méthodes de partitionnement. Le découpage de l’espace aérien européen a cependant toujours été
notre problématique centrale.
Plusieurs méthodes sont présentées dans cette thèse : des méthodes de partitionnement classiques,
comme l’expansion de région, le multi-niveaux ou les algorithmes de type Kernighan-Lin ; des
métaheuristiques, comme le recuit simulé, les algorithmes de colonies de fourmis et les algorithmes
évolutionnaires ; et une nouvelle méthode que nous avons mise au point, la fusion-fission. Comme
cette dernière a permis de trouver les découpages de l’espace aérien les plus performants, au sens de
la fonction de coût utilisée, nous avons voulu diversifier ses applications. Ainsi, elle a été adaptée à la
segmentation d’images et à la classification de documents. Afin de tester la qualité de cette méthode,
nous l’avons aussi éprouvée sur les bancs de tests classiques du partitionnement de graphe.
La démarche que nous avons suivie au cours de cette thèse nous a influencés dans l’organisation
de ce document. Ainsi, nous étudierons dans un premier temps les méthodes de partitionnement,
puis dans un second temps nous présenterons leur application aux problèmes du trafic aérien, de la
segmentation d’image, de la classification de documents et des bancs de tests classiques.
Le partitionnement
Le mot « » est un néologisme correspondant au mot anglais partitioning, qui
désigne l’action de créer une partition. La partition est le résultat de la division en parties d’un ensemble.
En mathématiques, une partition d’un ensemble E est une famille de parties de E, disjointes deux à
deux et dont la réunion est l’ensemble E. Tout élément de E appartient donc à une et une seule de ces
parties.
Le partitionnement est utilisé pour résoudre un grand nombre de problèmes d’ingénierie. Les
exemples d’applications du partitionnement sont multiples : l’exploration de données, la conception
de circuits intégrés électroniques, la répartition de charge pour les machines parallèles, la dynamique
des fluides, le calcul matriciel, le trafic aérien, etc.
Créer une partition consiste à répartir un ensemble d’objets en plusieurs sous-ensembles. Dans le
but de répartir les objets dans ces différents sous-ensembles, il peut être utile de pouvoir les comparer
entre eux. Ainsi, chaque objet va être associé à d’autres objets, et les associations résultantes, ou
liens, devront pouvoir être quantifiées. De plus, si l’ensemble des ces objets est fini, ou au moins
12 INTRODUCTIONGÉNÉRALE
dénombrable, alors toutes les conditions sont réunies pour créer un graphe de ces objets, c’est-à-dire
concrétiser les associations entre objets. Il ne reste plus qu’à construire une partition de ce graphe.
L’objectif du partitionnement d’un ensemble d’objets est en général de répartir ceux-ci en parties ayant
de très forts liens internes et de faibles liens entre les parties. C’est ce que l’on appelle l’objectif du
partitionnement ou fonction objectif. Cette fonction objectif varie selon le problème précis à résoudre.
Le problème du partitionnement de graphe est commun à plusieurs disciplines :
– il fait partie des problèmes de théorie des graphes et par là même des mathématiques discrètes.
Les mathématiques discrètes sont l’étude des structures discrètes, c’est-à-dire des ensembles
finis ou dénombrables ;
– il appartient aussi aux problèmes d’optimisation combinatoire. Un problème d’optimisation
combinatoire consiste à trouver la meilleure solution au sein d’un ensemble discret de solutions ;
– il est résolu grâce aux outils informatiques.
Le partitionnement de graphe se situe donc à cheval entre l’informatique et les mathématiques
appliquées. Les mathématiques discrètes et l’optimisation combinatoire sont liées à la recherche
opérationnelle. La recherche opérationnelle est une discipline transversale qui regroupe les
appliquées, l’informatique et les sciences de l’ingénieur. Son but est de résoudre des problèmes de
décision complexes issus du monde réel, en particulier des problèmes d’optimisation. Le
partitionnement de graphe est un problème de recherche opérationnelle.
Notre contribution
Notre contribution à l’avancement des connaissances nous paraît s’organiser suivant quatre axes :
– cette thèse présente un état de l’art du partitionnement de graphe. Cette spécialité n’étant pas
présente dans notre laboratoire, il nous a fallu en premier lieu identifier parmi les différentes
méthodes de partitionnement, celles qui concernaient les graphes. Puis nous avons classifié les restantes en plusieurs catégories : multi-niveaux, spectrales, expansion de région,
affinage, etc. Enfin, la présentation de cet état de l’art est le fruit d’une analyse critique de ces
méthodes. En plus de l’état de l’art du partitionnement de graphe, cette thèse comporte une
présentation détaillée de trois métaheuristiques : le recuit simulé, les algorithme de colonies de
fourmis et les algorithmes évolutionnaires ;
– plusieurs innovations sont apportées par cette thèse. La principale est la création de la méthode
de fusion-fission et des deux algorithmes de partitionnement de graphe qui en découlent.
Cependant, d’autres nouveaux pour le partitionnement de graphe sont aussi proposés :
l’algorithme basé sur la percolation, l’algorithme de répartition de charge utilisant la notion de
gain de Kernighan-Lin, les deux algorithmes de recuit simulé pour le partitionnement,
l’algorithme de colonies de fourmis pour le partitionnement, ainsi que les trois algorithmes
évolutionnaires pour le partitionnement ;
– nous avons appliqué le de graphe à de nombreux problèmes. Parmi ces
applications, la principale est le problème du découpage de l’espace aérien européen. Si cette
dernière a nécessité l’étape de modélisation la plus complexe et la plus longue, toutes ces
applications ont demandé une phase de modélisation importante. Puis a succédé à la modélisation
de ces problèmes, l’étape d’adaptation des méthodes de partitionnement ;
– enfin, des nombreuses évaluations sont présentées dans cette thèse. Celles-ci permettent de
comparer la performance des méthodes, notamment grâce à l’utilisation de bancs de tests
classiques ; d’évaluer l’adaptation des méthodes au partitionnement de graphe, en particulier pour
les métaheuristiques ; d’éprouver les modélisations des problèmes traités ; et de vérifier la per-

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.