Intelligence collective des fourmis et nouvelles techniques d'optimisation1


Pour des informations complémentaires, contacter les chercheurs, en cliquant ici
Page précédente

Les recherches sur les comportements collectifs des insectes sociaux fournissent aux informaticiens des méthodes puissantes pour la conception d'algorithmes d'optimi-sation combinatoire et de routage et de contrôle distribué. L'étude menée conjointement par des chercheurs du Laboratoire d'éthologie et cognition animale2, de la société Eurobios3 et de l'Institut de recherches interdisciplinaires et développements en intelligence artificielle4 montre que ces techniques s'appliquent aujourd'hui à tout un ensemble de problèmes scientifiques et techniques.

En plus de leur capacité, déjà surprenante, à résoudre un large spectre de problèmes " statiques ", ces techniques offrent un haut degré de flexibilité et de robustesse dans des environnements dynamiques. Elles permettent, en particulier, de résoudre de façon plus efficace des problèmes d'optimisation, comme le problème de l'assignation quadratique5, et également d'adapter le flux des communications circulant sur un réseau.

Les sociétés d'insectes ont une capacité à résoudre des problèmes d'une manière très flexible (la colonie s'adapte aux brusques changements d'environnement) et robuste (la colonie continue de fonctionner lorsque certains individus échouent à accomplir leur tâche). Les problèmes quotidiens résolus par une colonie sont nombreux et de nature très variée : recherche de nourriture, construction du nid, division du travail et allocation des tâches entre les individus, etc. La plupart de ces problèmes se retrouvent dans le domaine des sciences de l'ingénieur, en informatique et en robotique notamment.

Les études réalisées par les éthologistes ont montré que certains comportements collectifs des insectes sociaux étaient auto-organisés. L'auto-organisation caractérise des processus au cours desquels des structures émergent au niveau collectif, à partir d'une multitude d'interactions simples entre insectes, sans être codées explicitement au niveau individuel. Certaines interactions - une fourmi qui suit la piste de phéromone laissée par une autre - aident à résoudre collectivement des problèmes difficiles, par exemple trouver le chemin le plus court parmi d'innombrables voies conduisant à une source de nourriture.

Les informaticiens et les ingénieurs ont pu transformer des modèles du comportement collectif des insectes sociaux en méthodes utiles pour l'optimisation et le contrôle. Un nouveau domaine de recherche a vu le jour qui a pour objet de transformer la connaissance que les éthologistes ont des capacités collectives de résolution de problèmes des insectes sociaux en techniques artificielles de résolution de problèmes : c'est l'intelligence en essaim. Parmi les techniques de l'intelligence en essaim, certaines sont arrivées à maturité. Les algorithmes de contrôle et d'optimisation inspirés de modèles de recherche collective de nourriture chez les fourmis en particulier, ont connu un succès inattendu et portent le nom d'"optimisation par colonie de fourmis" et de "routage par colonie de fourmis".

Le comportement collectif des fourmis d'Argentine (Linepithema humile) a servi de source d'inspiration au développement de techniques d'intelligence en essaim.
© Guy Theraulaz. CNRS, Toulouse

L'optimisation par colonie de fourmis
Les éthologistes ont montré que les fourmis étaient capables de sélectionner le plus court chemin pour aller du nid à une source de nourriture grâce au dépôt et au suivi de pistes de phéromone. Lorsqu'une colonie de fourmis d'Argentine doit emprunter un pont à deux branches de longueurs différentes pour exploiter une source de nourriture, elle sélectionne la branche courte si la différence entre les longueurs des branches est suffisamment importante (voir photo). Les fourmis déposent de la phéromone à l'aller vers la source de nourriture et au retour vers le nid. Au départ, le choix est aléatoire mais la branche courte devient vite la plus marquée car les fourmis qui l'empruntent arrivent plus vite au nid et auront statistiquement plus de chance de l'emprunter lorsqu'elles retourneront vers la source de nourriture.

En utilisant le même principe, les informaticiens ont conçu un moyen de résoudre le célèbre problème du voyageur de commerce. Ce problème consiste à trouver le chemin le plus court en passant une seule fois par un nombre donné de villes. En utilisant des fourmis artificielles conçues pour déposer des pistes de phéromone dont la concentration varie en fonction de la distance totale qu'elles ont parcourue, on peut obtenir des chemins quasi optimaux (voir tableau). Cette optimisation est une conséquence de l'interaction subtile entre renforcement et évaporation de la phéromone, qui fait que seules les meilleures liaisons subsistent.

Le routage par colonie de fourmis
Les techniques de l'intelligence en essaim démontrent également toute leur puissance dans le cas de problèmes dont l'énoncé, les données ou les paramètres varient en permanence sur des échelles de temps très courtes. C'est le cas du routage dans les réseaux de communications. Schémati-quement, le problème est le suivant : lorsqu'une communication est établie entre deux ordinateurs, le message initial est découpé en paquets de données qui circulent le long d'un réseau constitué de lignes de transmission - dont les capacités de débit peuvent être très diverses et variables au cours du temps - et de routeurs qui constituent les nœuds de ce réseau. La fonction des routeurs est de diriger les paquets de données vers l'un des autres routeurs du réseau et ce, jusqu'à ce que les paquets de données arrivent à leur destination finale. Mais le routeur doit aussi tenir compte de l'importance du trafic sur les voies de communication auquel il est relié de manière à éviter l'engorgement de ces voies. Il arrive donc très souvent que des paquets de données d'un même message suivent des voies complètement différentes.

Pour résoudre ce problème, on fait circuler en parallèle avec les paquets de données, des agents de routage, sorte de fourmis virtuelles, qui analysent en temps réel l'état d'encombrement des différentes voies du réseau et qui indiquent ensuite cet état à chacun des routeurs. Les fourmis calculent le temps qu'elles mettent pour aller d'un nœud du réseau à un autre et marquent ensuite à l'aide de phéromone virtuelle la voie qu'elles viennent d'emprunter. Plus le délai est court, plus l'intensité du marquage est importante. Ainsi, lorsqu'un paquet de données arrive au niveau d'un routeur donné, il aura d'autant plus de chance d'emprunter une voie que la densité de phéromone virtuelle sur cette voie sera importante. De cette manière, le réseau s'adapte en permanence et de manière totalement décentralisée à l'activité du trafic (voir figure).


Résultat typique d'une comparaison entre AntNet, un algorithme de routage par colonie de fourmis, avec d'autres algorithmes de routage répandus pour la commutation de paquets. Daemon est une approximation d'un algorithme idéal et offre une borne à la meilleure performance possible. Le réseau est simulé en condition de fort trafic avec des caractéristiques de trafic stochastiques. Au temps t = 400, on simule un accroissement soudain du trafic qui dure 120 secondes et amène le réseau à saturation. Le graphe du haut compare le flux du réseau pour les différents algorithmes, tandis que le graphe du bas compare les retards moyens des messages sur une fenêtre de 5s. AntNet offre le même flux de paquets que les meilleurs algorithmes tout en maintenant un retard moyen bien inférieur à tous les autres algorithmes de routage.

 

Références :

  • E. Bonabeau, M. Dorigo and G. Theraulaz. Inspiration for optimization from social insect behaviour. Nature, Vol. 406, juillet 2000, pp. 39-42.
  • Bonabeau, E. & Theraulaz, G. (2000). Swarm Smarts. Scientific American, 282 (3): pp. 72-79.
  • E. Bonabeau, M. Dorigo and G. Theraulaz. (1999). Swarm Intelligence : From Natural to Artificial Systems. Oxford University Press.

     


    Oliver30 Eil50 Eil75
    (30-city) (50-city) (75-city)

    OCF 420 425 525
    (830) (1,830) (3,480)

    Genetic 421 428 545
    algorithm (3,200) (25,000) (80,000)

    Evolutionary 420 426 542
    programming (40,000) (100,000) (325,000)

    Simulated 424 443 580
    annealing (24,617) (68,512) (173,250)

    Optimal 420 425 535
    solution

    Comparaison des performances de la technique d'optimisation par colonie de fourmis (OCF) avec plusieurs autres heuristiques générales appliquées au problème du voyageur de commerce. Oliver30, Eil50 et Eil75 sont des exemples de problèmes comprenant respectivement 30, 50 et 75 villes. Chaque case de la table indique la meilleure solution trouvée par l'algorithme et, entre parenthèses, le nombre d'itérations de l'algorithme nécessaires pour trouver cette solution.
    © Elsevier, (Dorigo, M. & Gambardella, L. M. Ant colonies for the traveling salesman problem. BioSystems, 43, pp. 73-81 (1997)).


    1 Il s'agit d'optimisation combinatoire statique et dynamique. Un problème d'optimisation combinatoire est un problème où il faut minimiser une certaine fonction (dite de coût) sur un ensemble fini de configurations. C'est un domaine important en recherche opérationnelle. Dans les deux exemples présentés, il s'agit d'une part de la distance totale reliant toutes les villes d'un réseau (ACO) et du délai d'acheminement de données dans un réseau de télécommunication (ACR).

    2 Guy Theraulaz, CNRS-Université Toulouse 3.

    3 Eric Bonabeau, Paris.

    4 Marco Dorigo, Université Libre de Bruxelles.

    5 Le problème de l'assignation quadratique se définit de la manière suivante : soit un ensemble d'activités distribuées sur des sites géographique différents. Les activités échangent entre elles des flux de matériaux. Le problème consiste à trouver une organisation des activités sur les différents sites qui minimise la somme du produit des flux par les distances séparant les activités.

  •