Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Colonie de fourmis Université de Moncton Gérard J. Poitras 2013 53 Faculté d’in

Colonie de fourmis Université de Moncton Gérard J. Poitras 2013 53 Faculté d’ingénierie Méthodes avancées d’ing. II GGEN6090 Faculté d’ingénierie Prof. Gérard J. Poitras, ing. Bureau : 132G2 Tél : 858-4759 Courriel : gerard.poitras@umoncton.ca Faculté d’ingénierie • Les algorithmes de colonies de fourmis sont des algorithmes inspirés du comportement des fourmis. Algorithme de colonies de fourmis • Initialement proposé par Marco Dorigo et al. dans les années 1990, le premier algorithme s’inspire du comportement des fourmis recherchant un chemin entre leur colonie et une source de nourriture. • Il est maintenant utilisé pour résoudre une classe plus large de problèmes en s’inspirant de divers aspects du comportement des fourmis. Colonie de fourmis Université de Moncton Gérard J. Poitras 2013 54 Faculté d’ingénierie • L’idée originale provient de l’observation de l’exploitation des ressources alimentaires chez les fourmis. Algorithme de colonies de fourmis • Une colonie de fourmis ayant le choix entre deux chemins d’inégale longueur menant à une source de nourriture avait tendance à utiliser le chemin le plus court. • Ils sont capables collectivement de trouver le chemin le plus court entre une source de nourriture et leur nid. Faculté d’ingénierie 1. La première fourmi trouve la source de nourriture, via un chemin quelconque, puis revient au nid en laissant derrière elle une piste de phéromone. 2. Les fourmis empruntent indifféremment des chemins possibles, mais le renforcement de la piste rend plus attrayant le chemin le plus court. 3. Les fourmis empruntent le chemin le plus court, les portions longues des autres chemins perdent leur piste de phéromones. Algorithme de colonies de fourmis • Principe : phéromone Colonie de fourmis Université de Moncton Gérard J. Poitras 2013 55 Faculté d’ingénierie • Une fourmi (appelée «éclaireuse») parcourt plus ou moins au hasard l’environnement autour de la colonie; • 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; • Ces phéromones étant attrayantes, les fourmis passant à proximité vont avoir tendance à suivre, de façon plus ou moins directe, cette piste; • En revenant au nid, ces mêmes fourmis vont renforcer la piste ; Algorithme de colonies de fourmis Faculté d’ingénierie Algorithme de colonies de fourmis Colonie de fourmis Université de Moncton Gérard J. Poitras 2013 56 Faculté d’ingénierie • 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; • La piste courte sera donc de plus en plus renforcée, et donc de plus en plus attrayante; • La longue piste, elle, finira par disparaître, les phéromones étant volatiles; • À terme, l’ensemble des fourmis a donc déterminé et «choisi» la piste la plus courte. Algorithme de colonies de fourmis Faculté d’ingénierie • Les fourmis utilisent l’environnement comme support de communication : elles échangent indirectement de l’information en déposant des phéromones, le tout décrivant l’état de leur «travail». • L’information échangée a une portée locale, seule une fourmi située à l’endroit où les phéromones ont été déposées y a accès. • Ce système repose sur des rétroactions positives (le dépôt de phéromone attire d’autres fourmis qui vont la renforcer à leur tour) et négatives (la dissipation de la piste par évaporation empêche le système de s'emballer). Algorithme de colonies de fourmis Colonie de fourmis Université de Moncton Gérard J. Poitras 2013 57 Faculté d’ingénierie • Théoriquement, si la quantité de phéromone restait identique au cours du temps sur toutes les branches, aucune piste ne serait choisie. • Grâce aux rétroactions, une faible variation sur une branche va être amplifiée et permettre alors le choix d’une branche. • L'algorithme va permettre de passer d'un état instable où aucune branche n'est plus marquer qu'une autre, vers un état stable où l'itinéraire est formé des « meilleures» branches. Algorithme de colonies de fourmis Faculté d’ingénierie • Les fourmis virtuelles ont une double nature. D’une part, elles modélisent les comportements abstraits de fourmis réelles, et d’autre part, elles peuvent être enrichies par des capacités que ne possèdent pas les fourmis réelles, afin de les rendre plus efficaces que ces dernières. • Points communs, fourmis réelles et virtuelles – Colonie d’individus coopérants, un ensemble d’entités qui se rassemblent ensemble pour trouver une "bonne" solution. – Pistes de phéromones, son rôle principal est de changer la manière dont l’environnement est perçu par les fourmis, en fonction de l’historique laissé par ces phéromones. – Évaporation des phéromones, ce mécanisme permet d’oublier lentement ce qui s’est passé avant. – Recherche du plus petit chemin reliant un point de départ (le nid) à des sites de destination (la nourriture). Algorithme de colonies de fourmis Colonie de fourmis Université de Moncton Gérard J. Poitras 2013 58 Faculté d’ingénierie • Points communs, fourmis réelles et virtuelles (suite) – Déplacement locaux, les fourmis se contentent de se déplacer entre sites adjacents du terrain. – Choix aléatoire lors des transitions, les fourmis doivent décider sur quel site adjacent se déplacer. Cette prise de décision se fait au hasard et dépend de l’information locale déposée sur le site courant. Algorithme de colonies de fourmis Faculté d’ingénierie • Les fourmis virtuelles possèdent certaines caractéristiques que ne possèdent pas les fourmis réelles : – Elles vivent dans un monde non continu, leurs déplacements consistent en des transitions d’état. – Mémoire, les fourmis virtuelles mémorisent l’historique de leurs actions. Elles peuvent aussi retenir des données supplémentaires sur leurs performances. – Nature des phéromones déposées par les fourmis virtuelles où l’évaporation des phéromones est une simple décrémentation de la valeur des variables d’états à chaque itération. – Qualité de la solution, les fourmis virtuelles déposent une quantité de phéromone proportionnelle à la qualité de la solution qu’elles ont découvert. – Retard dans le dépôt de phéromone, les fourmis virtuelles peuvent mettre à jour les pistes de phéromones de façon non immédiate : souvent elles attendent d’avoir terminé la construction de leur solution. Algorithme de colonies de fourmis Colonie de fourmis Université de Moncton Gérard J. Poitras 2013 59 Faculté d’ingénierie • Les fourmis virtuelles possèdent certaines caractéristiques que ne possèdent pas les fourmis réelles (suite) : – Capacités supplémentaires où les fourmis virtuelles peuvent être pourvues de capacités artificielles afin d’améliorer les performances du système. – Ces possibilités sont liées au problème et peuvent être: 1. l’anticipation : la fourmi étudie les états suivants pour faire son choix et non seulement l’état local. 2. le retour en arrière : une fourmi peut revenir à un état déjà parcouru, car la décision qu’elle avait prise à cet état a été mauvaise. Algorithme de colonies de fourmis Faculté d’ingénierie • Développement de l’algorithme (population initiale) Algorithme de colonies de fourmis Colonie de fourmis 8 8 8 8 8 8 8 8 8 8 888888 888888 8 8 8 8 8 8 Nourriture L1 L2 Colonie de fourmis 8 8 8 8 8 8 8 Nourriture 8 8 8 8 8888888 8888888 8 8 8 8 8 8 8 où L1 = d1, L2 = d2 et d1 > d2 τi est la quantité de phéromone déposée sur l’arête i τ1 =1 τ2 =1 Une fourmi choisit l’un des deux chemins avec une probabilité pi où roulette i p i i     2 , 1 , 2 1    Colonie de fourmis Université de Moncton Gérard J. Poitras 2013 60 Faculté d’ingénierie • Développement de l’algorithme Algorithme de colonies de fourmis Colonie de fourmis 8 8 8 8 8 Nourriture 8888888 8888888 8 8 8 8 8 8 8 8 88888888 88888888 1 2         i i i d Q où Q est un paramètre de réglage et di est la distance parcourue (la valeur de la fonction objective) Colonie de fourmis Nourriture 8888888888888888888 8888888888888888888  i i     1 (retour des fourmis) où [0 ,1] est un paramètre de réglage pour l’évaporation des phéromones. Faculté d’ingénierie • Le premier algorithme de colonies de fourmis proposé 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. • L’algorithme général repose sur un ensemble de fourmis, chacune parcourant un trajet parmi ceux qui sont possibles. • À chaque étape, la fourmi choisit de passer d’une ville à une autre en fonction de quelques règles. Algorithme de colonies de fourmis • 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. Colonie de fourmis Université de Moncton Gérard J. uploads/Litterature/ colonie-de-fourmis-13.pdf