Optimisation par colonies de fourmis COSTANZO Andrea LUONG Thé Van MARILL Guill

Optimisation par colonies de fourmis COSTANZO Andrea LUONG Thé Van MARILL Guillaume 19 mai 2006 Table des matières 1 Introduction 4 1.1 Pourquoi les fourmis ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Relation avec l’informatique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Comportement de la fourmi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 Optimisation par colonie de fourmis 6 2.1 Historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Similarités et différences avec les fourmis réelles [Dréo 04] . . . . . . . . . . . . . . 6 2.2.1 Points communs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.2 Différences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Expériences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3.1 Pont binaire de Deneubourg [Dréo 04] . . . . . . . . . . . . . . . . . . . . . 7 2.3.2 Expérience du double pont binaire [Dorigo 03] . . . . . . . . . . . . . . . . 8 2.3.3 Effet de la coupure d’une piste de phéromone [Dréo 04] . . . . . . . . . . . 9 2.3.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3 Voyageur de commerce : Algorithme Ant System (AS) 11 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2 Ant System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2.1 Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2.2 Choix d’implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.3 Fonctionnement de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.3.1 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.3.2 Variantes [Dorigo 03] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.4 Choix des paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.4.1 Considérations générales [Dréo 04] . . . . . . . . . . . . . . . . . . . . . . . 15 3.4.2 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.4.3 Les fourmis élitistes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.4.4 Résumé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4 Performances de l’algorithme Ant System 18 4.1 Présentation générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.2 Résultats sans fourmis élitistes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.3 Résultats avec fourmis élitistes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.4 Applications sur d’autres tailles de données . . . . . . . . . . . . . . . . . . . . . . 24 4.4.1 Un plus petit problème ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.4.2 ... et un plus grand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.4.3 Conclusion des expériences . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2 TABLE DES MATIÈRES 3 5 Améliorations plus récentes de Ant System 29 5.1 Évolution des algos TSP : Nouvelles approches . . . . . . . . . . . . . . . . . . . . 29 5.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.1.2 Ant-Q [Dorigo 02] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.1.3 Ant Colony System (ACS) [Dorigo 02] . . . . . . . . . . . . . . . . . . . . . 30 5.1.4 Max-Min Ant System : MMAS [Dorigo 03] . . . . . . . . . . . . . . . . . . 30 6 Optimisation des tables de routage 31 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 6.2 Principe de l’algorithme [Dréo 04] . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 6.2.1 Les fourmis du net . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 6.2.2 Mecanisme de antNet . . . . . . . . . uploads/Societe et culture/ colonies-fourmis-200605-rapport.pdf

Tags
Société et culturefourmis phéromones fourmi longueur l’algorithme
Documents similaires
  • 29
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager