Les fourmis partent dîner

Comment les fourmis font-elles pour se communiquer l’emplacement de la nourriture qu’elles veulent aller chercher ?

Pista roja El 5 junio 2022  - Escrito por  Léo Dana Ver los comentarios

L’une des tâches importantes des fourmis ouvrières pour faire survivre la colonie est de trouver de la nourriture et de la ramener à la fourmilière. Cette tâche, plutôt simple en apparence, à été très bien optimisée par les fourmis. Plutôt que de rechercher indépendamment la nourriture dans leur environnement, les fourmis se transmettent de l’information sur l’emplacement de la nourriture. Nous savons notamment qu’elles utilisent des phéromones pour se guider dans l’espace. Lorsqu’une fourmi va trouver de la nourriture, elle va laisser des phéromones pour guider les prochaines fourmis vers cette source de nourriture.

Mais ceci suffit-il à guider efficacement les fourmis ? C’est la question que se sont posés des chercheurs [1], en considérant un modèle de déplacement aléatoire en fonction du nombre de phéromones.

Cet article a été écrit à la suite du stage de recherche que j’ai effectué durant l’été 2021 sous la direction de Bruno Schappira; nous présentons leurs travaux ainsi que les résultats obtenus lors du stage.

Problème

La question qui nous intéresse vient de l’observation suivante : lorsque les fourmis cherchent de la nourriture dans un labyrinthe, le mouvement des premières fourmis apparaît aléatoire, puis à partir d’un moment toutes les fourmis empruntent un seul chemin, qui est le plus court. Comment peut-on rendre compte de ce phénomène mathématiquement ?

Une réponse peut être que la fourmilière est un organisme auto-organisateur, c’est-à-dire que les individus, en suivant certaines lois arrivent à s’organiser à grande échelle, même sans en avoir conscience à leur petite échelle. Cet article de Pierre Degond publié sur ce site en parle d’ailleurs. Ici, nous souhaitons trouver un mécanisme simple qui permettrait d’expliquer le phénomène. Nous allons introduire le modèle mathématique proposé par les chercheurs, ainsi que les différents paramètres qui influencent le modèle. Ce formalisme permettra notamment de donner un sens clair à la question, et d’y répondre.

Modèle

Comme annoncé, nous voulons faire marcher des fourmis dans un labyrinthe et regarder si elles arrivent à trouver la source de nourriture qui s’y trouve. Le labyrinthe sera donc modélisé par un graphe. Un graphe est un ensemble de nœuds et d’arêtes qui les relient.

PNG - 71.1 KB

Les fourmis vont donc se déplacer sur des graphes composés d’un seul morceau et ayant deux nœuds spéciaux : le nœud N pour la fourmilière (Nest) et le nœud F pour la nourriture (Food). Les fourmis se déplacent alors de nœud en nœud en partant de N jusqu’à arriver en F, puis rentrent à la fourmilière.

PNG - 46.6 KB

On ne regarde que des graphes composés d’un morceau car cela nous garantit que la fourmi trouvera toujours F en partant de N. De plus, des endroits que la fourmi ne pourrait pas atteindre ne sont pas intéressants pour le problème.

Comment une fourmi se déplace-t-elle ?

La fourmi, lorsqu’elle est en un nœud, va choisir aléatoirement une des arêtes liées à ce nœud et la parcourir. Elle arrive alors à un nouveau nœud et recommence le processus. La fourmi ne s’arrête que lorsqu’elle arrive en F : elle a atteint son objectif et va alors rentrer à la fourmilière.
Ici, il faut encore spécifier ce que veut dire «choisir aléatoirement», car il existe plusieurs aléatoires possibles pour ce déplacement. Nous voulons que la fourmi choisisse l’arête en fonction des phéromones que les fourmis y ont déposées pour qu’elles puissent transmettre l’information de l’emplacement où se trouve la nourriture aux autres. Ainsi, la probabilité pour une certaine arête d’être prise par la fourmi, sera proportionnelle à une fonction $f$ de la quantité de phéromones de cette arête. Cette fonction est un des paramètres importants du modèle que nous discuterons plus tard.

Pour chaque arête $e$ du graphe, nous lui associons maintenant son poids $P_e$ correspondant au nombre de phéromones déposées sur ce chemin. La probabilité de prendre l’arête $e$ en partant du sommet A est donnée par la formule suivante : \[\frac{f(P_{e})}{\sum_{a\sim{A}}{f(P_{a})}}\] où la somme est faite sur toutes les arêtes ayant pour sommet A. (Nous ne considérerons dans la suite que le cas où $f(x) = x$, ce qui donne la formule $\frac{P_{e}}{\sum_{a\sim{A}}{P_{a}}}$, qui est le cas de stricte proportionnalité.)

PNG - 62.6 KB

Graphe avec 3 arêtes illustrant la façon dont une fourmi a choisi une arête.

Explicitons ce qu’il se passe dans le cas simple où f(x)=x. La fourmi est en N et doit choisir entre les arêtes 1, 2 ou 3. La probabilité de prendre l’arête 2 est donc ici \[\frac{P_{2}}{P_{1}+P_{2}+P_{3}} = \frac{4}{1+4+3} = \frac{1}{2}\] Celle de l’arête 1 est $\frac{1}{8}$, et celle de l’arête 3 est $\frac{3}{8}$.
Nous avons à présent les bases du modèle : une fourmi part de N, marche aléatoirement de nœud en nœud en fonction des poids des arêtes, et arrive en F au bout d’un moment. Il nous reste à voir comment la fourmi renforce les nœuds, c’est-à-dire, comment le poids des arrêtes, correspondant à la quantité de phéromones sur le chemin, est augmenté par les fourmis.

Comment les fourmis reviennent à la fourmilière ?

Maintenant que les fourmis savent se déplacer dans l’espace, il faut qu’elles sachent où déposer leurs phéromones pour aider au mieux les autres fourmis à atteindre elles aussi la nourriture.

Une première idée intuitive est que les fourmis déposent les phéromones partout où elles passent et reviennent par le même chemin que celui par lequel elles sont arrivées. Mais cette solution n’est pas très bonne : les fourmis ne trouvent pas le chemin le plus court.

On va choisir ici une autre façon de déposer les phéromones. La dépose des phéromones sera faite par la fourmi lorsqu’elle revient à son nid : elle dépose les phéromones sur son chemin de retour. Le choix du chemin de retour est lui aussi un paramètre clé du modèle. Une possibilité est que la fourmi dépose des phéromones sur l’un des chemins les plus courts parmi ceux qu’elle a visités. Mais la façon la plus naturelle du point de vue mathématique de choisir le chemin est appelée Retour Sans Boucle (RSB). A l’aller, la fourmi mémorise à chaque nouveau nœud, le chemin qui l’a mené à ce nœud. Puis au retour, la fourmi fait le chemin inverse de l’aller, mais à chaque nœud où elle arrive, elle repart par le chemin qu’elle a pris en premier pour arriver au nœud. Cette définition est assez complexe, nous allons donc l’illustrer par un exemple.

Exemple de retour

Exemple de retour

Pour rendre l’explication de la façon dont la fourmi revient à la fourmilière facile, nous nous basons sur la vidéo ci-contre. La fourmi est représentée par le point orange à l’aller, et devient bleue au retour.

Dans ce labyrinthe, on voit un parcours fait par la fourmi qui va successivement en N,I,B,A,I,A,F. Il est d’ailleurs bon de noter qu’une fourmi peut revenir sur ces pas lorsqu’elle recherche la nourriture, ici elle fait $A\rightarrow I$ puis $I\rightarrow A$.
Pour revenir, elle se trouve en F et se demande d’où elle vient. Ici il n’y a qu’un choix, elle va donc revenir en A. Même question en A, sauf qu’ici la fourmi a fait $I\rightarrow A$ et $B\rightarrow A$. Elle va cependant choisir le nœud par lequel elle est arrivée en A la première fois : ici c’est B. Puis de même elle revient en I puis N.

On peut noter que ce choix de chemin de retour garantit à la fourmi de toujours revenir à N, mais elle ne prendra pas forcément le plus court chemin. Ce chemin a une propriété intéressante : il demande de se souvenir seulement d’une partie du trajet pour pouvoir revenir à N, même si cela se fait au détriment de prendre le chemin le pus rapide. La fourmi aurait pu ici ne pas passer par B, mais directement aller sur le retour de A vers I. Mais imaginer le plan du labyrinthe pour prendre le trajet optimal requiert certainement plus de calculs pour la fourmi. Nous faisons pour ces raisons l’hypothèse d’un retour RSB.

Nous allons à présent pouvoir nous intéresser au comportement des fourmis après un grand nombre de passages, pour voir l’effet des phéromones sur le trajet des fourmis.

Comment se comporte la nième fourmi ?

Dans le cadre mathématique que nous avons introduit, lorsqu’une fourmi effectue une marche sur le graphe et rentre au nid, la prochaine fourmi va effectuer une marche sur le même graphe, les nœuds auront donc un poids différent pour la deuxième fourmi. Nous nous intéressons alors au déplacement de la 10000e fourmi : quel chemin va-t-elle prendre ? Prendra-t-elle le plus court ?

Il n’est pas intuitif avec la définition donnée que la fourmi doive prendre un certain chemin plutôt qu’un autre. Regardons alors un exemple sur un labyrinthe simple.

PNG - 99.8 KB

Graphe illustrant la façon dont les phéromones changent après le passage d’une fourmi.

Le graphe ci-dessus servira de base pour les notations de cette partie, en particulier ici, la nourriture se trouvant en A, B et C est la même (on peut imaginer que les points sont les mêmes, mais pour la visibilité ils sont distingués sur le schéma). En partant de N, la fourmi a deux choix : soit elle va directement à C, soit elle prend le nœud intermédiaire I. Dans le premier cas, la marche est directement terminée et la fourmi va renforcer l’arête 1 : \[P_{1}(n+1) = P_{1}(n) + 1\]
Dans le second cas, la fourmi peut maintenant aller en A ou B, ou bien revenir au noeud N. Arriver en A ou B est donc plus compliqué pour la fourmi que d’aller en C à partir de N. On voit donc que dans ce cas il serait logique qu’à terme toutes les fourmis aillent directement de N à F. C’est ce qui se passe pour le modèle et nous allons le montrer.

Lorsque $n=0$, tous les poids valent 1 : il n’y a aucune phéromone, la première fourmi n’a donc aucune préférence. Nous voulons à présent calculer la probabilité d’atteindre C avant d’atteindre A ou B. On peut alors regarder tous les chemins qui vont de N à C sans passer par A ou B, calculer leurs probabilités et ajouter ces probabilités pour trouver le résultat. Ici les chemins sont $N\rightarrow C$, $N\rightarrow I\rightarrow N\rightarrow C$, etc. On peut numéroter les chemins par le nombre de fois où il passe par I : $c_{0}$, $c_{1}$... On calcule alors les trois probabilités qui nous intéressent :
\[p_{NC} = \mathbb{P}(N\rightarrow C) = \frac{P_{1}(1)}{P_{1}(1)+P_{2}(1)} = \frac{1}{2}\]
\[p_{NI} =\mathbb{P}(N\rightarrow I) = \frac{P_{2}(1)}{P_{1}(1)+P_{2}(1)} = \frac{1}{2}\]
\[p_{IN} =\mathbb{P}(I\rightarrow N) = \frac{P_{2}(1)}{P_{2}(1)+P_{3}(1)+P_{4}(1)} = \frac{1}{3}\]

Enfin, on utilise l’indépendance du choix du nœud par la fourmi pour dire que \[\mathbb{P}(N\rightarrow I\rightarrow N) = \mathbb{P}(N\rightarrow I)\mathbb{P}(I\rightarrow N)\]
On en déduit alors que \[\mathbb{P}(c_{i}) = p_{NC}\times p_{NI}^{i}\times p_{IN}^{i}\] car on effectue i aller-retour au point I. On trouve \[\mathbb{P}(c_{i}) = \frac{1}{2^{i+1}3^{i}}\] En sommant tous les chemins, on trouve finalement que la probabilité d’arriver en C est \[\mathbb{P}(C) = \frac{3}{5}\]
On trouve bien le résultat attendu : la première fourmi a plus de chance d’aller de N à C, qu’à A ou B. Donc elle a beaucoup de chances de renforcer l’arête 1. Ceci va alors encore augmenter ses chances de prendre l’arête C, etc. Finalement, on peut montrer par des techniques probabilistes que l’on a toujours $\frac{P_{1}(n)}{n}\rightarrow 1$ lorsque $n\rightarrow +\infty$ : après un long nombre de fourmis passées, la proportion des fourmis ayant emprunté le chemin 1 est de 1 (toutes sauf un nombre négligeable devant le nombre total de fourmis).

Nous avons regardé ici un exemple simple de graphe, mais les calculs sont plus complexes lorsque la structure du graphe est différente. Néanmoins, on peut appliquer les mêmes techniques de calcul en dénombrant les chemins pour une certaine classe de graphe. Les théorèmes actuels permettent de prédire que les fourmis trouvent le plus court chemin pour cette classe : ce sont les graphes Série-Parallèle.

Graphe Série-Parallèle et Losange

La classe des graphes Série-Parallèle (ou SP) est un ensemble de graphes construits récursivement à partir de deux graphes $G_{1}$ et $G_{2}$ pour construire $G$ : soit en les plaçant en parallèle en fusionnant $N_{1} = N_{2} = N$ et $F_{1} = F_{2} = F$, soit en les plaçant en série en fusionnant $F_{1} = N_{2}$ et $N_{1} = N$, $ F_{2} = F$.

PNG - 171.1 KB

L’avantage d’utiliser ces graphes est que l’on peut intuitivement comprendre quel chemin la fourmi va prendre. Si $G$ est un graphe SP composé de $G_{1}$ et $G_{2}$ en série, alors on sait que la fourmi doit prendre un chemin dans $G_{1}$ et un autre dans $G_{2}$. On peut alors regarder ce qu’il se passe dans chacun des sous-graphes. De même pour la mise en parallèle, on sait alors que la fourmi emprunte un graphe ou l’autre, donc qu’à la fin on va renforcer un chemin soit de $G_{1}$, soit de $G_{2}$.
C’est notamment cette propriété qui permet aux auteurs de [1] d’arriver au même résultat que dans le cas étudié précédemment :

Théorème. Si G est un graphe SP, alors pour chaque arête $e$ du graphe on a $\frac{P_{e}(n)}{n}\rightarrow X_{e}$ lorsque $n\rightarrow +\infty$, avec $X_{e}$ une variable aléatoire presque sûrement positive si e est sur un plus court chemin de N à F (on parle de chemin géodésique), et presque sûrement nulle sinon.
PNG - 65 KB

Simulation pour 10000 fourmis. La proportion de chaque arête vérifie bien le théorème.

Notre question initiale est donc résolue pour ces graphes, mais qu’en est-il des graphes qui ne sont pas SP ? Le plus simple est appelé le graphe Losange, et le même théorème est vérifié pour ce graphe.

PNG - 79.5 KB

Pour le reste des graphes, il n’existe pas de preuve que les fourmis trouvent le plus court chemin. Cependant, les simulations informatiques conjecturent que le théorème reste vrai.

D’autres questions et résultats

Dans cette section, je vais finalement discuter deux des questions sur lesquelles j’ai pu travailler pendant mon stage [2]. Cette section est un peu plus avancée que le début de l’article.

Densité des poids limites : Le théorème de la section précédente nous a révélé l’existence de la variable $X_{e}$. Cette variable aléatoire est nulle si $e$ n’est pas sur une géodésique du graphe. Mais si elle y est, tout ce que l’on sait c’est qu’elle n’est pas nulle. La question naturelle est alors de se demander quelle est sa loi ? C’est-à-dire, de répondre par exemple à la question «est-il plus probable d’observer que 5% des fourmis passent sur l’arrête, ou que 50% des fourmis y passent ?».
Mais cette question est très difficile et nous allons simplement nous demander si la proportion limite peut prendre toutes les valeurs entre 0 et 1, ou s’il y a des valeurs inaccessibles. Ce genre de variable aléatoire est dite à densité. On a alors un résultat pour G un arbre que les poids limites des arrêtes sur les géodésiques valent soit 1, soit sont à densité.

Sur- et Sous-linéarité : Nous avons introduit plus tôt la fonction $f$ qui modélisait à quel point les fourmis prennent en compte les phéromones déposées sur les chemins. Que se passe-t-il alors si l’on utilise une autre fonction que $f(x)=x$ ? En général il est difficile de prévoir le comportement du système, cependant certains résultats sont connus pour les fonctions $f_{\alpha}(x) = x^{\alpha}$, avec $\alpha$ différent de 1.
Lorsque $\alpha>1$, la fonction $f_{\alpha}$ croit plus vite que $f_{1}$, on parle donc de modèle sur-linéaire. Dans ce cas, les fourmis ne trouvent pas le plus court chemin. Un seul chemin de N à F aura les $X_{e}$ non nuls, mais ce chemin ne sera pas obligatoirement une géodésique.

PNG - 38.9 KB

Simulation pour 10000 fourmis de la proportion de fourmis empruntant chaque arête, avec $\alpha=2$. Les fourmis n’ont pas trouvé la géodésique.

Lorsque $\alpha<1$, on parle de modèle sous-linéaire. Dans ce cas, les fourmis ne trouvent pas le plus court chemin non plus. Tous les chemins de N à F auront les $X_{e}$ non nuls, et avec des poids fixés à l’avance par la structure du graphe SP (et que l’on peut calculer).

PNG - 68.3 KB

Même simulation pour $\alpha=\frac{1}{2}$. Les valeurs sur chaque arête sont fixées par la forme du graphe.

Ce résultat montre que la valeur $\alpha=1$, que nous avons étudiée plus tôt, est bien la seule intéressante dans ce modèle.

Post-scriptum :

Je remercie Mr Aurélien Alvarez pour m’avoir aidé dans le processus de publication, Mr Rémi Coulon et Mr Nicolas Bedaride pour avoir relu l’article et relevé les fautes, ainsi que le personnel d’Images des Mathématiques pour m’avoir accompagné sur la plateforme.

Article édité par Aurélien Alvarez

Notas

[1arXiv:2010.04820 ; Kious D. $\&$ Mailler C. $\&$ Schapira B. (2020), Finding geodesics on graphs using reinforcement learning, Cornwell Universit

[2Marche aléatoire de fourmis sur un graphe, Léo Dana, 2021, rapport de stage

PDF - 325.7 KB

Comparte este artículo

Para citar este artículo:

Léo Dana — «Les fourmis partent dîner» — Images des Mathématiques, CNRS, 2022

Comentario sobre el artículo

Dejar un comentario

Foro sólo para inscritos

Para participar en este foro, debe registrarte previamente. Gracias por indicar a continuación el identificador personal que se le ha suministrado. Si no está inscrito/a, debe inscribirse.

Conexióninscribirse¿contraseña olvidada?

La traducción del sitio del francés al castellano se realiza gracias al apoyo de diversas instituciones de matemáticas de América Latina.