95
Master en Sciences de la Modélisation, de l’Information et des Systèmes Spécialité Sûreté du Logiciel et Calcul Haute Performance ÉTABLISSEMENT : École Nationale Supérieure de l’Aéronautique et de l’Espace LABORATOIRE : Laboratoire d’optimisation globale (ENAC/DTI–SDER) S UJET DU MÉMOIRE : Résolution de conflits par algorithmes stochastiques parallèles Février à juillet 2006 à Toulouse Auteur : Xavier OLIVE [email protected] Maître de stage : Nicolas DURAND [email protected] Directeur de recherche : Jean-Marc ALLIOT [email protected] RÉSUMÉ : Dans ce mémoire, nous étudierons comment les algorithmes à colonies de fourmis permettent de résoudre des conflits aériens. Afin d’optimiser les temps de convergence, nous développerons plusieurs méthodes de paral- lélisation. Enfin, nous testerons ces méthodes sur d’autres problèmes classiques : voyageur de commerce, satisfaisabilité. MOTS CLÉS : Résolution de conflits aériens Algorithmes de colonies de fourmis Algorithmes parallèles

Résolution de conflits par algorithmes stochastiques parallèles

  • Upload
    others

  • View
    5

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Résolution de conflits par algorithmes stochastiques parallèles

Master en Sciences de la Modélisation, de l’Information et des SystèmesSpécialité Sûreté du Logiciel et Calcul Haute Performance

ÉTABLISSEMENT : École Nationale Supérieure de l’Aéronautique et de l’Espace

LABORATOIRE : Laboratoire d’optimisation globale (ENAC/DTI–SDER)

SUJET DU MÉMOIRE :

Résolution de conflits par algorithmesstochastiques parallèles

Février à juillet 2006 à Toulouse

Auteur : Xavier OLIVE [email protected]ître de stage : Nicolas DURAND [email protected] de recherche : Jean-Marc ALLIOT [email protected]

RÉSUMÉ :

Dans ce mémoire, nous étudierons comment les algorithmes à colonies defourmis permettent de résoudre des conflits aériens. Afin d’optimiser lestemps de convergence, nous développerons plusieurs méthodes de paral-lélisation.Enfin, nous testerons ces méthodes sur d’autres problèmes classiques :voyageur de commerce, satisfaisabilité.

MOTS CLÉS :

– Résolution de conflits aériens– Algorithmes de colonies de fourmis– Algorithmes parallèles

Page 2: Résolution de conflits par algorithmes stochastiques parallèles
Page 3: Résolution de conflits par algorithmes stochastiques parallèles

Remerciements

Je souhaite remercier le laboratoire d’optimisation globale de l’ENAC, qui m’a accueilliet financé pendant 6 mois de stage, en mettant à ma disposition tous les moyens qu’il avaitpour me permettre de mener à bien mon travail.

Parmi les membres du laboratoire que je ne pourrais pas tous citer, je remercie en parti-culier :

– Jean-Marc ALLIOT, chef du laboratoire, qui m’a proposé ce sujet et encadré dans lesmoments où « ça bloque ! »

– Nicolas DURAND, qui m’a aiguillé dès le début du stage, et a relu mes nombreusesversions de ce rapport.

– Nicolas BARNIER et Pascal BRISSET qui ont toujours été disponibles pour des conseilstechniques.

J’en profite pour m’excuser également auprès des personnes victimes des désagrémentscausés par les fourmis venues spécialement parasiter leurs ressources matérielles.

Par ailleurs, j’adresse un clin d’œil à Cyril ALLIGNOL et Pierre-Selim HUARD, stagiairesau même titre que moi, compagnons de galère, brillants par notre médiocrité dans l’utilisa-tion du pavé numérique au retour du déjeuner.

Côté SUPAERO, je remercie spécialement Christophe GARION qui m’a encadré pendantplus d’une année de cours et solidement soutenu sur tous mes projets.Je remercie également Pierre SIRON, responsable de mon stage à SUPAERO.

Côté ENSEEIHT, je souhaite particulièrement remercier Gérard PADIOU, responsable duMaster 2 Recherche SLCP, pour le soutien sans réserve qu’il m’a fourni pour mes projets auJapon.

À ceux qui ont relu et corrigé ce rapport,À ceux que j’ai oubliés, et qui se reconnaîtront,

Merci !

iii

Page 4: Résolution de conflits par algorithmes stochastiques parallèles
Page 5: Résolution de conflits par algorithmes stochastiques parallèles

Table des matières

Introduction 1

I Les algorithmes et le choix du problème 3

1 Les algorithmes d’optimisation par colonies de fourmis 51.1 L’algorithme de base : le « Ant System » . . . . . . . . . . . . . . . . . . . . . . . 5

1.1.1 Origines biologiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.1.2 Description de l’algorithme : problème du voyageur de commerce . . 61.1.3 Résultats sur des problèmes traditionnels . . . . . . . . . . . . . . . . . 7

1.2 Une amélioration de l’AS : le « Ant Colony System (ACS) » . . . . . . . . . . . . 121.2.1 Description théorique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.2.2 Comparaison de l’AS et de l’ACS . . . . . . . . . . . . . . . . . . . . . . 13

2 Introduction aux problèmes de résolutions de conflits 152.1 Contexte du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.1.1 Les niveaux de gestion du trafic aérien . . . . . . . . . . . . . . . . . . 152.1.2 Contraintes du problème . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.2 Complexité du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.3 Méthodes de résolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.3.1 Approche par algorithmes génétiques . . . . . . . . . . . . . . . . . . . 172.3.2 Programmation par contraintes . . . . . . . . . . . . . . . . . . . . . . . 17

3 Résolution de conflits par colonies de fourmis 193.1 Description du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.2 Intérêt de l’approche par colonies de fourmis . . . . . . . . . . . . . . . . . . . 203.3 Description de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.3.1 Structure du graphe des chemins, comportement d’une fourmi . . . . 213.3.2 Dépôt des phéromones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.4 Résultats obtenus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.4.1 Premiers résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.4.2 Aide à la convergence, relaxation de contraintes . . . . . . . . . . . . . 223.4.3 Résultats pour 30 avions . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

v

Page 6: Résolution de conflits par algorithmes stochastiques parallèles

Table des matières

II Parallélisation du problème de gestion du trafic aérien 27

4 Parallélisation de l’algorithme : modèle client–serveur 294.1 Un premier modèle simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.1.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294.1.2 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.2 Optimisation de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.2.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.2.2 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

5 Optimisation par multithreading 355.1 Multithreading du serveur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

5.1.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355.1.2 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

5.2 Asynchronisation des clients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365.2.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365.2.2 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

5.3 Optimisation du volume de données transmises . . . . . . . . . . . . . . . . . 365.4 Évaluation de la méthode – Mesures . . . . . . . . . . . . . . . . . . . . . . . . 40

6 Choix du mode de communication 456.1 Description théorique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

6.1.1 Parallel Virtual Machine, PVM . . . . . . . . . . . . . . . . . . . . . . . 456.1.2 Message Passing Interface, MPI . . . . . . . . . . . . . . . . . . . . . . . 45

6.2 Comparaison sur le problème multithreadé, client simple . . . . . . . . . . . . 466.3 Interface ad hoc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

7 Parallélisation de l’algorithme : modèle par îlots 497.1 Description du modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497.2 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

7.2.1 Le conflit à 30 avions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517.2.2 Le conflit à 25 avions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

7.3 Mode de communication ad hoc . . . . . . . . . . . . . . . . . . . . . . . . . . 527.3.1 Exigences vis-à-vis du protocole . . . . . . . . . . . . . . . . . . . . . . 537.3.2 Description du protocole . . . . . . . . . . . . . . . . . . . . . . . . . . 537.3.3 Description du nouvel algorithme . . . . . . . . . . . . . . . . . . . . . 537.3.4 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547.3.5 Mise en évidence et intérêt de l’îlotisme . . . . . . . . . . . . . . . . . . 557.3.6 Comparaison des méthodes pour différentes tailles de problèmes . . . 55

7.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

8 Parallélisation de l’algorithme : modèle mixte 578.1 Description du modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578.2 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578.3 Bancs d’essai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

vi

Page 7: Résolution de conflits par algorithmes stochastiques parallèles

Table des matières

III Parallélisation de l’algorithme sur d’autres problèmes 63

9 Parallélisation du problème du voyageur de commerce 659.1 L’algorithme client-serveur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 659.2 L’algorithme par îlots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 679.3 L’algorithme mixte, îlots de clients-serveurs . . . . . . . . . . . . . . . . . . . . 67

10 Problèmes SAT et CSP 6910.1 Présentation des problèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

10.1.1 Les problèmes SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6910.1.2 Les problèmes CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

10.2 Résolution par algorithme à colonies de fourmis . . . . . . . . . . . . . . . . . 7010.2.1 Résolution d’un problème SAT . . . . . . . . . . . . . . . . . . . . . . . 7010.2.2 Résolution d’un problème CSP . . . . . . . . . . . . . . . . . . . . . . . 70

10.3 Bancs d’essai sur exécution locale . . . . . . . . . . . . . . . . . . . . . . . . . . 7010.3.1 Problème aim-50-1_6-yes1-1 . . . . . . . . . . . . . . . . . . . . . . 7110.3.2 Problème aim-100-1_6-yes1-1 . . . . . . . . . . . . . . . . . . . . . 7110.3.3 Conclusion de l’exécution sur l’algorithme local . . . . . . . . . . . . . 71

10.4 Modèle parallèle client-serveur . . . . . . . . . . . . . . . . . . . . . . . . . . . 7110.4.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7110.4.2 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

10.5 Modèle parallèle par îlots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7110.5.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7110.5.2 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

10.6 Cas défavorables à l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

11 Comparaison des modèles de parallélisation 7711.1 Caractéristiques des problèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

11.1.1 Le problème de résolution de conflits . . . . . . . . . . . . . . . . . . . 7711.1.2 Le problème du voyageur de commerce . . . . . . . . . . . . . . . . . . 7811.1.3 Le problème de satisfaisabilité . . . . . . . . . . . . . . . . . . . . . . . 78

11.2 Les modèles d’algorithmes parallèles . . . . . . . . . . . . . . . . . . . . . . . . 7811.2.1 Le modèle client-serveur . . . . . . . . . . . . . . . . . . . . . . . . . . . 7811.2.2 Le modèle par îlots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7811.2.3 Le modèle mixte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

11.3 Adéquation des modèles aux problèmes . . . . . . . . . . . . . . . . . . . . . . 7911.3.1 Le problème de résolution de conflits et le modèle mixte . . . . . . . . 7911.3.2 Le problème TSP et le modèle par îlots . . . . . . . . . . . . . . . . . . 7911.3.3 Le problème SAT et le modèle par îlots . . . . . . . . . . . . . . . . . . 79

Conclusion 81

Bibliographie 83

vii

Page 8: Résolution de conflits par algorithmes stochastiques parallèles
Page 9: Résolution de conflits par algorithmes stochastiques parallèles

Table des algorithmes

1 Algorithme de colonies de fourmis : le problème du voyageur de commerce . 72 Algorithme de résolution de conflit (en local) . . . . . . . . . . . . . . . . . . . 293 Algorithme de résolution de conflit (en parallèle) . . . . . . . . . . . . . . . . . 304 Algorithme de résolution de conflit optimisé (en parallèle) . . . . . . . . . . . . 335 Envoi de message par PVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466 Algorithme de résolution de conflit (modèle par îlots) . . . . . . . . . . . . . . 507 Algorithme de résolution de conflit (modèle par îlots UDP) . . . . . . . . . . . 54

ix

Page 10: Résolution de conflits par algorithmes stochastiques parallèles
Page 11: Résolution de conflits par algorithmes stochastiques parallèles

Table des figures

1.1 Sélection des branches les plus courtes par colonie de fourmi . . . . . . . . . . 61.2 Algorithme de colonies de fourmi : le voyageur de commerce . . . . . . . . . 71.3 TSP : 94 préfectures françaises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.4 TSP : 48 capitales des États-Unis . . . . . . . . . . . . . . . . . . . . . . . . . . 91.5 TSP : 48 capitales des États-Unis . . . . . . . . . . . . . . . . . . . . . . . . . . 91.6 TSP : 94 préfectures françaises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3.1 Problème de n avions en conflit . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.2 Intérêt de l’approche « colonie de fourmis » . . . . . . . . . . . . . . . . . . . . 203.3 Différents états des fourmis lors du parcours du graphe . . . . . . . . . . . . . 213.4 Automate représentant les états possibles d’une fourmi . . . . . . . . . . . . . 213.5 Relaxation de contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.6 Conflit à 5 avions : convergence de l’algorithme de colonies de fourmis . . . . 243.7 Conflit à 30 avions : convergence de l’algorithme de colonies de fourmis . . . 253.8 Vitesse de convergence de l’algorithme de colonies de fourmis . . . . . . . . . 25

4.1 Principe de communication client–serveur . . . . . . . . . . . . . . . . . . . . 304.2 Principe de communication client–serveur (optimisé) . . . . . . . . . . . . . . 314.3 Conflit à 30 avions par un modèle client–serveur optimisé . . . . . . . . . . . 324.4 Algorithme local et algorithme client–serveur : comparaison des performances 334.5 Modèle client–serveur : trace des communications entre processus . . . . . . . 34

5.1 Principe de fonctionnement du serveur multithreadé . . . . . . . . . . . . . . 375.2 Modèle client–serveur multithreadé : trace des communications entre processus 375.3 Modèle client–serveur multithreadé : comparaison des performances . . . . . 385.4 Principe de fonctionnement des clients et serveurs multithreadés . . . . . . . 385.5 Modèle client–serveur multithreadé, serveur asynchrone : trace des commu-

nications entre processus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395.6 Modèle client–serveur multithreadé, serveur asynchrone : comparaison des

performances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395.7 Représentation d’un trail creux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415.8 Vitesse de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425.9 Qualité de la solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425.10 Qualité de la solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

xi

Page 12: Résolution de conflits par algorithmes stochastiques parallèles

Table des figures

7.1 Principe de fonctionnement du modèle par îlots . . . . . . . . . . . . . . . . . 507.2 Algorithme par îlots : problème à 30 avions . . . . . . . . . . . . . . . . . . . . 517.3 Caractéristique d’une résolution locale du problème . . . . . . . . . . . . . . . 527.4 Algorithme par îlots, envoi UDP : problème à 25 avions . . . . . . . . . . . . . 547.5 Algorithme par îlots, envoi UDP : problème à 25 avions — État des îlots à un

instant donné . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

8.1 Principe de fonctionnement du modèle mixte . . . . . . . . . . . . . . . . . . . 588.2 Principe de fonctionnement des serveurs multithreadés (modèle mixte) . . . . 588.3 Résultats sur un problème à 30 avions avec 13 machines réparties en deux îlots 598.4 Vitesse de convergence sur un problème à 30 avions avec 13 machines . . . . 618.5 Qualité de la solution sur un problème à 30 avions avec 13 machines . . . . . 61

9.1 Exécution du programme sur le problème des 48 capitales des États-Unis . . 669.2 Exécution du programme sur le problème des 94 préfectures françaises . . . . 669.3 Exécution du programme sur le problème des 48 capitales des États-Unis . . 689.4 Exécution du programme sur le problème des 94 préfectures françaises . . . . 68

10.1 Graphe de résolution d’un problème SAT . . . . . . . . . . . . . . . . . . . . . 7010.2 Algorithme local, problème aim-50-1_6-yes1-1 . . . . . . . . . . . . . . . 7210.3 Algorithme local, problème aim-100-1_6-yes1-1 . . . . . . . . . . . . . . 7210.4 Algorithme client-serveur, problème aim-50-1_6-yes1-1 . . . . . . . . . . 7310.5 Algorithme client-serveur, problème aim-100-1_6-yes1-1 . . . . . . . . . 7310.6 Algorithme par îlots, problème aim-50-1_6-yes1-1 . . . . . . . . . . . . . 7410.7 Algorithme par îlots, problème aim-100-1_6-yes1-1 . . . . . . . . . . . . 74

xii

Page 13: Résolution de conflits par algorithmes stochastiques parallèles

Introduction

Les problèmes de résolution de conflits aériens font partie de la famille des problèmesNP-complets. Les difficultés de résolution par méthodes d’optimisation classiques conduisentà souvent résoudre ce problème par des métaheuristiques évolutionnaires. En particulier, lesalgorithmes génétiques permettent de gérer des problèmes combinatoires de grande taille.

Il existe une autre grande classe de métaheuristiques évolutionnaires, proposée à la findes années 80 par Moyson et Manderick, et à laquelle Dorigo a fortement contribué dans lesannées 90 pour la recherche de chemins optimaux dans un graphe. Cette métaheuristiques’inspire du comportement des fourmis recherchant un chemin depuis la fourmilière vers lasource de nourriture la plus proche.

L’objet de notre étude sera alors de résoudre des conflits aériens de grande taille non pluspar algorithmes génétiques mais plutôt par algorithmes de colonies de fourmis.

Afin d’optimiser les temps de résolution, on s’attachera ensuite à la parallélisation decet algorithme. La parallélisation consiste à réaliser de manière concurrente des tâches demanière à diminuer le délai de réalisation de l’ensemble.Les opérations seront alors réparties sur un cluster de machines afin d’optimiser les tempsde convergence.

Afin de valider les méthodes de parallélisation trouvées, on cherchera également à pa-ralléliser d’autres problèmes NP-complets résolus par algorithmes de colonies de fourmis.Parmi eux, le problème du voyageur de commerce, qui se modélise naturellement par ungraphe que les fourmis pourront parcourir, et un autre problème NP-complet, le problèmede satisfaisabilité, pour lequel Denis Huet a étudié la résolution par algorithmes génétiquesdans [Huet, 1994].

1

Page 14: Résolution de conflits par algorithmes stochastiques parallèles
Page 15: Résolution de conflits par algorithmes stochastiques parallèles

Première partie

LES ALGORITHMES ET LE CHOIX DUPROBLÈME

3

Page 16: Résolution de conflits par algorithmes stochastiques parallèles
Page 17: Résolution de conflits par algorithmes stochastiques parallèles

CHAPITRE 1

Les algorithmes d’optimisation parcolonies de fourmis

Les algorithmes de colonies de fourmis forment une classe de métaheuristiques, c’est-à-dire une famille d’algorithmes d’optimisation visant à résoudre des problèmes d’optimisa-tion difficile, qu’il n’est pas possible de résoudre avec des méthodes classiques.

L’algorithme de base est le Ant System, qui a été spécialement conçu pour résoudre leproblème du voyageur de commerce.

L’idée, proposée à l’origine dans [Dorigo and Caro, 1999] et détaillée dans [Dréo et al., 2003]est basée sur le fait que les fourmis, en colonie, parviennent à résoudre des problèmes relati-vement complexes, notamment des problèmes de choix.

1.1 L’algorithme de base : le « Ant System »

1.1.1 Origines biologiques

Les fourmis utilisent pour communiquer des substances chimiques particulières appe-lées phéromones. Les fourmis sont très sensibles à ces substances, qui marquent des cheminsà suivre par leurs congénères.

Le concept sous-jacent est celui de stigmergie, c’est-à-dire une forme de communicationpar modification de l’environnement.

Ceci permet ainsi à une colonie de choisir le plus court chemin jusqu’à une source denourriture sans que personne n’ait de vision globale du trajet.

Si une colonie de fourmis emprunte des chemins aléatoires pour aller vers une cible,moins la fourmi mettra de temps pour rentrer, plus vite les fourmis suivantes seront sensiblesà ses phéromones, ce qui « creusera » un chemin de plus en plus profond vers la cible.

Au fur et à mesure que le temps s’écoule, les phéromones s’évaporent, permettant ainside ne pas exclure d’emblée des chemins et de ne pas rester coincé dans des maxima locaux.

Comme illustré sur la figure 1.1, les fourmis qui réalisent leur parcours en un tempsoptimal sont celles qui empruntent le chemin le plus court, et la quantité de phéromones yest par conséquent plus forte.

En réalité, il s’agit d’amplifier une préférence des fourmis pour un chemin.Les algorithmes de colonies de fourmis permettent alors, couplés avec une heuristique

de direction, d’optimiser des problèmes NP-complets (voyageur de commerce, problème desatisfaction de contraintes, . . . )

5

Page 18: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 1. Les algorithmes d’optimisation par colonies de fourmis

DépartNourriture

FIG. 1.1 – Sélection des branches les plus courtes par colonie de fourmi

1.1.2 Description de l’algorithme : problème du voyageur de commerce

Pour bien comprendre le principe de cet algorithme, nous allons nous pencher plus endétail sur le problème du voyageur de commerce, exemple le plus connu dans la catégoriedes problèmes NP-complets.

L’idée du problème est la suivante : un représentant de commerce doit visiter N villes enminimisant la distance à parcourir et sans repasser deux fois par la même ville.

On peut modéliser ce problème par un graphe où tous les sommets sont des villes, toutesreliées entre elles par des arêtes portant en poids la distance qui sépare les villes.

À chaque itération, chaque fourmi parcourt le graphe et construit un trajet complet de Nétapes. Le choix de la prochaine ville dépend alors de :

– la liste des villes déjà visitées Jki , quand la fourmi k est sur la ville i ;

– la visibilité ηij, inverse de la distance entre deux villes ;– l’intensité de la piste τij, ou quantité de phéromones déposée sur la piste.Alors, la règle de déplacement est régie par une probabilité :

pkij(t) =

τij(t)α · ηij(t)β

∑l∈Jki

τil(t)α · ηil(t)βsi j ∈ Jk

i

0 si j /∈ Jki

(1.1)

où α et β contrôlent l’importance de l’intensité par rapport à la visibilité.τk

ij(t) varie suivant la qualité de la solution trouvée :

∆τkij(t) =

QLk(t)

si (i, j) ∈ Tk(t)

0 si (i, j) /∈ Tk(t)(1.2)

où Tk(t) est le trajet effectué par la fourmi à l’itération t, Lk(t) la longueur du tour, et Qun paramètre fixé.

Enfin, on ajoute un paramètre ρ pour prendre en compte l’évaporation des phéromones :

τij(t + 1) = (1− ρ) · τij(t) + ∆τij(t) (1.3)

La figure 1.2 illustre cet algorithme : après avoir parcouru les villes 1, 2 et 3, la fourmi ale choix entre les 3 villes a, b et c. Le choix se fait en fonction de deux paramètres, liés à ladistance qui sépare les villes et au taux de phéromones porté par les pistes.On pourra donner plus ou moins d’importance à chacun des deux paramètres.

6

Page 19: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 1. Les algorithmes d’optimisation par colonies de fourmis

Algorithme 1 – Algorithme de colonies de fourmis : le problème du voyageur de commercepour chaque instant t faire

pour chaque fourmi k fairechoisir une ville au hasard (à l’instant t = 1)pour chaque ville non visitée i faire

choisir une ville j, dans Jki suivant les probabilités pk

ij(t)fin pourdéposer une piste ∆τk

ij(t)fin pourévaporer les pistes

fin pour

3

1

2

a

b

c

(τ3j, η3j)

FIG. 1.2 – Algorithme de colonies de fourmi : le voyageur de commerce

1.1.3 Résultats sur des problèmes traditionnels

Première analyse

La figure 1.3 rend compte de premiers résultats sur un problème à 94 villes (les préfec-tures françaises). Cette figure montre à un instant donné, avec des coefficients α et β, quanti-fiant l’importance donnée respectivement aux phéromones et à la distance, valant chacun 1et 5 (plus forte importance donnée à la distance).Ces valeurs sont proposées dans [Dorigo et al., 1996] en tant que valeurs favorables à laconvergence de l’algorithme.

Les traits de couleur rouge montrent le chemin de la meilleure fourmi, donc le cheminoptimal à l’instant de la capture. Les autres traits illustrent la quantité de phéromones pré-sents. Des seuils d’affichage ont été imposés pour éviter de surcharger la figure :

– si τ < smin, on n’affiche rien ;– si τ ∈ [smin, smax], on affiche un trait gris, d’une épaisseur proportionnelle à la quantité

de phéromones ;– si τ > smax, on affiche un trait bleu d’épaisseur constante.

7

Page 20: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 1. Les algorithmes d’optimisation par colonies de fourmis

FIG. 1.3 – Problème du voyageur de commerce : 94 préfectures françaises, α = 1, β = 5,10 itérations, 15 000 fourmis

Il est intéressant de constater que, au vu de la quantité de phéromones déposée, la cou-verture du territoire reste diversifiée et ne reste pas bloquée dans des extrema locaux évi-dents.

On peut émettre quelques réserves sur le résultat trouvé sur la figure 1.3 : en effet, sides extrema locaux triviaux sont relativement bien évités, on trouve encore dans le cheminproposé quelques boucles, témoins de la non-optimalité du résultat.

Évolution des solutions

Sur un problème de taille moyenne (48 villes), la figure 1.4 montre qu’au début (40 ité-rations), on obtient un résultat où, pour arriver à un extremum local sur des zones commel’ouest de la carte, il suffirait d’inverser deux arcs, alors que sur l’est, le processus qui per-mettrait de rejoindre la courbe bleue paraît plus complexe.

Avec 130 itérations, l’algorithme a choisi des chemins de bien meilleure qualité et trèspeu d’arcs restent à inverser.

On peut aussi jouer sur les paramètres α et β. Ici, on donne une grande importance àl’heuristique de distance, et beaucoup moins à la quantité de phéromones.Ce genre de rapport donne une convergence rapide en début d’algorithme (voir figure 1.4),mais laisse peu de marge de manœuvre par la suite et impose une convergence plus lente.

8

Page 21: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 1. Les algorithmes d’optimisation par colonies de fourmis

40 iterations en 18 secondes (34717 contre 33523)

En bleu, le chemin optimal.

FIG. 1.4 – Problème du voyageur de commerce : 48 capitales des États-Unis, α = 1, β = 5

130 iterations en 58 secondes (34432 contre 33523)

En bleu, le chemin optimal.

FIG. 1.5 – Problème du voyageur de commerce : 48 capitales des États-Unis, α = 1, β = 5

9

Page 22: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 1. Les algorithmes d’optimisation par colonies de fourmis

Si on donne plus d’importance aux phéromones qu’à la distance (par exemple α = 5 etβ = 1) , la convergence a beaucoup plus de mal à être amorcée. On arrive à des résultats trèsmédiocres même en laissant tourner l’algorithme longtemps.

Vitesse de convergence sur le premier problème

1 iterations en 6 secondes (893) 15 iterations en 173 secondes (877)

27 iterations en 331 secondes (865)

FIG. 1.6 – Problème du voyageur de commerce : 94 préfectures françaises, α = 1, β = 5

La figure 1.6 montre l’évolution de la solution proposée par l’algorithme avec le temps.Une fois de plus, on constate que trouver une solution de qualité raisonnable est chose ai-sée ; en revanche, il est beaucoup moins rapide de converger vers la solution optimale duproblème.

10

Page 23: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 1. Les algorithmes d’optimisation par colonies de fourmis

Influence des différents paramètres

Avant de se plonger dans la mise en œuvre d’un tel algorithme, il est nécessaire d’éviterquelques écueils qui peuvent nuire gravement à la qualité de la solution :

le nombre de fourmis doit nécessairement être très important. En effet, il faut qu’il y aitsuffisamment de fourmis pour qu’elles puissent interagir correctement via des phéro-mones. Si les résultats obtenus ne sont pas satisfaisants, le premier réflexe à avoir n’estpas de laisser tourner l’algorithme plus longtemps, mais en priorité d’augmenter lataille de la population des fourmis. À l’inverse, si on prend un nombre de fourmis tropimportant, le temps mis pour calculer une itération est trop long ;

la quantité de phéromones déposée est inversement proportionnelle à la distance totale duparcours des fourmis. Néanmoins, le choix d’une quantité de phéromones à déposerest fortement dépendant des distances à l’intérieur du système et aussi de la taille duproblème (nombre de villes et nombre de fourmis).Le jeu consiste au fond à garder une quantité de phéromones raisonnable sur tout leréseau, pour que les fourmis puissent y être sensibles, mais sans pour autant avoir àsaturer ces pistes ;

l’évaporation est un paramètre qui joue sur la rémanence des informations. S’il y a beau-coup d’évaporation, le système “oublie” rapidement les solutions proposées, et recom-mence les itérations en espérant trouver une meilleure solution. À l’inverse, pour unefaible évaporation, l’algorithme va creuser des pistes et rester bloqué dans des extremalocaux.Il convient donc de trouver un juste milieu, fortement dépendant de la quantité dephéromones déposée, et du nombre de fourmis. En effet, plus il y a de fourmis, plusles phéromones déposées auront de chance d’avoir une influence sur d’autres fourmisavant d’être évaporées ;

les paramètres α et β, les paramètres de la formule 1.1, qui donnent plus ou moins d’im-portance à la distance ou à la quantité de phéromones. Il est important de les prendresupérieurs à 1, le comportement de x → xn étant différent suivant que x < 1 ou x > 1.Il peut également être préférable de donner une plus forte importance à la distancequ’aux phéromones, pour qu’après un faible nombre d’itérations, les résultats soientcorrects.Un tableau montrant la convergence d’un algorithme à colonies de fourmis, en fonc-tion des paramètres α et β est lisible dans [Dorigo et al., 1991] :

β10 ∞ ∞ ∞ ∞ ∞5 ∞ † † • •2 ∞ ∞ † • •1 ∞ ∞ † • •

∞ ∞ ∞ • •0 0.5 1 2 5 α

– ∞ signifie que l’algorithme ne parvient pas à converger– • signifie que l’algorithme converge sans trouver de solutions de bonne qualité– † signifie que l’algorithme converge et trouve des bonnes solutionsPour le problème du voyageur de commerce, le couple (1, 5) a été choisi.

11

Page 24: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 1. Les algorithmes d’optimisation par colonies de fourmis

1.2 Une amélioration de l’AS : le « Ant Colony System (ACS) »

1.2.1 Description théorique

Alors que les algorithmes AS donnent des solutions quasi instantanément pour des pro-blèmes de petites tailles, [Dorigo et al., 1996] et [Dréo et al., 2003] proposent avec l’ACS desaméliorations pour les problèmes de grande taille.

Une balance diversification/intensification

Pour pallier les défauts de non-rémanence des solutions dans un sens, ou de blocage dansun extremum local dans l’autre, il peut paraître pertinent d’agir sur le paramètre évaporation.

Bien que cette solution ne soit pas viable à long terme (on imagine difficilement un opéra-teur régler constamment la valeur de l’évaporation pour aider la convergence à long terme),elle permettait d’aider à obtenir des résultats pendant la phase de développement.

L’ACS introduit donc un nouveau paramètre q0 ∈ [0, 1]. Après avoir choisi un paramètrealéatoire uniformément distribué q, la fourmi choisit sa ville destination suivant la règle :

j =

{argmaxu∈Jk

i

[τiu(t) · ηβ

i J

]si q ≤ q0

J si q > q0(1.4)

avec J choisi suivant la formule 1.1.Si q > q0, l’algorithme tend vers une diversification, à l’instar du premier algorithme AS ;

à l’inverse, si q ≤ q0, l’algorithme tend vers une intensification ; l’algorithme n’exploite plusl’information récoltée par le système et ne peut choisir de trajet non exploré.

Deux niveaux de gestion des pistes

L’ACS propose deux niveaux de mise à jour des pistes : une mise à jour locale, effectuée parchaque fourmi individuellement, et une mise à jour globale qui participe à une intensificationpar sélection de la meilleure solution.

Chaque fourmi dépose une piste lors de la mise à jour locale :

τij(t + 1) = (1− ρ) · τij(t) + ρ · τ0 (1.5)

où τ0 est la valeur initiale de la piste.La mise à jour globale s’effectue quant à elle :

τij(t + 1) = (1− ρ) · τij(t) + ρ · ∆τij(t) (1.6)

où les arêtes ij appartiennent au meilleur tour de longueur L avec ∆τij(t) =1L

.

Une liste de candidats

Pour chaque ville, on stocke une liste de villes qui sont les plus proches voisines, clas-sées par distance croissante. On instaure alors un régime transitoire pendant lequel chaquefourmi ne peut choisir sa ville suivante que parmi les arêtes non encore explorées.

Si, dans la liste de candidats, toutes les arêtes ont déjà été explorées, elle continue dechoisir suivant la formule 1.1.

Ceci va aider à une meilleure couverture du système par les fourmis, pour éviter lesminima locaux.

12

Page 25: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 1. Les algorithmes d’optimisation par colonies de fourmis

1.2.2 Comparaison de l’AS et de l’ACS

Cette méthode a été implantée mais n’a pas apporté d’amélioration spectaculaire de laconvergence. Elle sera donc mise à l’écart pour la suite du rapport, l’objectif étant d’optimiserl’algorithme par parallélisation et non pas par des artifices greffés sur la méthode la plusbasique.

13

Page 26: Résolution de conflits par algorithmes stochastiques parallèles
Page 27: Résolution de conflits par algorithmes stochastiques parallèles

CHAPITRE 2

Introduction aux problèmes derésolutions de conflits

2.1 Contexte du problème

2.1.1 Les niveaux de gestion du trafic aérien

Historiquement, les avions volaient « à vue » et utilisaient les règles de l’air pour assurerleur séparation, et ce en respectant le principe « voir et être vu ». L’amélioration des perfor-mances des avions et la densification du trafic ont conduit les États à organiser un systèmede gestion du trafic fondé sur une série de filtres, chaque filtre ayant des objectifs différentset gérant des espaces et des horizons temporels distincts.

En Europe, on peut grossièrement distinguer cinq niveaux :

À long terme (plus de 6 mois), le trafic est organisé de façon macroscopique. Sont concer-nés par exemple les schémas d’orientation de trafic, les mesures du comité des horaires,ou encore les accords inter-centres et les accords avec les militaires, qui permettent auxcivils d’utiliser leurs zones aériennes pour écouler les pointes de trafic du vendrediaprès-midi.

À plus court terme, on parle souvent de pré-régulation : elle consiste à organiser une journéede trafic, la veille ou l’avant-veille. À ce stade, on dispose d’une grosse partie des plansde vols, on connaît la capacité de contrôle que peut offrir chaque centre en fonctionde ses effectifs, le débit maximal d’avions pouvant pénétrer dans un secteur, appelécapacité du secteur. C’est le rôle de la CFMU1.

Le jour même, des ajustements sont réalisés en fonction des derniers événements. Le trafictransatlantique, par exemple, peut être pris en compte à ce stade, les avions supplé-mentaires se voient affecter leurs routes et heures de décollage, on peut égalementré-allouer des créneaux horaires non utilisés et tenir compte de la météo du jour. Cerôle est en général joué par les FMP2 dans chaque centre.

Le dernier filtre de la chaîne du contrôle aérien est le filtre tactique : il s’agit du contrôleà l’intérieur d’un secteur. Le temps moyen passé par un avion dans un secteur est del’ordre d’une quinzaine de minutes.

1Central Flow Management Unit, cellule européenne de gestion des flux de trafic.2Flow Management Position, cellule de gestion des flux du trafic aérien d’un centre de contrôle travaillant en

collaboration avec la CFMU.

15

Page 28: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 2. Introduction aux problèmes de résolutions de conflits

La visibilité du contrôleur est un peu supérieure puisqu’il dispose des plans de volquelques minutes avant l’entrée de l’avion dans le secteur. Le contrôleur assure lestâches de surveillance, de résolution de conflit et de coordination avec les secteurs voi-sins.Il convient de préciser la définition d’un conflit aérien : deux avions sont dits en conflitlorsque la distance horizontale qui les sépare est inférieure à 5 milles nautiques et leurdifférence d’altitude est inférieure à 1000 pieds. Les méthodes de résolution de conflitsappliquées par les contrôleurs aériens font appel avant tout à leur expérience. Lorsqueplusieurs couples d’avions interagissent dans le même conflit, ils commencent par sé-parer les problèmes pour n’avoir que des conflits élémentaires à résoudre.

Le filtre d’urgence n’est censé intervenir que lorsque le système de contrôle est absent ou aété défaillant : pour le contrôleur, le filet de sauvegarde prédit la trajectoire de chaqueavion avec un horizon temporel de quelques minutes à l’aide des positions radar pas-sées et d’algorithmes de poursuite et déclenche une alarme en cas de conflit.Il ne propose pas de solution aux conflits détectés. À bord des avions, le TCAS3 a pourrôle d’éviter une collision présumée. La prédiction temporelle est inférieure à la minuteet varie entre 25 et 40 secondes. Il est alors trop tard pour que le contrôleur interviennepuisque l’on estime qu’il lui faut entre 1 et 2 minutes pour analyser une situation, trou-ver une solution et la communiquer aux avions.Actuellement, le TCAS détecte les avions environnants et donne un avis de résolutionau pilote (pour le moment dans le plan vertical). Ce filtre doit résoudre les conflits nonprévisibles comme, par exemple, un avion dépassant un niveau de vol donné par lecontrôle, ou un accident technique qui dégraderait notablement les performances del’avion.

2.1.2 Contraintes du problème

Le problème de résolution de conflits aérien se situe au niveau du filtre tactique : connais-sant les positions des avions à un instant donné et leurs positions futures (avec une préci-sion donnée), quelles sont les manœuvres à donner à ces avions afin que les trajectoires negénèrent aucun conflit et que le retard engendré soit minimal.

Un certain nombre de contraintes doivent être précisées :– Un avion ne peut pas modifier sa vitesse (ou très faiblement), sauf dans sa phase de

descente ;– On ne peut pas considérer qu’un avion vole à vitesse constante, sauf éventuellement

lorsqu’il est en croisière et qu’il n’y a pas de vent. De plus en montée et en descente,sa trajectoire n’est pas rectiligne. On ne peut donc pas en donner de description analy-tique. L’évaluation des positions futures d’un avion requiert l’utilisation d’un simula-teur ;

– Les avions sont contraints en taux de virage, les pilotes préfèrent généralement ma-nœuvrer latéralement que verticalement, sauf dans les phases de montée ou de des-cente ;

– Bien que les pilotes automatiques soient aujourd’hui largement plus performants queles pilotes humains (dans les situations normales de vol), il ne paraît pas réaliste pourl’instant d’envisager des trajectoires qui ne soient pas exécutables par un pilote hu-main.

3Traffic alert and Collision Avoidance System, système anti-abordage embarqué à bord des avions.

16

Page 29: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 2. Introduction aux problèmes de résolutions de conflits

– L’incertitude sur les taux de montée et de descente est très forte (entre 10 % et 50 % dela vitesse verticale). En croisière, l’incertitude sur la vitesse est plus réduite (voisine de5 %). Latéralement, l’incertitude ne croît pas avec le temps, de même qu’un avion encroisière tient en général bien son altitude.

2.2 Complexité du problème

La nécessité d’avoir recours à un simulateur pour calculer les positions futures des avionsrend impossible la recherche de solutions analytiques au problème de résolution de conflitsaériens, ainsi que l’utilisation de méthodes d’optimisation classiques, ayant recours au gra-dient ou au hessien du critère à optimiser.Toutefois, la principale difficulté tient plus à la complexité du problème lui-même qu’auxcontraintes citées précédemment.

Si les avions sont largement automatisés, les tâches de contrôle sont restées aujourd’huilargement artisanales, en partie à cause de la complexité de la résolution des conflits.

La relation « est en conflit potentiel avec » définit une relation d’équivalence. On définitalors des classes d’équivalences associées à ces conflits que l’on appelle clusters.

Au sein d’un cluster de n avions, on peut se retrouver en présence de 12 · n(n− 1) conflits.

L’ensemble des solutions admissibles contient alors 212 ·n(n−1) composantes connexes, ce qui

suppose que si l’on veut employer des méthodes exhaustives, le problème est fortementcombinatoire.Par exemple pour un cluster à 6 avions, on aurait un total de 32 768 composantes connexes.

2.3 Méthodes de résolution

Ces problèmes peuvent être résolus par différentes méthodes, comme les algorithmesgénétiques ou la programmation par contraintes.

Le lecteur pourra aussi se reporter à [Durand, 2004] pour la description d’autres mé-thodes telles le Branch & Bound ou la programmation semi-définie.

2.3.1 Approche par algorithmes génétiques

Les algorithmes génétiques sont des méthodes stochastiques issus de la théorie de l’évo-lution. À partir d’une population donnée, des opérations de croisement, sélection et de mu-tation sont mises en jeu.

Chaque problème est représenté par un individu d’une population qui va subir des évo-lutions génétiques, en vue de converger vers une solution où chaque écart de la trajectoire àla ligne droite est minimisé, tout en évitant les conflits.

2.3.2 Programmation par contraintes

La programmation par contrainte consiste à n’écrire que les contraintes d’un problème àoptimiser sur un domaine, avec des paramètres à maximiser.

Pour un problème de résolution de conflit, il convient d’écrire les contraintes de non-collision entre les appareils, et de minimiser l’écart des trajectoires par rapport à la lignedroite.

L’intérêt d’une telle approche est la simplicité de la formalisation du problème, les librai-ries de résolution ayant déjà été écrites au préalable et étant fortement réutilisables.

17

Page 30: Résolution de conflits par algorithmes stochastiques parallèles
Page 31: Résolution de conflits par algorithmes stochastiques parallèles

CHAPITRE 3

Résolution de conflits par colonies de fourmis

3.1 Description du problème

Pour tester une métaheuristique d’optimisation, l’idéal est de considérer des problèmesdifficiles. Le problème proposé ici est un conflit à n avions, étant tous situés sur un cercle derayon R, et volant vers le centre du cercle à une même vitesse : les n avions seront donc enconflit au centre du cercle.

n avions

Zone de conflit

FIG. 3.1 – Problème de n avions en conflit

Il s’agit donc de déformer le moins possible les trajectoires des n avions pour éviter lesconflits.

19

Page 32: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 3. Résolution de conflits par colonies de fourmis

3.2 Intérêt de l’approche par colonies de fourmis

À la différence des algorithmes génétiques qui associent à chaque problème un élémentde population, nous avons fait le choix d’associer une colonie de fourmis à chaque avion,ceci afin de réduire fortement la combinatoire du problème et de permettre de résoudre desproblèmes plus gros.

1 fourmi pour n avions

1 fourmi pour 1 avion

FIG. 3.2 – Intérêt de l’approche « colonie de fourmis »

En effet, si un avion peut être dans p états différents, l’approche traditionnelle des algo-rithmes génétiques est un système à pn états, alors que l’approche des colonies de fourmisest un système à n× p états, ce qui réduit considérablement la complexité du problème.

On pourrait penser que cette approche nuirait à la convergence de l’algorithme, carchaque fourmi doit tenter de survivre, quelle que soit la qualité des chemins parcourus parles autres fourmis. Mais la réduction de la complexité du problème est indispensable à laconvergence de l’algorithme pour des problèmes de grande taille.

3.3 Description de l’algorithme

On considère un cluster de na avions. À chaque simulation, n f fourmis simulent le par-cours d’un seul avion. On garde ainsi la meilleure solution parmi les n f pour une distributionde phéromones donnée.

20

Page 33: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 3. Résolution de conflits par colonies de fourmis

3.3.1 Structure du graphe des chemins, comportement d’une fourmi

L’algorithme implanté autorise au total 7 trajectoires : la ligne droite, et trois anglesd’écart (en positif et négatif). Afin de limiter au maximum les manœuvres, on propose uncomportement pour les avions illustré par les figures 3.3 et 3.4 :

1. quand l’avion ne s’est pas écarté de la ligne droite, il est dans l’état E0 ;

2. quand l’avion commence à s’éloigner du chemin, il entre dans l’état E1 ;

3. quand il reprend la direction du point objectif, il prend l’état E2.

Le principe est de n’autoriser qu’un seul écart de trajectoire par appareil. L’automatedécrit par la figure 3.4 permet de satisfaire cette contrainte.

E0

E1E2

E1 E2

END

FIG. 3.3 – Différents états des fourmis lors du parcours du graphe

END

E0 E1 E2

FIG. 3.4 – Automate représentant les états possibles d’une fourmi

3.3.2 Dépôt des phéromones

La ligne droite est le trajet optimal en temps, on associe donc à l’état E0 la valeur 0. Unécart de trajectoire est à pénaliser, on associe donc à l’état E1 la valeur 2.Un autre objectif est de retarder le plus possible les manœuvres de l’appareil, permettantainsi de gagner en précision. En associant à l’état E2 la valeur 1, une manœuvre prématuréesera pénalisée par la fonction d’évaluation.

21

Page 34: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 3. Résolution de conflits par colonies de fourmis

À chaque itération, une fourmi choisit son chemin en fonction de la quantité de phéro-mones qu’il y a sur les arêtes suivantes.

Si une fourmi passe trop de temps à trouver une solution, où si elle entre en conflit, ellene dépose aucun phéromone, sinon elle dépose une quantité de phéromones égale à :

∆τ =na − nout

na· τ0

cparcours

où nout est le nombre de fourmis « perdues », τ0 la quantité de phéromones initiale, etcparcours la somme des coûts des états par lesquels est passée la fourmi.

On garde dans cette quantité de phéromones une dépendance vis-à-vis du nombre totald’appareils qui ont réussi à trouver un chemin valide.

3.4 Résultats obtenus

3.4.1 Premiers résultats

Les résultats sur un problème de résolution de conflits sont plutôt encourageants : avecun algorithme qui n’est pas optimisé, on parvient à résoudre un conflit à 5 avions en 11secondes (voir figure 3.6), ce qui est comparable aux résultats obtenus avec des algorithmesgénétiques.

Sur cette même figure, on peut observer comment converge cet algorithme, ce qui peutnous suggérer des pistes d’amélioration. En effet, quand on observe le résultat à 2 secondes,on peut voir que par rapport au régime stationnaire, les écarts par rapport à la ligne droitesurviennent très tôt.

On pourra ainsi penser dans des améliorations futures à mieux initialiser le dépôt de phé-romones, en n’encourageant pas les écarts dès le début du parcours, mais plutôt en gardantune répartition équiprobable selon tous les chemins que l’on peut parcourir.

3.4.2 Aide à la convergence, relaxation de contraintes

Pour un grand nombre d’avions (30 par exemple), un simple algorithme de colonies defourmis avec les contraintes imposées ne parvient pas à converger. Seuls deux appareils surles 30 initiaux parviennent à trouver un chemin sans conflit. Les fourmis ne peuvent doncpas déposer de phéromones et l’état du système est invariant.

Afin d’améliorer cette convergence, une idée consiste à relâcher la contrainte : on s’auto-rise au début à ce que chaque avion ait k conflits avec d’autres avions. Dès que suffisamentde fourmis ont trouvé des solutions au problème plus souple, on devient plus sévère sur lacontrainte :

k ← (k− 1)

Les solutions au problème posé seront celles proposées pour k = 0.

La figure 3.5 représente le domaine de recherche de l’ensemble des fourmis. Pour unproblème d’optimisation difficile, le domaine qui satisfait les contraintes est très petit, et iln’y a aucune chance de trouver une solution qui vérifie toutes les contraintes.

En gardant des solutions qui ne vérifient que certaines des contraintes, on parvient àdéposer plus de phéromones, et ainsi à attirer des populations pour réduire le domaine derecherche et augmenter la probabilité de converger vers une solution satisfaisant toutes lescontraintes.

22

Page 35: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 3. Résolution de conflits par colonies de fourmis

Domaine de recherche

Domaine qui satisfait des contraintes

Domaine qui satisfait toutes les contraintes

FIG. 3.5 – Relaxation de contraintes

3.4.3 Résultats pour 30 avions

30 avions sont disposés sur un cercle et pointent vers le centre du cercle.Le résultat de la figure 3.7 respecte bien la symétrie du problème et place les avions sur

un rond-point. Tous les avions tournent dans le même sens.Il est aussi intéressant de tracer la convergence du problème, en nombre de conflits réso-

lus et seuil de conflits acceptables par rapport au temps.Sur la figure 3.8 on peut voir que des premières solutions apparaissent avec un seuil de

conflits tolérés. Lorsque l’on réduit la tolérance, on trouve moins d’avions qui vérifient lescontraintes.

L’algorithme s’approche d’une solution sans conflit, sans y arriver pour plus de 29 avions.

23

Page 36: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 3. Résolution de conflits par colonies de fourmis

18 iterations en 2 secondes

46 iterations en 5 secondes

105 iterations en 11 secondes

FIG. 3.6 – Conflit à 5 avions : convergence de l’algorithme de colonies de fourmis

24

Page 37: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 3. Résolution de conflits par colonies de fourmis

150 iterations en 870 secondes (932)

FIG. 3.7 – Conflit à 30 avions : convergence de l’algorithme de colonies de fourmis

0

0.5

1

1.5

2

2.5

3

3.5

4

0 100 200 300 400 500 0

5

10

15

20

25

30

No

mb

re d

e co

nfl

its

Nombre d’avions

Temps en secondes

ConflitsAvions ayant moins de k(t) conflits

FIG. 3.8 – Vitesse de convergence de l’algorithme de colonies de fourmis

25

Page 38: Résolution de conflits par algorithmes stochastiques parallèles
Page 39: Résolution de conflits par algorithmes stochastiques parallèles

Deuxième partie

PARALLÉLISATION DU PROBLÈME DEGESTION DU TRAFIC AÉRIEN

27

Page 40: Résolution de conflits par algorithmes stochastiques parallèles
Page 41: Résolution de conflits par algorithmes stochastiques parallèles

CHAPITRE 4

Parallélisation de l’algorithme :modèle client–serveur

Afin d’améliorer le temps d’obtention des résultats de l’algorithme de colonies de four-mis sur un problème de résolution de conflits à 30 avions, une première tentative simple deparallélisation peut être envisagée.

L’algorithme de départ à paralléliser est le suivant :

Algorithme 2 – Algorithme de résolution de conflit (en local)Initialiser le seuil de tolérance σpour chaque itération faire

déplacer les fourmis sur le réseaudétecter les conflits de fourmis en fonction de σmettre à jour le trailréinitialiser les fourmis

fin pour

4.1 Un premier modèle simple

Une première méthode consiste à déporter le calcul des opérations coûteuses sur les ma-chines esclaves, et à centraliser les résultats des opérations.

4.1.1 Description

Dans ce modèle, on déporte les opérations coûteuses :– déplacement d’une colonie de fourmis ;– détection des conflits ;– calcul des phéromones ;

sur la machine cliente. Afin de favoriser l’originalité des îlots, on peut laisser itérer l’algo-rithme un certain nombre de fois avant de communiquer les résultats au maître.

Le maître quant à lui se charge de concaténer les résultats et de fournir aux machinesclientes des pistes de phéromones mises à jour grâce aux calculs du parc complet des ma-chines.

29

Page 42: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 4. Parallélisation de l’algorithme : modèle client–serveur

Master

Slavei −→Master

Master −→ Slavei

Slavei

Slavei

Slavei

Slavei

Données (étape 0) :

Résultats (étape i) :

(étape i+1)

FIG. 4.1 – Principe de communication client–serveur

Ainsi, à l’étape 0, on diffuse les données du problème. Ensuite, à l’étape i, une machinecliente renvoie au maître ses résultats, et attend de lui (étape i+1) de nouvelles données.

En language algorithmique, on obtient :

Algorithme 3 – Algorithme de résolution de conflit (en parallèle)MASTER SLAVE

diffuser le problème (0)pour chaque itération faire

recevoir un parcours optimal (i)recevoir un trail? mettre à jour le trail masterenvoyer le nouveau trail (i+1)

fin pour

recevoir le problème (0)pour chaque itération faire

? déplacer les fourmis sur le réseau? détecter les conflits de fourmis? mettre à jour le trail slaveenvoyer les résultats (i)recevoir le nouveau trail (i+1)

fin pour

4.1.2 Analyse

Ce premier modèle n’est pas du tout satisfaisant. En effet, les clients passent beaucoupde temps à attendre le serveur. L’opération la plus coûteuse qui reste sur le serveur est lamarshallisation1 des données.

En effet, dans l’implantation faite en OCAML, l’interface PVM utilisée incite à marshal-liser les données avant de les envoyer. Cette opération est très facile et permet d’envoyersimplement tout type de données.La structure la plus envoyée étant un tableau de Mapqui contient toutes les phéromones, il

1La marshallisation est une opération qui consiste à transformer une structure de données quelconque en uneséquence d’octets.

30

Page 43: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 4. Parallélisation de l’algorithme : modèle client–serveur

est appréciable de ne pas avoir à perdre du temps à la mise en œuvre technique de l’envoide données complexes.

Ainsi, le client qui envoie ses phéromones doit attendre du maître qu’il démarshallise lesdonnées, qu’il les traite, qu’il les remarshallise et qu’il les envoie. Cet intervalle de temps estlong. Comme tous les clients finissent leurs calculs plus ou moins au même moment, dumoins en régime transitoire, le maître sature rapidement et le temps d’attente d’un clientavant de pouvoir continuer à itérer n’est pas raisonnable.

4.2 Optimisation de l’algorithme

4.2.1 Description

Afin de limiter les coûts dûs à la marshallisation du Mapcontenant les phéromones, cetteoptimisation propose de répondre au client immédiatement, en lui envoyant le contenu dubuffer d’envoi.

(étape 10 · i)

Mise à jour

Marshallisation

Master

(étape i+1)

Données (étape 0)Phéromones

Buffer d’envoi

Résultats (étape i)

Slavei

FIG. 4.2 – Principe de communication client–serveur (optimisé)

À chaque réception, on met bien à jour le trail master, mais on ne marshallise pas systé-matiquement. De temps en temps seulement (on peut choisir par exemple une fréquence del’ordre de grandeur du nombre de machines du parc), on marshallise le Mapcourant, qui seraalors à jour pour la prochaine machine qui le recevra.

Cet artifice introduit certes un retard dans la convergence mais permet d’alléger la massede travail du serveur.

4.2.2 Analyse

Qualité du résultat

L’algorithme parallèle converge bien vers une solution (figure 4.3). Il est intéressant deconstater, au delà du fait que celui-ci tourne plus vite, que la manière de converger n’est pasla même.

31

Page 44: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 4. Parallélisation de l’algorithme : modèle client–serveur

500 iterations en 346 secondes (723)

0

0.5

1

1.5

2

2.5

3

3.5

4

0 100 200 300 400 500 0

5

10

15

20

25

30

No

mb

re d

e co

nfl

its

No

mb

re d

’av

ion

s

Temps en secondes

ConflitsAvions ayant moins de k(t) conflits

FIG. 4.3 – Conflit à 30 avions par un modèle client–serveur optimisé

32

Page 45: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 4. Parallélisation de l’algorithme : modèle client–serveur

Algorithme 4 – Algorithme de résolution de conflit optimisé (en parallèle)MASTER SLAVE

diffuser le problème (0)pour chaque itération j faire

recevoir un parcours optimal (i)recevoir un trailenvoyer le nouveau trail (i+1)? mettre à jour le trail mastersi j est un multiple de p alors

? bufferiser le nouveau trailfin si

fin pour

recevoir le problème (0)pour chaque itération faire

? déplacer les fourmis sur le réseau? détecter les conflits de fourmis? mettre à jour le trail slaveenvoyer les résultats (i)recevoir le nouveau trail (i+1)

fin pour

0

5

10

15

20

25

30

0 100 200 300 400 500

No

mb

re d

’av

ion

s ay

ant

mo

ins

de

k(t

) co

nfl

its

Temps en secondes

Algorithme non paralleleAlgorithme client--serveur

FIG. 4.4 – Algorithme local et algorithme client–serveur : comparaison des performances

33

Page 46: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 4. Parallélisation de l’algorithme : modèle client–serveur

Comparons sur la figure 4.4 l’évolution de la qualité du résultat au cours du temps.On constate que l’algorithme client–serveur est beaucoup moins réactif que l’algorithme

local. Pourtant c’est lui qui trouve une solution le premier.On peut imputer ce manque de réactivité (paliers) aux choix de conception qui ont été

faits précédemment :– les données envoyées sont volontairement obsolètes ;– toutes les machines ne peuvent communiquer que via le serveur maître ;Néanmoins, l’algorithme reste plus rapide à converger : chaque machine ayant son propre

générateur de nombres aléatoires, on parcourt mieux le domaine, ce qui peut expliquer lesbrutales améliorations de la qualité des trajets trouvés.

Analyse de performances

FIG. 4.5 – Modèle client–serveur : trace des communications entre processus

La figure 4.5 trace les communications entre les processus. On distingue alors 3 phases :

la phase 0 est la première phase de distribution des données. Le réseau est assez chargé caron envoie à tout le monde en même temps les données.

la phase 1 est un régime transitoire. Tous les processus ont fini leur travail quasiment aumême moment, et ils doivent attendre le serveur, chacun leur tour, pour pouvoir ren-voyer leurs données. Certaines machines ont donc beaucoup d’attente avant de pou-voir reprendre leur calcul.

la phase 2 est un régime permanent. La phase 1 a permis de décaler tous les processus qui neveulent pas communiquer au même moment. Plus aucun client n’attend que le maîtresoit disponible.

Avec cette configuration et ces réglages (notamment le nombre d’itérations locales nlocchez le client), on distingue clairement ces trois régimes. Néanmoins, avec la charge, c’est-à-dire en augmentant le nombre de machines, ou en diminuant nloc, le régime permanent n’estpas atteint car le serveur sature.

34

Page 47: Résolution de conflits par algorithmes stochastiques parallèles

CHAPITRE 5

Optimisation par multithreading

Le principe du multithreading est de faire s’exécuter plusieurs processus en parallèlesur la même machine. Ainsi, des tâches qui ne pouvaient pas commencer parce qu’ellesn’avaient pas la main, peuvent s’exécuter en parallèle avec des traitements coûteux en temps.

5.1 Multithreading du serveur

5.1.1 Description

Le principe de ce modèle est décrit sur la figure 5.1. En réalité, on divise le processusmaître en deux processus légers :

– le premier écoute les slaves, et récupère les données, qu’il dépacke, sans démarshalliser,dans une Queue1 ;

– le second se charge de vider la Queue en mettant à jour les phéromones, et en re-packant régulièrement les données, sur le même principe que le modèle précédent(optimisé) ;

– afin d’éviter de tourner inutilement, le thread de traitement des données se met enattente quand la Queue est vide. Dès que le thread d’écoute la remplit à nouveau, ilprévient le thread de traitement par un signal. (principe de sémaphore)

Note technique sur les threads Ce modèle n’est pas très facile à implanter. En effet, aunon-déterminisme induit par la parallélisation des données, s’ajoute celui induit par le mul-tithreading. Lorqu’un bug survient, il est difficile de le reproduire.

De plus, lorsqu’on utilise le langage CamL, il est nécessaire d’avoir des bindings C thread-safe. En effet, le risque avec PVM par exemple, est qu’une réception bloquante interrompesimultanément tous les processus légers du master : en pratique, lorsque le master est libre,il se bloque en attente de réception au lieu de vider la Queue.

5.1.2 Analyse

Le résultat correspond bien à nos attentes. En effet, notre courbe de convergence est bientranslatée. Le régime transitoire, où les réponses des serveurs sont en quinconces, observé

1La Queue est la structure First In – First Out (FIFO) du langage Caml.

35

Page 48: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 5. Optimisation par multithreading

en mode non multithreadé n’est plus aussi flagrant, car les réponses des slaves restent quasisimultanées tout au long du processus.

La figure 5.2 représente les communications tout au long de l’exécution de l’algorithmealors que la figure 5.3 illustre la convergence du processus par rapport aux autres modes.

5.2 Asynchronisation des clients

5.2.1 Description

En observant un peu mieux la figure 5.2, on peut constater que pendant que le clientrenvoit ses données au serveur, et attend sa réponse, il ne calcule plus rien.

Ceci n’a pas beaucoup d’impact sur la performance de l’algorithme si l’on considère unproblème de taille moyenne. Cependant, ceci permettrait également de résoudre le problèmede Mutex décrit dans le paragraphe précédent.

En effet, au lieu de répondre à chaque passage, on laisse le client tourner avec son vieuxtrail et on renvoie régulièrement le trail à tout le monde.À chaque fin d’itération, le client vérifie le contenu de son buffer de réception : si de nou-velles données sont arrivées, il les met à jour, sinon il continue d’itérer.

5.2.2 Analyse

Comme le client ne reste jamais inactif, même s’il tourne avec des données un peu vieilles,la convergence est encore un peu optimisée. En témoignent les figures 5.5 et 5.6.

Le lecteur attentif pourra remarquer sur la figure 5.5 qu’aucune flèche n’indique de com-munication du maître vers les serveurs, passée la première distribution des données : undébuggage un peu plus poussé permet de montrer que ces communications ont bien lieu,mais qu’un bug de XPVM empêche de les afficher.

5.3 Optimisation du volume de données transmises

Toutes les mesures précédentes ont été faites sans tenir compte du facteur temps de com-munication : tout a été fait pour être gêné le moins possible par le temps de communication,mais rien n’a encore été fait pour réduire le volume de données à transmettre.

Les mesures prises précédemment restent bien sûr valides : on aura beau optimiser lestemps de communication, le problème à 20 avions est toujours plus rapide à résoudre que leproblème à 30 avions. Si les valeurs numériques ont varié, les positions relatives des courbessont les mêmes.

Les autres analyses ayant été faites à nombre d’avions constant, donc à volume de don-nées à transmettre quasi constant, les valeurs des optima trouvés resteront sensiblement lesmêmes.

Les seuls facteurs influencés par cette future optimisation sont :– la vitesse de convergence ;– la stabilité du programme

36

Page 49: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 5. Optimisation par multithreading

F.I.F.O.

Écoute

Traitement

notify()si la FIFO est vide

Mutex

FIG. 5.1 – Principe de fonctionnement du serveur multithreadé

FIG. 5.2 – Modèle client–serveur multithreadé : trace des communications entre processus

37

Page 50: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 5. Optimisation par multithreading

0

5

10

15

20

25

30

0 100 200 300 400 500

No

mb

re d

’av

ion

s ay

ant

mo

ins

de

k(t

) co

nfl

its

Temps en secondes

Algorithme non paralleleAlgorithme client--serveur

Algorithme multithreade

FIG. 5.3 – Modèle client–serveur multithreadé : comparaison des performances

Slave

Slave

Slave

Slave

Réception

Traitement

Résultats (étape i)

Données (étape 10j)

FIG. 5.4 – Principe de fonctionnement des clients et serveurs multithreadés

38

Page 51: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 5. Optimisation par multithreading

FIG. 5.5 – Modèle client–serveur multithreadé, serveur asynchrone : trace des communica-tions entre processus

0

5

10

15

20

25

30

0 100 200 300 400 500

No

mb

re d

’av

ion

s ay

ant

mo

ins

de

k(t

) co

nfl

its

Temps en secondes

Algorithme non paralleleAlgorithme client--serveur

Algorithme multithreadeAlgorithme multithreade, client asynchrone

FIG. 5.6 – Modèle client–serveur multithreadé, serveur asynchrone : comparaison des per-formances

39

Page 52: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 5. Optimisation par multithreading

La donnée communiquée la plus volumineuse est le trail, c’est-à-dire la carte des phé-romones pour chacun des avions. Il convient donc de réduire le volume de données de cetrail.

Au bout de quelques itérations de l’algorithme, les pistes les plus mauvaises verront leurtaux de phéromones chuter vertigineusement, comparées aux meilleures pistes, qui conser-veront des taux de phéromones conséquents.

L’idée est d’envoyer alors un trail creux, à l’image des matrices creuses utilisées en ma-thématiques. Avant l’envoi du trail, on le lirait pour n’en envoyer qu’une copie où seules lesvaleurs supérieures à un certain seuil seraient copiées.

La figure 5.7 donne une idée de la simplification et de l’allègement des données.

Résultats Le seuil retenu a été le taux minimum de phéromones. Cet allègement des don-nées n’a aucune influence sur la convergence de l’algorithme, les informations transmisespermettant de reconstruire le trail étant conservées. Les optimisations précédentes ayant per-mis de s’affranchir des retards liés à l’envoi de données. En revanche, il permet d’accroîtrela robustesse de l’algorithme, car il manipule un volume de données moindre.

Pour donner un ordre de grandeur, les paquets envoyés précédemment pesaient environ10 méga-octets, alors qu’ils pèsent à présent entre 500 kilo- et 2 méga-octets.

On pourrait penser que les améliorations auraient été plus significatives, mais les paquetsenvoyés ne contiennent pas que les trails de phéromones, mais aussi d’autres informationsnécessaires au maître, entre autres les fourmis et leurs chemins.

5.4 Évaluation de la méthode – Mesures

Afin d’évaluer la pertinence de la méthode, une série de tests ont été lancés.Deux difficultés sont rencontrées par l’algorithme, et doivent être prises en compte pour

évaluer chacun des algorithmes : tout d’abord, la première difficulté est de trouver une solu-tion au problème, même médiocre. Ensuite, il s’agit d’optimiser la qualité de cette solution.

Avant toute chose, il convient de définir clairement ce que l’on va mesurer.

Définition 1 (Temps de convergence) On désignera par temps de convergence de l’algorithme,le temps que met l’algorithme à trouver une solution, qu’elle soit optimale ou pas.

Définition 2 (Qualité de la solution) On désignera par qualité de la solution trouvée par l’al-gorithme, la valeur de la fonction d’évaluation au temps de convergence.

Le plus gros problème dans l’évaluation de l’algorithme est le non-déterminisme. Afinde pouvoir cibler le domaine dans lequel l’algorithme parallèle est performant, un premierpassage sur le domaine a été fait en une seule exécution.L’algorithme testé est donc l’algorithme multithreadé, avec client asynchrone, qui itère enlocal 15 fois avant de renvoyer une solution.

Sont donc tracés sur les figures 5.8 et 5.9 les temps de convergence et qualité de la solutionpour 1, 2, 4, 6, 10 et 14 machines en réseau.

Les problèmes de petite taille : 5 et 10 avions

Pour les problèmes de petite taille, l’algorithme local trouve une solution de qualité équi-valente plus rapidement que l’algorithme distribué. Pour les petits problèmes, le parallé-lisme n’est donc pas justifié.

40

Page 53: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 5. Optimisation par multithreading

Trail complet

Trail creux

Copie avant envoi

FIG. 5.7 – Représentation d’un trail creux

41

Page 54: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 5. Optimisation par multithreading

0

20

40

60

80

100

0 2 4 6 8 10 12 14

30 avions

25 avions

20 avions

15 avions

10 avions

5 avions

Vitesse de convergence en fonction du nombre de machines

FIG. 5.8 – Vitesse de convergence

100

200

300

400

500

600

700

800

900

0 2 4 6 8 10 12 14

30 avions

25 avions

20 avions

15 avions

10 avions

5 avions

Qualité de la solution en fonction du nombre de machines

FIG. 5.9 – Qualité de la solution

42

Page 55: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 5. Optimisation par multithreading

Ceci est d’autant plus vrai qu’avec 14 machines, la file d’attente du maître sature, car ilreçoit trop de données pour avoir le temps de les traiter. On est donc obligé d’itérer pluslongtemps sur les esclaves avant de renvoyer des solutions, ce qui ralentit d’autant plusl’apparition de la première solution (donnée non tracée sur les figures).

Les problèmes de taille moyenne : 15 et 20 avions

Ici, l’algorithme parallèle sature toujours pour 14 machines. En revanche, on commenceà voir une différence sur la qualité de la solution.

L’algorithme local trouve toujours une solution plus rapidement, à cause du coût descommunications sur le réseau, mais la qualité des solutions s’améliore avec le nombre demachines.

On voit en effet apparaître l’effet de l’aléatoire sur la qualité de la solution. Plus on a demachines, mieux les fourmis parcourent leur domaine (en un temps fixé).

Si l’on cherche simplement à avoir une solution, l’algorithme local sera le plus adapté, sil’on cherche à avoir la meilleure solution, on convergera plus rapidement avec un algorithmeparallèle.

Une étude plus poussée permettrait de déterminer le nombre optimal de machines ainsique le nombre optimal d’itérations locales avant renvoi d’informations vers le maître.

Les problèmes de grande taille : 25 et 30 avions

Pour une exécution de l’algorithme local sur 30 avions, l’exploration du domaine n’étaitpas assez importante pour trouver une solution. L’algorithme parallèle est donc incontesta-blement le meilleur.

La vitesse de convergence semble en moyenne constante : en effet, une solution a toujoursété trouvée au bout d’un certain nombre (3) de cycles itération locale – communication.

En revanche, c’est la qualité de la solution qui s’améliore avec le nombre de machines.Plus le nombre de machines est grand, meilleure est la vitesse d’exploration du domaine etla diversité des solutions, parmi lesquelles les meilleures pourront avoir une influence surtoute la population de machines.

La figure 5.10 reflète les résultats de 10 exécutions par nombre de machines. Ici, la dis-persion de la qualité des résultats est frappante, sans doute le témoin d’une forte sensibilitéaux extrema locaux.

Cependant, ceci n’est que le résultat d’un seul type de problème extrêmement difficile, etil faudrait pour pouvoir généraliser ce raisonnement, extrapoler à des problèmes différents.

Aussi, ce problème de convergence précoce pourrait être résolu par un algorithme parîlots qui sera décrit plus loin.

43

Page 56: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 5. Optimisation par multithreading

500

550

600

650

700

750

800

850

0 2 4 6 8 10 12 14

Premiers resultatsMoyenne des premiers resultats

Meilleurs resultatsMoyenne des meilleurs resultats

Qualité de la solution en fonction du nombre de machines

FIG. 5.10 – Qualité de la solution

44

Page 57: Résolution de conflits par algorithmes stochastiques parallèles

CHAPITRE 6

Choix du mode de communication

Avant de nous intéresser à un autre algorithme parallèle, il paraît légitime de se poserla question du choix du mode de passage de message. En effet, à l’origine, le choix de PVMs’était imposé car une librairie pour le langage Caml était déjà développée et utilisée par lelaboratoire.

Cependant, des librairies pour MPI ont aussi été développées, et quand on connaît larenommée de MPI il paraît légitime de se poser la question du choix du mode de passage demessage.

6.1 Description théorique

6.1.1 Parallel Virtual Machine, PVM

Comme son nom l’indique, PVM fonctionne comme une machine virtuelle. Pour exécuterun programme parallèle en PVM, il est nécessaire d’avoir lancé au préalable un démon surtoutes les machines qui vont devoir participer à la manipulation.

En ce qui concerne le principe du passage de message, PVM possède un buffer d’envoiet un buffer de réception. Il est très délicat de gérer plusieurs buffers d’envoi ou de récep-tion. En effet, malgré les primitives pvm_setrbuf (réception) et pvm_setsbuf (envoi) quirendent actifs les buffers identifiés par leur bufid , il n’est pas facile de gérer plusieurs buf-fers à la fois.

6.1.2 Message Passing Interface, MPI

MPI est caractérisé par la diversité de ses configurations possibles. Il existe des modesde fonctionnement par démon (MPI–LAM), d’autres par RSH/SSH (MPICH), à mémoirepartagée, etc. qui rendent la compilation de MPI délicate pour le néophyte, et bien sûr, uneutilisation différente selon les modes.

Au contraire de PVM, MPI gère directement les buffers : le fait de passer en paramètrede la primitive d’envoi un buffer, évite de gérer des échanges de buffers actifs, très délicats.

45

Page 58: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 6. Choix du mode de communication

Les modes d’envoi/réception de MPI sont également plus complets que ceux de PVM.MPI permet des envois synchrones, asynchrones, ready1 ou bufferisés2 et bloquants/non-bloquants3.

MPI_SEND envoi asynchrone bloquant pvm_sendMPI_ISEND envoi asynchrone non bloquantMPI_RSEND envoi ready bloquantMPI_IRSEND envoi ready non bloquantMPI_SSEND envoi synchrone bloquantMPI_ISSEND envoi synchrone non-bloquantMPI_BSEND envoi par copie de buffer bloquantMPI_IBSEND envoi par copie de buffer non-bloquant

MPI_RECV réception bloquante pvm_recvMPI_IRECV réception non bloquante pvm_nrecv

réception timeout pvm_trecv

TAB. 6.1 – Comparaison des primitives d’envoi MPI et PVM

La table 6.1 compare les primitives disponibles sous MPI et sous PVM. Toutefois, la pos-sibilité de choisir aussi précisément son mode d’envoi sous MPI a un prix :

– Les implantations courantes de MPI (MPICH et MPI–LAM) ne sont pas thread-safe. Enparticulier avec les bindings C–OCAML, les primitives enter_blocking_section()et leave_blocking_section() qui garantissent un code OCAML thread-safe ne suf-fisent pas avec la librairie MPICH ;

– La bibliothèque MPE, qui permet de tracer les communications pour avoir des effetssimilaires à XPVM est réputée buggée, ce qui ne facilite pas le développement en MPI.

6.2 Comparaison sur le problème multithreadé, client simple

PVM ralentit de par sa conception l’exécution de cet algorithme multithreadé. En effet,tout réside dans la manière suivant laquelle PVM envoie ses données :

Algorithme 5 – Envoi de message par PVMInitialiser un buffer : primitive pvm_initsendbufPacker un message : primitive pvm_packEnvoyer un message : primitive pvm_send

Dans l’algorithme multithreadé, un thread écoute les messages des slaves et renvoie lecontenu du buffer d’envoi aussitôt ; alors que le thread de traitement met parfois à jour unbuffer d’envoi en même temps.

Il existe bien des primitives d’activation/désactivation de buffers d’envoi, mais le fonc-tionnement du pvm_initsendbuf est assez opaque : lui arrive-t-il d’écrire sur le bufferqu’on est en train d’envoyer ?

1On est sûr que la réception est amorcée lors du retour de l’une fonction ready2Un envoi bufferisé fonctionne par copie du buffer d’envoi.3Un envoi non-bloquant rend la main avant la fin de l’envoi de données

46

Page 59: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 6. Choix du mode de communication

Il est alors nécessaire de rajouter un Mutex sur les parties de code qui sont sensibles,même si cela n’est pas nécessaire. En effet, on peut être dans une situation où deux morceauxde code sont en mutuelle exclusion alors qu’ils ne travaillent pas sur le même buffer.

MPI est l’autre environnement de communication pour de la programmation parallèle.,dans sa primitive d’envoi des données, par exemple M P I_SE N Dpour la plus simple prenden paramètre l’identifiant du buffer que l’on veut envoyer. La maîtrise de ces buffers est bienmeilleure.

Plutôt que de gérer soi-même les copies de buffer, on peut même utiliser la primitiveM P I_BSE N Dqui vérifie précisément nos spécifications.

Le même protocole a donc été implanté en MPI. Il arrivait à l’algorithme de convergercorrectement en mauvais multithreadé4, plus rapidement que le PVM multithreadé même.(translation de la courbe de la figure 5.3)

Malheureusement, il lui arrivait de s’arrêter sur une primitive de réception MPI. Aprèsavoir longuement tenter de corriger le problème, les recherches ont été recentrées sur laproblématique de départ qui était plus la comparaison de différents algorithmes parallèlesplutôt que la comparaison PVM–MPI, voire le debuggage de MPI et des bindings OCAML.

6.3 Interface ad hoc

Pour le problème de parallélisation d’algorithmes à colonies de fourmis, toutes les pos-sibilités de MPI ne seront pas exploitées. L’objectif étant certes de comparer des algorithmesparallèles, on peut toutefois vouloir continuer à optimiser la vitesse de convergence dumeilleur algorithme trouvé.

On pourrait alors imaginer d’implanter soi-même un système de communication adaptéà la fois au problème et au réseau, à base de sockets Unix par exemple.

En conclusion, pour le problème considéré, on conservera la librairie PVM qui reste trèsbonne pour du prototypage. Si jamais on veut ensuite améliorer les performances, on pourraessayer de se pencher plus en détail sur MPI voire sur un protocole de communication adhoc à base de sockets.

4La file de réception ne se remplissait jamais de plus d’un buffer

47

Page 60: Résolution de conflits par algorithmes stochastiques parallèles
Page 61: Résolution de conflits par algorithmes stochastiques parallèles

CHAPITRE 7

Parallélisation de l’algorithme :modèle par îlots

Un autre modèle classique de parallélisation pour des algorithmes stochastiques à po-pulation (algorithmes génétiques, . . . ) est le modèle par îlots, où chaque processus lancé enparallèle fait tourner son propre algorithme et communique régulièrement ses résultats à unautre processus.

Contrairement à ce qui est comparé habituellement dans la littérature [Lefablec, 1995](parallélisation d’algorithmes génétiques) ou [Bullheimer et al., ] (parallélisation d’algorithmesà colonie de fourmis), le modèle client–serveur proposé dans ce rapport ne se caractérise paspar une simple distribution de calculs.Au contraire, dans ce modèle, chaque machine fait tourner son propre algorithme et com-muniquait des informations avec le maître, qui les redistribuait à toute la population demachines. L’apport du modèle par îlots est la décentralisation des informations.

7.1 Description du modèle

Le principal défaut du modèle client–serveur est la variance de la qualité des résultats dela figure 5.10 page 44. En effet, ceci pourrait être le témoin d’une convergence précoce versun extremum local.

L’objectif du modèle par îlots serait de limiter cette convergence précoce : profiter dunombre de machines pour préserver l’originalité des solutions de chaque machine, tout enfaisant en sorte que les machines avancent ensemble.

Ce modèle garde dans les grandes lignes le même principe que le modèle client–serveur,au détail près qu’il n’y a plus de serveur (excepté pour l’initialisation des données). Lescommunications ont donc lieu non plus entre clients et serveur, mais entre 2 clients.

À chaque itération, au lieu de renvoyer ses données vers le serveur, chaque client, quenous appelerons désormais îlot, envoie ses meilleures pistes de phéromones vers un autreîlot choisi au hasard. La figure 7.1 illustre ce principe.

Statistiquement, tous les îlots devraient recevoir autant d’information qu’ils en envoient.En revanche, l’information qu’ils reçoivent est beaucoup plus sélective que celles que rece-vaient les clients dans le modèle précédent, car ce n’est l’information que d’un seul îlot.

49

Page 62: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 7. Parallélisation de l’algorithme : modèle par îlots

Îlot

Îlot

Îlot

Îlot

Îlot

FIG. 7.1 – Principe de fonctionnement du modèle par îlots

Algorithme 6 – Algorithme de résolution de conflit (modèle par îlots)recevoir le problèmepour chaque itération faire

? déplacer les fourmis sur le réseau? détecter les conflits de fourmis? mettre à jour le trailenvoyer les résultats vers un autre îlotsi des données sont en attente alors

recevoir le trail (creux)? fusionner les trails

fin sifin pour

50

Page 63: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 7. Parallélisation de l’algorithme : modèle par îlots

7.2 Résultats

Les résultats ne sont a priori pas aussi probants que ce qu’on aurait pu attendre. Obser-vons tout d’abord les résultats sur notre problème habituel de conflits à 30 avions.

7.2.1 Le conflit à 30 avions

0

5

10

15

20

25

30

0 50 100 150 200 250 300 350 400

No

mb

re d

’av

ion

s ay

ant

mo

ins

de

k(t

) co

nfl

its

Temps en secondes

FIG. 7.2 – Algorithme par îlots : problème à 30 avions

Pour des soucis de lisibilité, on n’a pas tracé les courbes de convergence de chacun desîlots. Néanmoins, les convergences de ces îlots peuvent être rangés en 3 catégories, présen-tées sur la figure 7.2.

Les îlots dont la convergence est représentée par une courbe rouge, environ 40 % desîlots, ont des résultats très proches des résultats de l’algorithme local : quand l’algorithmetrouve pour la première fois une solution avec une tolérance de un conflit par avion, lasolution qu’il trouve à l’itération suivante résout le problème pour moins d’avions. Il fautalors réitérer avant de trouver une solution à 30 avions. Sur la courbe de convergence, lephénomène est mis en valeur à la figure 7.3.

Les îlots dont la convergence est représentée par une courbe bleue, environ 20 % desîlots, sont influencés par les autres îlots, mais ne récupèrent que les mauvais effets, ils n’ar-rivent pas à converger. Ils arrivent petit à petit à améliorer les solutions trouvées, mais neprésentent aucun résultat intéressant.

Les îlots dont la convergence est représentée par une courbe verte, environ 40 % des îlots,sont les plus proches du comportement d’îlots qu’on attendait : ils parviennent à convergerun peu plus lentement (le partage de données est moindre), mais arrivent à une solution à30 avions à coup sûr.

51

Page 64: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 7. Parallélisation de l’algorithme : modèle par îlots

Nombre de contraintes relaxées et nombre d’avions résolus en fonction du temps.

FIG. 7.3 – Caractéristique d’une résolution locale du problème

Cependant les temps de convergence de l’algorithme sont assez mauvais pour l’algo-rithme par îlots. Le lecteur pourra en effet comparer la figure 7.2 avec la figure 5.8.

7.2.2 Le conflit à 25 avions

Pour le conflit à 25 avions, les résultats sont plus intéressants : les îlots se répartissentdifféremment dans les 3 catégories énumérées dans le paragraphe précédent.

La proportion d’îlots qui ne convergent pas (courbe bleue) reste inchangée, cependant ontrouvera plus d’îlots convergeant lentement vers une solution (courbe verte) que d’îlots ayantun comportement proche de celui de l’algorithme local (courbe rouge, avec la bosse).

Ceci peut être expliqué par le fait qu’avec 25 avions, chaque îlot a accès à une portiond’information plus importante relativement à la taille du problème. Ainsi, la tendance estplus à un comportement parallèle avec partage de données, qu’à un comportement local,caractérisé par la bosse de la figure 7.3.

Quant à l’objectif qui a inspiré cet algorithme — l’espoir de voir apparaître des résultatsde meilleure qualité au détriment de la vitesse de convergence — les résultats montrent qu’iln’est pas atteint : l’algorithme client-serveur multithreadé évalue le meilleur chemin à unehauteur d’environ 650 points alors que la meilleure solution trouvée sur tous les îlots estévaluée à 750 points.

7.3 Mode de communication ad hoc

Une interprétation aux problèmes rencontrés dans l’approche par îlots est le manque decommunication entre les machines. Une possible approche serait alors de communiquer nonplus des informations à un îlot mais à tous les îlots.

L’objectif avoué est de profiter autant que possible de la diversité engendrée par le nombrede machines.

52

Page 65: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 7. Parallélisation de l’algorithme : modèle par îlots

Afin de simplifier la procédure d’envoi de données, de ne pas être handicapé si un îlota un débit d’émission trop important, on a développé un mode de communication ad hoc,comme suggéré dans la partie 6.3.

7.3.1 Exigences vis-à-vis du protocole

Intrinsèquement, notre algorithme est fortement asynchrone dans la mesure où l’on nerécupère pas des calculs dans un ordre particulier ; au contraire, on cherche plutôt à récupé-rer un maximum d’information à chaque niveau de la convergence.

Tout au long des itérations, on cherche à maintenir la plus grande diversité possible dansl’espace des solutions envisageables.

Ainsi, que toutes les informations transmises soient prises en compte n’a aucune impor-tance, l’essentiel étant que chaque îlot reçoive la plupart des informations.

En revanche, on souhaite pouvoir envoyer à tout le monde des informations, sans avoirpour autant à se soucier de la capacité d’écoute des autres machines.

Si possible, il convient d’éviter d’utiliser des librairies trop jeunes pour le langage, afinde pouvoir être sûr que les erreurs de codage viennent bien du code que l’on tape et pas dubinding peu testé que l’on utilise.

Ainsi, nous en sommes venus à utiliser du broadcast UDP :– L’UDP est plus léger et plus rapide que le TCP. Cependant, il ne garantit pas l’arrivée

des informations à destination.– Le broadcast permet d’envoyer les informations à tout le monde, sans se soucier pour

autant de « qui est tout le monde ? ».Cela permet ainsi à de nouveaux îlots de rejoindre la course en cours de route sanspour autant perturber l’évolution globale de l’ensemble des îlots ;

– La seule librairie utilisée sera la librairie Unix , utilisée depuis longtemps en OCaml etlargement débuggée.

7.3.2 Description du protocole

Chaque îlot ouvre une socket liée à l’adresse de broadcast, dans laquelle il envoie desdonnées. En parallèle (Unix.fork , pour ne pas avoir de problèmes de fonctions thread-safeou non), on écoute sur le même port.

Une contrainte liée à la taille des paquets limite a priori la taille des données à envoyer.En effet, la taille maximale d’une chaîne de caractères à envoyer est 16384.

Pour permettre au protocole de fonctionner sans artifice où l’on enverrait des morceauxde paquets à reconstituer à l’arrivée : la donnée envoyée ne sera plus un trail entier, maisun chemin choisi aléatoirement parmi les chemins du trail (les probabilités sont pondéréespar la qualité du chemin).

7.3.3 Description du nouvel algorithme

Par rapport à l’algorithme précédent par îlots, dont le principe est de limiter l’envoi desinformations pour préserver l’originalité de chaque îlot, cet algorithme sacrifie un peu dela diversité voulue (l’envoi se fait au broadcast), mais en contrepartie, n’envoie qu’un seulchemin par avion au lieu de toute la carte des chemins.

L’algorithme 7 décrit le nouveau principe de fonctionnement.

53

Page 66: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 7. Parallélisation de l’algorithme : modèle par îlots

Algorithme 7 – Algorithme de résolution de conflit (modèle par îlots UDP)recevoir le problèmesi Unix.fork = 0 alors

pour chaque itération fairerecevoir un chemin? fusionner le chemin reçu au trail

fin poursinon

pour chaque itération faire? déplacer les fourmis sur le réseau? détecter les conflits de fourmis? mettre à jour le trail? choisir un chemin parmi les meilleursenvoyer ce chemin vers tous les autres îlots

fin pourfin si

7.3.4 Résultats

Les résultats de cette méthode présentés figure 7.4 n’apportent aucune amélioration surle problème à 30 avions, où les courbes témoignent d’un manque de diversité dans le par-cours de l’espace des solutions : on ne considérera alors que le problème à 25 avions danscette partie.

Ici la méthode par îlots, envoi UDP, n’est pas dénuée d’intérêt car elle présente des tempsde convergence comparables aux méthodes client–serveur.

De plus, on n’observe plus d’îlots au comportement proche de l’algorithme local, et quetrès peu d’îlots ayant des difficultés à converger.

0

5

10

15

20

25

0 50 100 150 200

No

mb

re d

’av

ion

s ay

ant

mo

ins

de

k(t

) co

nfl

its

Temps en secondes

FIG. 7.4 – Algorithme par îlots, envoi UDP : problème à 25 avions

54

Page 67: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 7. Parallélisation de l’algorithme : modèle par îlots

7.3.5 Mise en évidence et intérêt de l’îlotisme

0

1

2

3

4

5

6

0 2 4 6 8 10 12 14

0

5

10

15

20

25

30Contraintes

Avions resolus

Evaluation

La figure présente, par îlot (en abcisse) :– le nombre de contraintes relaxées (échelle à gauche),– le nombre d’avions solutions (échelle à droite),– l’évaluation d’une solution (pas d’échelle)

L’évaluation n’est pertinente que si l’îlot a trouvé une solution à 25 avions et toutes les contraintes.

FIG. 7.5 – Algorithme par îlots, envoi UDP : problème à 25 avions — État des îlots à uninstant donné

Un autre aspect intéressant est décrit par la figure 7.5 : tous les îlots ne convergent pas àla même vitesse.

Certains îlots ont trouvé une solution, d’autres pas. Parmi les îlots qui ont trouvé, chacuna une qualité de solution différente. Ainsi, même après l’arrivée à une solution, on continueà converger vers une solution optimale.

7.3.6 Comparaison des méthodes pour différentes tailles de problèmes

Exécutons l’algorithme pour différentes tailles de problèmes avec la méthode client–serveur et avec la méthode par îlots, et notons les évaluations.

L’écart des types des solutions proposées par chaque îlot est du même ordre de grandeurque celui constaté sur la figure 5.9 pour une dizaine d’exécutions.

Ainsi, en une seule exécution sur une dizaine d’îlots, on obtient la même variance qu’avecune dizaine d’exécutions de l’algorithme client-serveur.Ceci étant dit, la qualité de la solution du meilleur îlot est de l’ordre de 10 % inférieure à laqualité des solutions trouvées avec la méthode client–serveur.

55

Page 68: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 7. Parallélisation de l’algorithme : modèle par îlots

n client–serveur îlots, envoi UDPmin moy σ

30 converge ne converge pas25 690 786 794,33 10,48 786, 813, 799, 786, 794, 78820 500 566 576,13 9,22 567, 589, 576, 569, 566, 572, 588, 58215 350 390 414,57 15,19 395, 424, 422, 424, 422, 425, 39010 150 206 223,5 13,66 217, 233, 216, 236, 218, 206, 247, 215

TAB. 7.1 – Évaluation de la méthode par îlots UDP, comparée à la méthode client-serveur

7.4 Conclusion

Ayant voulu avoir plus de diversité dans les îlots pour limiter les effets de minimumlocal, on a voulu ne plus centraliser le problème. Cependant, l’intérêt de la parallélisationpour les problèmes de grosse taille, est la diversité « une graine par machine » dont on netire pas assez profit par ce type de méthode, surtout dans les débuts de l’exécution.

Si la méthode par îlots simple préserve une graine par machine, le fait de n’envoyerle trail qu’à un seul autre îlot du groupe handicape la convergence. La tendance pour lesproblèmes de grande taille est à converger comme l’algorithme local, et à ne pas trouver desolution.1

La méthode par îlots UDP, au lieu de partager toutes les données entre peu d’îlots, par-tage peu de données entre tous les îlots. Elle garde suffisamment de diversité : on gardeautant de graines de générateurs aléatoires que de machines dans le parc. Elle gagne aussi,par rapport à la première méthode par îlots, en isolation entre îlots en n’envoyant qu’un seulchemin.

La méthode est intéressante, mais ne peut se substituer en l’état à l’algorithme client-serveur pour les problèmes de grande taille.

1La bosse de la figure 7.3 sert de critère à la pertinence du parallèlisme.

56

Page 69: Résolution de conflits par algorithmes stochastiques parallèles

CHAPITRE 8

Parallélisation de l’algorithme : modèle mixte

D’un côté, nous avons une méthode extrêmement performante en vitesse de convergenceet en qualité de résultats, d’un autre côté, nous avons une autre méthode, aussi rapide maisun peu moins performante. En revanche, celle-ci assure une diversité entre îlots.

L’idée suivante consiste alors à fabriquer une méthode hybride qui prend les qualités dechacune des méthodes.

8.1 Description du modèle

Afin d’assurer une bonne qualité de résultats, la méthode de base sera l’algorithme client-serveur asynchrone multi-threadé. Cependant, afin d’avoir un minimum de diversité, onrépartit en îlots plusieurs serveurs qui ont leurs propres clients, comme le décrit la figure 8.1.

Le fonctionnement des Slaveji est le même que celui de l’algorithme client–serveur mul-

tithreadé asynchrone. Cependant, le fonctionnement du Master i diffère, pour prendre encompte le broadcast UDP.

En effet, il faut prendre garde à ce que la mise à jour du trail en vidant la Queue ne sefasse pas en même temps que celui du broadcast.En rajoutant un thread de réception UDP qui partage un Mutex avec le thread de réceptionPVM. La figure 8.2 illustre ce fonctionnement.

L’idée sera alors une fois que l’algorithme sera implanté, de faire varier le nombre d’îlotspour trouver le nombre d’îlots optimal pour ce type de problème, sachant que si l’on n’aqu’un seul îlot, on est (à l’envoi UDP près) dans le cas client-serveur multithreadé à clientasynchrone, qui est l’algorithme qui jusqu’à présent a donné les meilleurs résultats tant auniveau de la vitesse de convergence que de la qualité des résultats.

8.2 Résultats

Les résultats trouvés pour 2 îlots sont très encourageants. La convergence du problèmereste raisonnable, bien qu’un rien plus lente, et la qualité des résultats est bien meilleure.

Sur la figure 8.3, les courbes de convergence de chaque îlot sont présentées. Le meilleurrésultat pour le premier îlot est évalué à 612 et celui du deuxième à 631. La moyenne dequalité de résultat sur un îlot était de 690. (voir figure 5.10)

57

Page 70: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 8. Parallélisation de l’algorithme : modèle mixte

Masteri

Slaveji

Slaveji

Slaveji

Slaveji

Îloti

Masteri

Slaveji

Slaveji

Slaveji

Slaveji

Îloti

Masteri

Slaveji

Slaveji

Slaveji

Slaveji

Îloti

Broadcast UDP

trail

trail trail trail

trail trail

un seul chemin

FIG. 8.1 – Principe de fonctionnement du modèle mixte

Réception UDP

Slave

Traitement

Réception PVM

Broadcast

Broadcast Slavei

Mutex

FIG. 8.2 – Principe de fonctionnement des serveurs multithreadés (modèle mixte)

58

Page 71: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 8. Parallélisation de l’algorithme : modèle mixte

0

0.5

1

1.5

2

2.5

3

3.5

4

0 20 40 60 80 100 120 140 160 180 200

0

5

10

15

20

25

30

Conflits

Avions resolus

0

0.5

1

1.5

2

2.5

3

3.5

4

0 20 40 60 80 100 120 140 160 180 200

0

5

10

15

20

25

30

Conflits

Avions resolus

Nombre de contraintes relaxées et nombre d’avions résolus en fonction du temps.

FIG. 8.3 – Résultats sur un problème à 30 avions avec 13 machines réparties en deux îlots

59

Page 72: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 8. Parallélisation de l’algorithme : modèle mixte

Certes la vitesse de convergence est un peu moindre, mais la qualité du résultat estmeilleure. A priori, pour le choix de l’algorithme, la démarche dépendra du critère qui ale plus d’importance : un résultat de bonne qualité, ou un résultat trouvé rapidement.

8.3 Bancs d’essai

Dans l’optique de trouver le nombre d’îlots optimal pour ce type de problème, 10 exécu-tions du programme ont été réalisées pour chaque nombre d’îlots de 1 à 4.

À l’instar de la figure 5.10, on mesure la vitesse de convergence globale — ie. le tempsmis pour trouver une solution, tout îlots confondus — l’évaluation du premier résultat et lameilleure évaluation en 200 secondes — tout îlots confondus.

L’exécution pour un îlot est en fait une exécution de l’algorithme client-serveur simple,qui ne lance pas le thread UDP inutilement.

Commentaires

La vitesse de convergence (figure 8.4) est pénalisée par le système d’îlots, car on rajoutechez le maître une tâche de transfert UDP et des Mutex qui bloquent des processus.

Pour un nombre d’îlots supérieur à 2, la vitesse de convergence en fonction du nombred’îlots est quasi constante.

La qualité de la solution (figure 8.5) souffre moins de dispersion avec une méthode à îlots.On gagne incontestablement en qualité de la solution, grâce à la diversité qu’on a su gagner.

Cependant la qualité redécroît quand le nombre de machines augmente. L’explication estsimple : le nombre de machines total étant constant, augmenter le nombre d’îlots revient àdiminuer le nombre de machines par îlot. Si on a peu de machines par îlot, alors l’îlot seul aplus de difficultés à converger.

Ainsi, pour chaque problème, il convient de trouver, en fonction du nombre de machinesdisponibles, la meilleure manière de répartir les machines en îlots.Ici, avec 13 machines, il est préférable de répartir le parc en deux îlots de 6 et 7 machines.

60

Page 73: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 8. Parallélisation de l’algorithme : modèle mixte

80

100

120

140

160

180

200

0 1 2 3 4 5

VitesseVitesse (moy)

Vitesse de convergence en fonction du nombre d’îlots.

FIG. 8.4 – Vitesse de convergence sur un problème à 30 avions avec 13 machines

500

550

600

650

700

750

0 1 2 3 4 5

Premiers resultatsPremiers res (moy)Meilleurs resultats

Meilleurs res (moy)

Qualité de la solution en fonction du nombre d’îlots.

FIG. 8.5 – Qualité de la solution sur un problème à 30 avions avec 13 machines

61

Page 74: Résolution de conflits par algorithmes stochastiques parallèles
Page 75: Résolution de conflits par algorithmes stochastiques parallèles

Troisième partie

PARALLÉLISATION DE L’ALGORITHMESUR D’AUTRES PROBLÈMES

63

Page 76: Résolution de conflits par algorithmes stochastiques parallèles
Page 77: Résolution de conflits par algorithmes stochastiques parallèles

CHAPITRE 9

Parallélisation du problème duvoyageur de commerce

Après avoir étudié en détail comment paralléliser des algorithmes de colonies de four-mis pour la gestion de trafic aérien, l’objectif de cette partie est d’évaluer la pertinence desremarques formulées, en appliquant chacun des algorithmes développés pour de nouveauxproblèmes d’optimisation.

Le problème évalué ici est le problème du voyageur de commerce qui a déjà été décritdans la partie 1.1.2.

9.1 L’algorithme client-serveur

L’idée principale de cet algorithme était de répartir les gros calculs sur des machinesdu parc. Dans le problème de résolution de conflit, les gros calculs étaient le choix d’unetrajectoire d’avion et surtout la détection de conflit parmi ces avions.

Dans le problème du voyageur de commerce, la seule opération coûteuse est le choix deschemins empruntés par le voyageur.

La figure 9.1 trace les deux exécutions : non parallèle et client–serveur.La principale observation que l’on peut faire sur ce type de problème est l’absence de

gain en temps pour trouver des solutions : au lieu d’être décalée horizontalement, la courbeest décalée verticalement, c’est-à-dire que c’est la qualité des solutions à temps de calcul égalqui est améliorée.

En effet, le problème du voyageur de commerce est coûteux non pas par la lourdeur descalculs, mais par l’exploration du domaine des chemins possibles.

L’amélioration observée est la conséquence de la présence d’extrema locaux. Alors quel’algorithme local se bloque dans des minima locaux, chaque client de l’algorithme parallèlene va pas se bloquer dans les mêmes extrema locaux, et aider les autres clients à se libérer deces extrema.

Toutefois, même si la convergence semble un peu meilleure, on reste loin du minimumdu problème connu1.

De même pour la figure 9.2, le parallélisme apporte une convergence plus rapide vers unminimum inférieur à celui trouvé par l’algorithme local.

1Le problème des capitales des États-Unis fait partie d’une banque de données de problèmes pour lesquelson connaît la meilleure solution.

65

Page 78: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 9. Parallélisation du problème du voyageur de commerce

33500

34000

34500

35000

35500

36000

36500

37000

37500

0 50 100 150 200

Algorithme localAlgorithme client-serveur

Minimum

Évaluation de la meilleure solution en fonction du temps.

FIG. 9.1 – Exécution du programme sur le problème des 48 capitales des États-Unis

855

860

865

870

875

880

885

890

895

900

905

0 50 100 150 200

Algorithme localAlgorithme client-serveur

Évaluation de la meilleure solution en fonction du temps.

FIG. 9.2 – Exécution du programme sur le problème des 94 préfectures françaises

66

Page 79: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 9. Parallélisation du problème du voyageur de commerce

9.2 L’algorithme par îlots

L’idée proposée pour l’algorithme par îlots est de faire converger séparément chaque ma-chine du parc. De temps en temps, chaque îlot diffuse sur le réseau (broadcast) son meilleurchemin, qui apporte alors une contribution sur le réseau de phéromones de chacun des îlots.

Chaque îlot garde ses pistes de phéromones, qui dépendent de ses itérations locales, maisaccepte d’explorer les meilleures pistes trouvées par les autres machines.

La figure 9.3 montre les résultats pour le problème des 48 capitales des États-Unis : l’al-gorithme par îlots ne reste pas coincé dans des minima locaux et converge vers le minimumconnu du problème.

La figure 9.4 montre les résultats pour le problèmes de 94 préfectures françaises : l’al-gorithme converge un peu moins vite au début, et finit par stationner dans un minimuminférieur aux minima locaux trouvés par les autres algorithmes.2

Contrairement aux problèmes de résolution de conflits aériens, où l’algorithme par îlotsétait insuffisant pour trouver une solution (pas assez de partage des données), le problèmedu voyageur de commerce se prête plutôt bien à cette méthode.L’algorithme par îlots, bien que plus lent, arrive à de meilleurs résultats.

9.3 L’algorithme mixte, îlots de clients-serveurs

Pour le problème de la résolution de conflits, un algorithme mixte avait été développé.La méthode étant déjà écrite, elle a été testée sur le problème du voyageur de commerce,

mais ne présente pas de résultat convaincant. Ceci n’est guère surprenant cependant.En effet, on a vu au cours des chapitres précédents que la convergence d’un algorithme

d’optimisation stochastique est délicate à atteindre ; c’est le résultat d’un équilibre à trouverentre diversité des données et convergence. Il faut arriver à parcourir au mieux le domaine,tout en trouvant des zones du domaine de recherche à favoriser.

La parallélisation client-serveur met en œuvre un fort partage de données, et aide à ci-bler le domaine de recherche. La méthode est particulièrement efficace pour la relaxation decontraintes. La parallélisation par îlots met en œuvre un faible partage de données, et favo-rise la diversité des solutions trouvées.Pour le problème du voyageur de commerce, il n’y a pas de problème de relaxation decontraintes : l’algorithme par îlots est alors le plus adapté.

2Ce problème ne fait pas partie de la banque de données citée plus haut. On ne connait pas la meilleuresolution « officielle »

67

Page 80: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 9. Parallélisation du problème du voyageur de commerce

33500

34000

34500

35000

35500

36000

36500

37000

37500

0 50 100 150 200

Algorithme localAlgorithme client-serveur

Algorithme par ilotsMinimum

Évaluation de la meilleure solution en fonction du temps.

FIG. 9.3 – Exécution du programme sur le problème des 48 capitales des États-Unis

850

855

860

865

870

875

880

885

890

895

900

905

0 50 100 150 200

Algorithme localAlgorithme client-serveur

Algorithme par ilots

Évaluation de la meilleure solution en fonction du temps.

FIG. 9.4 – Exécution du programme sur le problème des 94 préfectures françaises

68

Page 81: Résolution de conflits par algorithmes stochastiques parallèles

CHAPITRE 10

Problèmes SAT et CSP

Ces deux problèmes font partie de la catégorie des problèmes NP-complets. Denis Huet aétudié la résolution de ce type de problèmes avec des algorithmes génétiques dans [Huet, 1994].

10.1 Présentation des problèmes

10.1.1 Les problèmes SAT

Définition 3 (Problème SAT) Un problème de satisfaisabilité, SAT P = (X, F) est défini par :– une séquence X = (x1, · · · , xn) de n variables booléennes– une formule F définie comme la conjonction de m clauses cj : F = c1 ∧ · · · ∧ cm. Chaque

clause est définie comme une disjonction des variables xi ou de leur négation xi. On aura ainsicj = y1 ∨ · · · ∨ yk avec yi ∈ {x1, · · · , xn, x1, · · · xn}.

Une formule F est satisfiable s’il existe n valeurs pour les variables {x1, · · · , xn} quirendent la formule F vraie, donc qui rendent toutes les clauses ci vraies. La recherche deces valeurs particulières correspond à la résolution du problème SAT.

Par exemple, X = (x1, x2, x3) et F = c1 ∧ c2 avec c1 = x1 ∨ x2 et c2 = x2 ∨ x3 est unproblème SAT.

10.1.2 Les problèmes CSP

Définition 4 (Problème CSP) Un problème de satisfaction de contraintes, CSP P = (X, D, C)est défini par :

– une séquence X = (x1, · · · , xn) de n variables– une séquence D = (d1, · · · , dn) de n domaines finis pour les variables de X. Le domaine di est

associé à la variable xi.– une séquence C = (c1, · · · , cm) de m contraintes. Chaque contrainte ci est définie par le couple

(vi, ri) :– vi est une séquence de ni variables (xi1 , · · · xini

) ∈ X sur lesquelles porte la contrainte ci ;– ri est une relation, définie par un sous-ensemble du produit cartésien di1 × · · · × dini

desdomaines associés aux variables vi.

Résoudre le problème CSP P consiste à trouver pour chaque variable xi une valeur dansle domaine di de manière à ce que chaque contrainte soit réalisée.

69

Page 82: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 10. Problèmes SAT et CSP

10.2 Résolution par algorithme à colonies de fourmis

10.2.1 Résolution d’un problème SAT

On transforme le problème en un graphe ayant pour sommets chaque couple (xi,>) et(xi,⊥), et un point départ. Les arêtes relient tous les points xi à tous les points xi+1.

Une affectation correspond alors à un chemin sur ce graphe. Les fourmis parcourent cegraphe pour trouver une solution.

(x1,>)

(x1,⊥)

(xi,>) (xn,>)

(xn,⊥)(xi,⊥)

Départ

FIG. 10.1 – Graphe de résolution d’un problème SAT

À chaque affectation trouvée, on compte le nombre N de clauses ci violées. En effet, pourque la formule F soit satisfiable, il faut et il suffit que toutes les clauses ci soit vraies, c’est-à-dire que N = 0. On dépose alors sur le parcours une quantité de phéromones inversementproportionnelle à N.

On pourrait comparer cette méthode à un raisonnement idiot, qui consiste à choisir desinstanciations au hasard, et à les affiner en fonction du nombre de contraintes violées.

10.2.2 Résolution d’un problème CSP

Le principe est le même qu’un problème SAT. La différence est que les sommets des arcsne sont plus indexés par > et ⊥ mais pas les valeurs du domaine de définition de chaquevariable.

Comme les problèmes CSP nécessitent moins de variables que les problèmes SAT, l’arbreinduit par le problème est plus en largeur que l’arbre induit par un problème SAT, plutôt enprofondeur.

Dans la suite du chapitre, on n’étudiera que les problèmes SAT.

10.3 Bancs d’essai sur exécution locale

Les données des problèmes choisis pour les bancs d’essai ont été prises sur le site SATLIBhttp ://www.intellektik.informatik.tu-darmstadt.de/SATLIB/benchm.html.

Les problèmes choisis ont été :– aim-50-1_6-yes1-1 ;– aim-100-1_6-yes1-1

70

Page 83: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 10. Problèmes SAT et CSP

10.3.1 Problème aim-50-1_6-yes1-1

Le problème exécuté est un problème SAT, satisfaisable, avec 50 variables et 80 clauses.La figure 10.2 représente graphiquement cette convergence. On arrive à trouver facile-

ment une solution qui viole 3 clauses, et en laissant itérer on peut trouver une solution quiviole 2 voire 1 seule clause.

10.3.2 Problème aim-100-1_6-yes1-1

Le problème exécuté est un problème SAT, satisfaisable, avec 100 variables et 160 clauses.La figure 10.3 représente graphiquement la convergence de l’algorithme qui ne parvient

pas à trouver de solutions qui viole moins de 8 clauses.

10.3.3 Conclusion de l’exécution sur l’algorithme local

Sur les deux problèmes, on sent assez vite venir l’intérêt de la parallélisation, qui per-mettra de mieux parcourir le domaine.

Ici le domaine à parcourir n’est pas très grand, il est possible que le modèle par îlots soitplus profitable que le modèle client-serveur.

10.4 Modèle parallèle client-serveur

10.4.1 Description

À l’instar des autres problèmes sur lesquels ce modèle a été développé, chaque clientfait tourner un algorithme et renvoie ces phéromones vers le serveur, qui somme toutes lesphéromones reçues.

Ensuite, le serveur renvoie régulièrement vers les clients le cumul des phéromones re-çues.

10.4.2 Résultats

Même si l’algorithme n’est pas parvenu à trouver une solution, les résultats n’en sont pasmoins meilleurs que pour l’algorithme local, comme en témoignent les figures 10.4 et 10.5.

10.5 Modèle parallèle par îlots

10.5.1 Description

Le modèle parallèle par îlots a aussi été implanté. Chaque îlot fait tourner un algorithmeet transmet au broadcast les phéromones qui mènent à une variable et une seule.

10.5.2 Résultats

On surveille la convergence sur chacun des îlots pour chacun des problèmes présentésprécédemment, et on trace le plus petit nombre de clauses violées sur l’ensemble des ma-chines du parc en fonction du temps.

On présente alors les tracés sur les figures 10.6 et 10.7 : même si le problème n’est toujourspas résolu, les solutions à nombre de clauses violées égal sont trouvées plus rapidementqu’avec les autres algorithmes.

71

Page 84: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 10. Problèmes SAT et CSP

0

2

4

6

8

10

0 20 40 60 80 100 120 140

Nombre de conflits sur les clauses en fonction du temps

FIG. 10.2 – Algorithme local, problème aim-50-1_6-yes1-1

0

5

10

15

20

0 20 40 60 80 100 120 140

Nombre de conflits sur les clauses en fonction du temps

FIG. 10.3 – Algorithme local, problème aim-100-1_6-yes1-1

72

Page 85: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 10. Problèmes SAT et CSP

0

2

4

6

8

10

0 20 40 60 80 100 120 140

Algorithme localAlgorithme client-serveur

Nombre de conflits sur les clauses en fonction du temps

FIG. 10.4 – Algorithme client-serveur, problème aim-50-1_6-yes1-1

0

5

10

15

20

0 20 40 60 80 100 120 140

Algorithme localAlgorithme client-serveur

Nombre de conflits sur les clauses en fonction du temps

FIG. 10.5 – Algorithme client-serveur, problème aim-100-1_6-yes1-1

73

Page 86: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 10. Problèmes SAT et CSP

0

2

4

6

8

10

0 20 40 60 80 100 120 140

Algorithme localAlgorithme client-serveur

Algorithme ilots

Nombre de conflits sur les clauses en fonction du temps

FIG. 10.6 – Algorithme par îlots, problème aim-50-1_6-yes1-1

0

5

10

15

20

0 20 40 60 80 100 120 140

Algorithme localAlgorithme client-serveur

Algorithme ilots

Nombre de conflits sur les clauses en fonction du temps

FIG. 10.7 – Algorithme par îlots, problème aim-100-1_6-yes1-1

74

Page 87: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 10. Problèmes SAT et CSP

10.6 Mise en évidence de cas défavorables à la résolution de pro-blèmes SAT par algorithme de colonies de fourmis

Les algorithmes de colonies de fourmis implantés ne parviennent pas à résoudre les pro-blèmes SAT proposés en benchmark.

Parmi les paramètres à remettre en cause, on peut signaler la fonction d’évaluation, quicompte le nombre de clauses violées.

Considérons un ensemble de 100 variables xi et la forme normale conjonctive suivante :

F = x1

∧ (x2 ∨ x1)∧ (x3 ∨ x1)∧ (x4 ∨ x1)∧ · · ·∧ (x100 ∨ x1)

Une solution évidente est ∀i, xi = >. Pourtant, pendant la résolution, si on choisit x1 = >,dans le pire des cas, on peut violer jusqu’à 99 clauses alors qu’en choisissant x1 = ⊥, danstous les cas, on ne viole qu’une seule contrainte, quelles que soient les autres affectationschoisies.

On est donc en présence d’un minimum local très fort, duquel il est très difficile de sortir.Cet exemple n’est bien sûr qu’un cas d’école, car on pourrait réduire le problème en

affectant d’emblée x1 = >, pourtant l’exemple montre que la mesure du nombre de clausesviolées n’est pas très pertinente en matière de convergence vers une solution du problèmeSAT (pour laquelle le nombre de clauses violées est nul).

Si l’on souhaite à l’avenir résoudre des problèmes SAT par colonies de fourmi, il serapréférable de reconsidérer la fonction d’évaluation.

Malgré tout, ce chapitre a permis de confirmer l’idée selon laquelle, pour de petits do-maines, l’algorithme par îlots permet des convergences plus rapides.

75

Page 88: Résolution de conflits par algorithmes stochastiques parallèles
Page 89: Résolution de conflits par algorithmes stochastiques parallèles

CHAPITRE 11

Comparaison des modèles de parallélisation

Parmi les trois problèmes étudiés ici, à savoir la résolution de conflits aériens, le problèmedu voyageur de commerce, et le problème de satisfaisabilité, les différentes méthodes deparallélisation n’ont pas donné les mêmes résultats.

Ce chapitre a pour but de reprendre chacun des problèmes, chacun des algorithmes, etd’étudier l’adéquation de chacun des algorithmes à chacun des problèmes.

11.1 Caractéristiques des problèmes

Chacun des problèmes étudiés sera décrit suivant une grille qui détaille :– la taille du domaine ;– la présence d’un critère d’optimisation ;– la présence de contraintes ;

et des commentaires.

11.1.1 Le problème de résolution de conflits

Le problème de résolution de conflit proposé dans ce rapport est le problème symétriquede n avions placés sur un cercle à la même altitude et pointant vers le centre avec la mêmevitesse. Il s’agit de trouver une trajectoire pour chacun des appareils tout en respectant lesdistances de sécurité entre appareils.

Le graphe utilisé est détaillé dans le chapitre 3.3 : sa taille n’est pas connue précisément,mais pour pouvoir trouver une solution, il faut un nombre de composantes connexes aumoins égal à 2

12 ·n(n−1).

Domaine O(en2)

Critère d’optimisation la somme des temps de parcours des avionsContraintes les distances de sécurité anti-collision

Le problème de résolution de conflits est un problème plutôt calculatoire, car il faut vé-rifier à chaque instant que tous les avions respectent les distances de sécurité deux à deux.

La taille du domaine à parcourir est certes très grande, cependant, grâce à l’analogienaturelle entre ce type particulier de graphe et un arbre, une branche du graphe qui conduità un échec est facilement éliminable du domaine de recherche.

77

Page 90: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 11. Comparaison des modèles de parallélisation

11.1.2 Le problème du voyageur de commerce

Le problème du voyageur de commerce (TSP) est un problème d’optimisation qui partd’un ensemble de n villes : un voyageur de commerce part d’une ville et doit parcourir toutesles villes une fois et une seule en minimisant la distance de son parcours.

Domaine n sommets et Θ(n2) arêtesCritère d’optimisation la taille totale du parcoursContraintes aucune

Le problème du voyageur de commerce est un problème peu calculatoire et très itératif.

11.1.3 Le problème de satisfaisabilité

Le problème de satisfaisabilité (SAT) est un problème qui consiste, partant de n variablesbooléennes et d’une formule logique mise sous forme normale conjonctive, à affecter desvaleurs à ces variables pour satisfaire cette formule.

Domaine 2n sommets et 4n arêtesCritère d’optimisation aucunContraintes validité de chacune des clauses de la formule

Le problème de satisfaisabilité est un problème plus calculatoire que le TSP dans la me-sure où il nécessite pour chaque solution proposée de vérifier chacune des m clauses de laformule.

11.2 Les modèles d’algorithmes parallèles

Face à chacun de ces problèmes aux caractéristiques bien différentes, différents modèlesd’algorithmes parallèles ont été développés.

11.2.1 Le modèle client-serveur

Le modèle client-serveur décrit ici est le modèle client-serveur multithreadé à client asyn-chrone (chapitre 5.2.1 page 36), optimal pour le problème de résolution de conflits aériens.

Le principe est celui d’un serveur central qui distribue toutes les données du problème àdes clients, qui récupère toutes les données à intervalles réguliers, pour pouvoir redistribuerla combinaison de ces données à tous les îlots.

Ce modèle présente un fort partage de données entre les machines, il permet ainsi defortement cibler le domaine de recherche.

11.2.2 Le modèle par îlots

Le modèle par îlots décrit ici est le modèle UDP. (chapitre 7.1 page 49)Le principe est celui d’îlots qui exécutent tous le même problème et diffusent en broad-

cast quelques unes de leurs données. En parallèle, ils récupèrent du broadcast les donnéesdes autres îlots pour les intégrer à leurs données.

Ce modèle présente un faible partage de données entre les îlots, ce qui permet de favori-ser la diversité entre les îlots.

78

Page 91: Résolution de conflits par algorithmes stochastiques parallèles

Chapitre 11. Comparaison des modèles de parallélisation

11.2.3 Le modèle mixte

Le modèle mixte a été développé pour mélanger les qualités des deux modèles précé-dents, et pour les appliquer au problème de résolution de conflits.

Le principe est celui de plusieurs îlots qui partagent quelques informations par broad-cast UDP, chaque îlot étant un serveur, déléguant ses calculs à quelques îlots. Il requiert derépartir les tâches à l’avance, pour que chaque machine sache quel rôle elle a au sein de quelgroupe.

Ce modèle permet de favoriser une diversité entre îlots, qui ont chacun ciblé leur do-maine de recherche.

11.3 Adéquation des modèles aux problèmes

11.3.1 Le problème de résolution de conflits et le modèle mixte

Le problème de résolution de conflits a un domaine de recherche très grand. Le modèleclient-serveur permet de fortement cibler le domaine de recherche et de trouver une solutionqui satisfasse les contraintes.

Cependant, le modèle client-serveur plonge rapidement tous les îlots vers des extremalocaux. La partie modèle par îlots du modèle mixte permet alors d’optimiser la solution trou-vée au problème.

11.3.2 Le problème TSP et le modèle par îlots

Le problème TSP a un domaine de recherche beaucoup plus réduit que celui du problèmede résolution de conflits. Le modèle client-serveur ne lui permet pas de se sortir des extremalocaux et d’optimiser les solutions qu’il propose.

En revanche, le modèle par îlots permet de bien diversifier les solutions proposées etd’arriver à converger vers une solution très proche de la solution optimale.

Le modèle mixte ne faisant rien d’autres que diminuer le nombre d’îlots, en enfermantchacun d’entre eux dans des extrema locaux, il n’est pas du tout adapté à ce genre de pro-blèmes.

11.3.3 Le problème SAT et le modèle par îlots

Les algorithmes de colonies de fourmis en l’état ne sont pas aptes à résoudre des pro-blèmes SAT, sans doute à cause de l’absence de critère d’optimisation. Si le problème derésolution de conflits aériens était défini par des contraintes, il avait aussi un critère d’opti-misation qui aidait au bon fonctionnement de l’algorithme.La définition d’un problème SAT n’étant faite que de contraintes, la convergence est difficile.

Pourtant, le modèle par îlots semble le plus approprié : à qualité de résultats égale, c’estle modèle par îlots qui converge le plus vite.

79

Page 92: Résolution de conflits par algorithmes stochastiques parallèles
Page 93: Résolution de conflits par algorithmes stochastiques parallèles

Conclusion

Ainsi, on a pu montrer tout au long de ce rapport que les algorithmes de colonies defourmis permettaient de résoudre quelques problèmes d’optimisation NP-complets.

Contrairement aux résultats habituels sur la parallélisation d’algorithmes, comme onpeut en voir dans le rendu d’images par exemple, la parallélisation ne permet pas tant desoulager les machines d’une forte charge de calculs que d’apporter une meilleure diversitédans le parcours du domaine de recherche.

On a pu ainsi voir que l’initialisation d’un générateur de nombres aléatoires différentselon les machines du parc a permis de ne pas éliminer prématurément des arêtes du graphe,et de se libérer des pièges de certains extrema locaux.

On a aussi pu remarquer que suivant les caractéristiques du problème à résoudre, cer-taines méthodes (client–serveur, îlots ou mixte) pouvaient être plus performantes que d’autres.

Bien souvent, les algorithmes d’optimisation évolutionnaires ne permettent pas de savoirsi la solution trouvée est optimale ou non.Cependant, on pourrait imaginer pour chacun des algorithmes implantés dans ce rapport,de rajouter aux algorithmes des artefacts de recherche locale (pour dérouler les boucles dansle problème du voyageur de commerce par exemple), qui permettraient d’arriver à coup sûrà la solution du problème posé.

81

Page 94: Résolution de conflits par algorithmes stochastiques parallèles
Page 95: Résolution de conflits par algorithmes stochastiques parallèles

Bibliographie

[Bullheimer et al., ] Bullheimer, B., Kotsis, G., and Strauss, C. Parallelization strategies forthe Ant System.

[Dorigo and Caro, 1999] Dorigo, M. and Caro, G. D. (1999). Ant Colony Optimization : aNew Meta-Heuristic.

[Dorigo et al., 1991] Dorigo, M., Maniezzo, V., and Colorni, A. (1991). Ant system : An auto-catalytic optimizing process.

[Dorigo et al., 1996] Dorigo, M., Maniezzo, V., and Colorni, A. (1996). The Ant system : Op-timization by a colony of cooperating agents.

[Dréo et al., 2003] Dréo, J., Petrowsky, A., Siarry, P., and Taillard, E. (2003). Métaheuristiquespour l’optimisation difficile, chapter 4. Les algorithmes de colonies de fourmis.

[Durand, 2004] Durand, N. (2004). Algorithmes Génétiques et autres méthodes d’optimisationappliqués à la gestion de trafic aérien. PhD thesis, Thèse d’habilitation.

[Gianazza, 2005] Gianazza, D. (2005). Algorithme évolutionnaire et A* pour la séparationen 3D des flux de trafic aérien. In Journal Européen des Systèmes automatisés, volume 38 -n◦9-10/2004, numéro spécial "Métaheuristiques pour l’optimisation difficile".

[Huet, 1994] Huet, D. (1994). Application des algorithmes génétiques aux problèmes SAT etCSP. Technical report.

[Lefablec, 1995] Lefablec, Y. (1995). Optimisation par algorithmes génétiques parallèles etmulti-objectifs. Master’s thesis, Rapport DEA IFP.

83