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 animale², de la société Eurobios³ et de l'Institut de recherches interdisciplinaires et développements en intelligence artificielle⁴ 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 quadratique⁵, 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 :