Remerciez-le!

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

1 Complexité - Intelligence en essaim et insectes sociaux Julie Dugdale 2 Somma

1 Complexité - Intelligence en essaim et insectes sociaux Julie Dugdale 2 Sommaire Qu’est-ce que l’intelligence en essaim? Caractéristiques d’un essaim Sociétés d’insectes Intelligence & sociétés d’insectes Algorithmes d’optimisation par colonies de fourmis Problème du voyageur de commerce Stigmergie 3 Intelligence en essaim L’intelligence en essaim est une technique d’intelligence artificielle basée sur l’étude du comportement collectif dans les systèmes décentralisés et auto-organisés Terme introduit par Beni & Wang 1989 (robotique en essaim) Selon Bonabeau et al. “Toute tentative de concevoir des algorithmes ou moteurs distribués de résolution de problème inspirés par le comportement collectif des colonies d’insectes sociaux et d’autres sociétés animales.” [Bonabeau, Dorigo, and Theraulaz, 1999] 4 Qu’est-ce que l’intelligence en essaim? Nouvelle métaphore informatique pour la résolution des problèmes distribués. Basée sur les principes expliquant le comportement des systèmes naturels composés de nombreux agents, tels que les colonies de fourmis et les groupes d’oiseaux. Idée: • L’étude des systèmes naturels montrant de l’intelligence en essaim, • L’application des principes au contrôle des systèmes d’agents mobiles simulés et distribués. Les applications incluent les algorithmes d’optimisation, les réseaux de communications, et la robotique. 5 Caractéristiques d’un essaim Distribués, pas de contrôle central ou de source de données Pas de modèle (explicite) de l’environnement Perception de l’environnement Capacité de changer l’environnement 6 Intelligence en essaim L’essaim est capable de faire des choses (X) que les individus ne peuvent pas faire La capacité de faire X est une propriété émergente de l’essaim Les membres individuels se comportent selon des règles simples, utilisant la communication locale 7 Fourmis, Termites, Abeilles, etc. Quelques uns des systèmes naturels auto-organisés les plus impressionnant sont trouvés dans le monde des insectes coloniaux… De telles espèces… • Cherchent de la nourriture , partagent les ressources coloniales • Construisent des ruches complexes, des nids, etc. • Partagent le travail efficacement et dynamiquement parmi la colonie • Trient et rassemblent différents objets (œufs, cadavres, etc.) • Coopèrent pour déplacer des objets, combattre des ennemis, etc. 8 Sociétés d’insectes Un modèle naturel de résolution de problème distribuée Le répertoire comportemental des insectes est limité Leurs systèmes cognitifs ne sont pas suffisamment puissants pour qu’un insecte • Aie accès à toute l’information sur l’état de la colonie • Garantisse le partage approprié du travail ..pour sécuriser le progrès de la colonie La colonie dans son ensemble montre un comportement stable et autorégulé, qui s’adapte facilement aux caractéristiques imprévisibles de l’environnement dans lequel elle évolue 9 Intelligence & Sociétés d’insectes Les sociétés d’insectes sociaux montrent de l’intelligence en essaim Intelligence (ici): • Capacité de résoudre des problèmes dans un domaine réel ou abstrait • Capacité de produire un comportement approprié à une situation Qu’est-ce qui a de l’intelligence? • Un système naturel d’un ou de plusieurs agents • Un système artificiel d’1 ou plusieurs agents (entités informatiques ou robots) 10 Intelligence & sociétés d’insectes Comment cette intelligence est obtenue? • Auto-organisation: interactions locales entre insectes, et entre les insectes et l’environnement, produisent des motifs émergents et des configurations qui ‘résolvent le problème’ • Spécialisation (assignation de tâche) : • Par âge (chez les abeilles, travailleurs jeunes -> tâches de la ruche, construction, préparation de nourriture, etc. travailleurs plus âgés -> ramènent de l’eau, du pollen, etc.) • Par morphologie, (des individus sont plus adaptés à certaines tâches -> fourmis avec de larges mandibules défendent le nid) • Par comportement, (fourmis identiques remplissent des tâches constantes dans le temps, par exemple couver – pas de modification du comportement) 11 Recherche de l’itinéraire le plus court Un résultat impressionnant des expérimentations de fourmis est leur capacité pour une colonie de découvrir les itinéraires les plus courts vers les ressources (par exemple la nourriture): Un chemin de phéromone est maintenant plus fort que les autres, dirigeant les fourmis vers la nourriture par l’itinéraire le plus court. nid food En cherchant, les fourmis déposent un chemin de phéromone à évaporation lente. Celles qui trouvent la nourriture en premier retournent au nid en premier. 12 Comportement de fourmis Le plus de fourmis suivent un chemin, le plus attractif devient ce chemin puisqu’il est suivi 13 Comportement de fourmis Même quand des chemins sont égaux, le comportement renforcera un chemin sur les autres -> convergence (Deneubourg et al) 14 Sélection d’itinéraire Les fourmis sont forcées de choisir si elles devraient aller à droite ou à gauche, et ce choix est fait aléatoirement Accumulation de phéromone est plus rapide sur les chemins les plus courts La différence de contenu de phéromone entre les deux chemins, dans le temps, force les fourmis à choisir le chemin le plus court Mécanisme de feedback positif permettant d’effectuer la recherche de l’itinéraire le plus court dans le même temps que la recherche de nourriture Différents problèmes d’optimisation ont été explorés en utilisant une simulation de ce comportement réel de fourmi.. 15 Problème du voyageur de commerce (ou TSP, Travelling Salesman Problem) 16 Définition du problème TSP OBJECTIF Etant donné un ensemble de n villes, le problème du voyageur de commerce demande à un voyageur de commerce de trouver l’itinéraire le plus court entre les villes données et de retourner à la ville de départ, en sachant que chaque ville ne peut être visitée qu’1 seule fois 17 Pourquoi est-ce difficile à résoudre? Trouver la meilleure solution pourrait passer par la recherche exhaustive de toutes les combinaisons de villes. Cela peut être prohibitif quand ‘n’ devient très grand 18 Heuristiques du TSP Variété d’heuristiques (par exemple algorithmes informatiques) utilisées pour résoudre le TSP Le TSP n’est pas seulement difficile en théorie, il est aussi difficile à résoudre en pratique car il est très couteux algorithmiquement Conséquence: il y a une variété de méthodes proposées pour le TSP Le « Voisin le plus proche » est une approche typique couteuse. 19 Une autre approche… Les algorithmes d’optimisation par colonie de fourmis (ACO pour Ants Colony Optimisation) 20 Les algorithmes d’optimisation par colonie de fourmis Les fourmis ne sont pas les seules à devoir trouver des chemins optimaux. Le trafic dans les systèmes de télécommunications, l’internet, les routes, le rail, et la mer bénéficieraient tous d’une réduction de la congestion qui pourrait résulter de l’utilisation des algorithmes d’itinéraires efficaces. Les aspects du comportement de colonie de fourmis sont utilisés pour concevoir de nouveaux types d’algorithmes et de robots Les algorithmes d’optimisation par colonie de fourmis : Idées de base Les fourmis sont des agents qui: • Se déplacent entre les nœuds d’un graphe • Choisissent où se diriger selon la force de phéromone Le chemin d’une fourmi représente une solution candidate spécifique Quand une fourmi a terminé une solution, la phéromone est laissée sur son chemin, selon la qualité de la solution. 22 Utilisent un mécanisme de feedback positif Possèdent une architecture informatique distribuée Utilisent une structure de donnée globale qui change dynamiquement à chaque fois qu’une fourmi traverse l’itinéraire Possèdent un élément de calcul distribué concernant la population de fourmis Impliquent des transitions statistiques entre les noeuds Les algorithmes d’optimisation par colonie de fourmis : Caractéristiques 23 Recherche d’itinéraire inspirée des fourmis Un système de navigation en voiture peut s’inspirer de ces algorithmes. Donc les itinéraires contenant des nœuds congestionnes sont graduellement affaiblis, obligeant les fourmis à prendre des itinéraires alternatifs. Une “fourmi” traverse le réseau en suivant le chemin de plus forte phéromones entre A et B. A la fin du voyage, la "fourmi" laisse des phéromones le long de l’itinéraire, en laissant moins de phéromones aux nœuds congestionnés. Puisque de nombreuses fourmis traversent le réseau constamment et que la phéromone s’évapore graduellement, le système s’adapte automatiquement à la charge actuelle du réseau. A B 24 Organigramme ACO Toutes les villes ont été visitées? Le nombre d’itérations maximum a été effectué Début ACO Localiser aléatoirement les fourmis dans les villes de la grille et stocker la ville actuelle dans une liste tabou Déterminer statistiquement quelle ville suivante visiter Passer à la ville suivante et placer cette ville dans la liste tabou Stocker la longueur de l’itinéraire et effacer la liste tabou Déterminer l’itinéraire le plus court jusqu’à maintenant et mettre la phéromone à jour NON OUI STOP ACO OUI NON 25 Différentes variations des algorithmes par colonie de fourmis Le cycle-fourmi est l’approche étudiée jusqu’ici - L’information est mise à jour à la fin de chaque itinéraire en fonction de sa longueur La densité-fourmi est une approche où la quantité de phéromone Q est déposée après qu’un segment soit traversé - Approche couteuse (information locale) et ne procurant pas d’information relative La quantité-fourmi est une approche où la quantité de 26 Est-ce que cela marche?  Dans « Swarm Intelligence », Bonabeau, Dorigo & Théraulaz affirment que “les travaux sur la recherche d’itinéraire à base de fourmis commencent seulement… mais dans toutes les situations testées il apparaît…que la recherche d’itinéraires à base de fourmis avec des agents patrouillant le réseau surpassent tous les autres algorithmes de recherche d’itinéraires”. • France Télécom développe des algorithmes pour leur système Les algorithmes utilisent le trafic constant des utilisateurs pour construire un cliché à jour de ce qu’il uploads/Societe et culture/ complexity-lecture-04-fr-2008-swarm-intelligence.pdf