23
Powerpoint Templates Page 1 Institut Supérieur d'Informatique et des Techniques de Communication L’algorithme de fourmis Elaborer par : Mayeh ons Bannour Amira

Institut Supérieur d'Informatique et des Techniques de Communication

  • Upload
    nen

  • View
    52

  • Download
    0

Embed Size (px)

DESCRIPTION

Institut Supérieur d'Informatique et des Techniques de Communication. L’algorithme de fourmis Elaborer par : Mayeh ons Bannour Amira . Sommaire . Historique C’est quoi l’algorithme de fourmis? Origine Les comportement Les fonctionnalités - PowerPoint PPT Presentation

Citation preview

Page 1: Institut  Supérieur  d'Informatique et des Techniques de Communication

Powerpoint Templates Page 1

Institut Supérieur d'Informatique et des Techniques de Communication

L’algorithme de fourmis

Elaborer par : Mayeh ons Bannour Amira

Page 2: Institut  Supérieur  d'Informatique et des Techniques de Communication

Powerpoint Templates Page 2

Sommaire

1. Historique2. C’est quoi l’algorithme de fourmis?3. Origine 4. Les comportement5. Les fonctionnalités 6. Les système fourni 7. Principale variante8. Cadre ACO9. Application10. Structure Algorithme de fourmis11. Conclusion

Page 3: Institut  Supérieur  d'Informatique et des Techniques de Communication

Powerpoint Templates Page 3

Historique

• Initialement proposé par Marco Dorigo et al. dans les années 1990, pour la recherche de chemins optimaux dans un graphe, le premier algorithme s’inspire du comportement des fourmis recherchant un chemin entre leur colonie et une source de nourriture.

Page 4: Institut  Supérieur  d'Informatique et des Techniques de Communication

Powerpoint Templates Page 4

C’est quoi algorithme de fourmis?

• Les algorithmes de colonies de fourmis sont des algorithmes inspirés du comportement des fourmis et qui constituent une famille de métaheuristiques d’optimisation.

• L’idée originale s'est depuis diversifiée pour résoudre une classe plus large de problèmes et plusieurs algorithmes ont vu le jour, s’inspirant de divers aspects du comportement des fourmis.

Page 5: Institut  Supérieur  d'Informatique et des Techniques de Communication

Powerpoint Templates Page 5

Origine

• L’idée originale provient de l’observation de l’exploitation des ressources alimentaires chez les fourmis. En effet, celles-ci, bien qu’ayant individuellement des capacités cognitives limitées, sont capables collectivement de trouver le chemin le plus court entre une source de nourriture et leur nid.

Page 6: Institut  Supérieur  d'Informatique et des Techniques de Communication

Powerpoint Templates Page 6

Les comportement (1/2)

• Un modèle expliquant ce comportement est le suivant :

1. une fourmi (appelée « éclaireuse ») parcourt plus ou moins au hasard l’environnement autour de la colonie 

2. si celle-ci découvre une source de nourriture, elle rentre plus ou moins directement au nid, en laissant sur son chemin une piste de phéromones 

3. ces phéromones étant attractives, les fourmis passant à proximité vont avoir tendance à suivre, de façon plus ou moins directe, cette piste 

4. en revenant au nid, ces mêmes fourmis vont renforcer la piste 

Page 7: Institut  Supérieur  d'Informatique et des Techniques de Communication

Powerpoint Templates Page 7

les comportement (2/2)

5.si deux pistes sont possibles pour atteindre la même source de nourriture, celle étant la plus courte sera, dans le même temps, parcourue par plus de fourmis que la longue piste 6.la piste courte sera donc de plus en plus renforcée, et donc de plus en plus attractive 7.la longue piste, elle, finira par disparaître, les phéromones étant volatiles 8.à terme, l’ensemble des fourmis a donc déterminé et « choisi » la piste la plus courte.

Page 8: Institut  Supérieur  d'Informatique et des Techniques de Communication

Powerpoint Templates Page 8

Les fonctionnalités

Page 9: Institut  Supérieur  d'Informatique et des Techniques de Communication

Powerpoint Templates Page 9

le  système fourmi

• Le système de deux manière de description :

Description généraleDescription formelle

Page 10: Institut  Supérieur  d'Informatique et des Techniques de Communication

Powerpoint Templates Page 10

Description général

• Le premier algorithme de colonies de fourmis proposé est appelé l’ Anti système(système fourmi). Il vise notamment à résoudre le problème du voyageur de commerce, où le but est de trouver le plus court chemin permettant de relier un ensemble de villes.

Page 11: Institut  Supérieur  d'Informatique et des Techniques de Communication

Powerpoint Templates Page 11

Description général

•  À chaque étape, la fourmi choisit de passer d’une ville à une autre en fonction de quelques règles :

1. elle ne peut visiter qu’une fois chaque ville 2. plus une ville est loin, moins elle a de chance

d’être choisie (c’est la « visibilité ») 3. plus l'intensité de la piste de phéromone disposée

sur l’arête entre deux villes est grande, plus le trajet aura de chance d’être choisi 

4. une fois son trajet terminé, la fourmi dépose, sur l’ensemble des arêtes parcourues, plus de phéromones si le trajet est court 

5. les pistes de phéromones s’évaporent à chaque itération.

Page 12: Institut  Supérieur  d'Informatique et des Techniques de Communication

Powerpoint Templates Page 12

Description général

Page 13: Institut  Supérieur  d'Informatique et des Techniques de Communication

Powerpoint Templates Page 13

Description formelle

• La règle de déplacement est appelée « règle aléatoire de transition proportionnelle », et est écrite mathématiquement sous la forme suivante :

Page 14: Institut  Supérieur  d'Informatique et des Techniques de Communication

Powerpoint Templates Page 14

Description formelle

• Une fois la tournée des villes effectuée, une fourmi k dépose une quantité  de phéromone sur chaque arête de son parcours :

Page 15: Institut  Supérieur  d'Informatique et des Techniques de Communication

Powerpoint Templates Page 15

Description formelle

• À la fin de chaque itération de l’algorithme, les phéromones déposées aux itérations précédentes par les fourmis s’évaporent de :

Et à la fin de l'itération, on a la somme des phéromones qui ne se sont pas évaporées et de celles qui viennent d'être déposées.

Page 16: Institut  Supérieur  d'Informatique et des Techniques de Communication

Powerpoint Templates Page 16

Principal variante

• L’algorithme de colonies de fourmis a été à l’origine surtout utilisé pour produire des solutions quasi-optimales au problème du voyageur de commerce, puis, plus généralement, aux problèmes d’optimisation combinatoire. On observe que depuis ses débuts son emploi s'est étendu à plusieurs domaines, depuis l’optimisation continue jusqu’à la classification ou encore le traitement d’image.

Page 17: Institut  Supérieur  d'Informatique et des Techniques de Communication

Powerpoint Templates Page 17

Le cadre ACO

• Ce cadre se limite cependant aux algorithmes construisant des solutions sous la forme de paramètres associés aux composants d'un graphe, à l'aide d'un modèle statistique biaisé.

• Une méthode de type ACO suit le schéma algorithmique suivant, paramétré par:

un critère d'arrêt de l’algorithme un temps de calcul ou un nombre d'itérations alloué dépassé, un seuil d'amélioration des solutions qui n’est plus satisfaisant, ou une combinaison de critères des heuristiques(éventuellement) un critère de choix des pistes à explorer ou à éliminer une construction des solutions et des pistes de

phéromones dépendant du problème à résoudre et de sa structures

Page 18: Institut  Supérieur  d'Informatique et des Techniques de Communication

Powerpoint Templates Page 18

Application (1/ 3)

• Les variantes combinatoires peuvent avoir un avantage, par rapport aux autres méta heuristiques, dans le cas où le graphe étudié peut changer dynamiquement au cours de l’exécution : la colonie de fourmis s’adaptera de façon relativement flexible aux changements. Ceci semble être intéressant pour le routage réseau.

Page 19: Institut  Supérieur  d'Informatique et des Techniques de Communication

Powerpoint Templates Page 19

Application (2/3)

• Les algorithmes de colonies de fourmis ont été appliqués à un grand nombre de problèmes d’optimisation combinatoire, allant de l'affectation quadratique au replis de protéine ou au routage de véhicules. Comme beaucoup de méta heuristiques, l’algorithme de base a été adapté aux problèmes dynamiques, en variables réelles, aux problèmes stochastiques, multi-objectifs ou aux implémentations parallèles, etc.

Page 20: Institut  Supérieur  d'Informatique et des Techniques de Communication

Powerpoint Templates Page 20

Application(3/3)

• Problème du sac à dos. Les fourmis en nombre limité privilégient la goutte de miel, en plus petite quantité mais plus intéressante que l'eau sucrée, plus abondante mais moins nutritive.

Page 21: Institut  Supérieur  d'Informatique et des Techniques de Communication

Powerpoint Templates Page 21

Algorithme de fourmis

Répéter Sélectionne aléatoire de n fourmis sur n ville Pour ide 1 a k faire Pour j de 1 a n faire Choisir le ville suivant en appliquant les

règles de choix Fin pour Fin pour Mise ajour de la piste phénomènes jusqu’à condition de fin

Page 22: Institut  Supérieur  d'Informatique et des Techniques de Communication

Powerpoint Templates Page 22

Conclusion

• D’une façon très générale, les algorithmes de colonies de fourmis sont considérés comme des méta heuristiques à population, où chaque solution est représentée par une fourmi se déplaçant sur l’espace de recherche.

• Les fourmis marquent les meilleures solutions, et tiennent compte des marquages précédents pour optimiser leur recherche.

Page 23: Institut  Supérieur  d'Informatique et des Techniques de Communication

Powerpoint Templates Page 23

• Merci pour votre attention