ANTs 22 ans après la première version…

, par MiKaël Navarro

Le but est donc ici de reprendre le projet ANTs afin de cette fois-ci récolter de la nourriture :

Quand une fourmi découvre de la nourriture, elle prélève le plus gros morceau qu’elle est capable de porter, puis elle le rapporte à la fourmilière. Une fois la nourriture stockée en lieu sûr, la fourmi retourne au travail.

Modélisation du problème

Le modèle est simplifié à l’extrême afin de faciliter son étude. Le monde est constitué d’une grille de taille finie (les bords sont infranchissables) dont chaque case peut contenir une ou plusieurs fourmis (la fourmilière est en haut à gauche), ainsi que de la nourriture (placée dans les autres coins).

Quand une fourmi se déplace, elle passe directement d’une case à une case des cases voisines. La fourmi possède une orientation, c’est-à-dire qu’elle regarde une des 8 cases voisines. Une fourmi peut prendre une décision de mouvement en fonction de son environnement.

Des fourmis stupides : Modèle de base

Dans un premier temps, nous étudions des fourmis très stupides : La fourmi possède un cerveau qui est soit en mode recherche, soit en mode retour à la fourmilière.

En mode recherche :

En mode retour à la fourmilière :

Les algorithmes appliqués sont extrêmement simples. Le but du demi-tour dans la fourmilière consiste pour la fourmi à repartir dans la direction d’où elle vient, et donc à essayer de rejoindre l’amas de nourriture.

Dans le mode recherche, la fourmi choisi au hasard sa prochaine direction. Pour éviter des mouvements trop désordonnés, la nouvelle direction est choisie relativement à l’ancienne, c’est-à-dire sous forme d’une rotation. Les probabilités retenus auront une influence sur le comportement exploratoire des fourmis.

On se donne trois distributions de probabilité :

rotation 0 +/- 1 +/- 2 +/- 3 +/- 4
distribution 1 5/24 8/24 6/24 4/24 1/24
distribution 2 12/19 4/19 2/19 1/19 0
distribution 3 12/16 2/16 1/16 1/16 0

Directivité n°1 :

Directivité n°2 :

Directivité n°3 :

On constate que la distribution directive (n°3) est beaucoup plus efficace que les autres.

L’intelligence collective : Les phéromones

Les fourmis utilisent en effet des phéromones pour laisser des pistes que les autres fourmis vont suivre pour s’orienter.

En mode retour une fourmi peut déposer des gouttes de phéromones sur le sol :

Une fourmi qui porte de la nourriture fabrique donc une piste entre l’emplacement de la nourriture et la fourmilière.

Les fourmis en recherche ont donc intérêt à se diriger vers des cases qui contiennent beaucoup de phéromones :

On constate que l’algorithme est local : La fourmi étudie seulement les cases qui l’entourent. Une fourmi va naturellement suivre une piste qui l’éloigne de la fourmilière.

La communication entre fourmis est indirecte : Toute la communication est basée sur les phéromones, il n’y a pas de liaison entre les fourmis.

Une fourmi n’a pas de mémoire, en fait, le sol joue le rôle d’une mémoire globale et répartie pour l’ensemble de fourmis.

Pour éviter que les pistes persistent quand une source de nourriture est épuisée, on donne une durée de vie aux phéromones.

Rq. la recherche initiale étant très directive, c’est la nourriture dans le coin opposé qui est trouvé en premier, puis à partir de ce chemin de phéromones la source de nourriture la plus proche dans le coin en haut à droite, enfin, après évaporation des phéromones la dernière source de nourriture en bas à gauche est trouvée.

Conclusion

Résultats pour un terrain de 120x120 (en nombre de steps) :

# fourmis 100 200 500 1000
mouvements aléatoires 303k 156k 66k 37k
mouvements directifs (n°3) 43k 21k 9k 5k
avec phéromones 116k 79k 56k 45k
phéromones + mvt directifs 43k 34k 26k 23k

On constate qu’avec des fourmis avec un mouvement directif, la recherche de nourriture est très efficace. Essentiellement dû au nombre de fourmis qui parcourent la zone de façon plus méthodique qu’un déplacement complètement aléatoire.

Avec des pistes de phéromones, on remarque que le recrutement dirige bien les fourmis vers les sources de nourritures les plus abondantes (ici sur le bord droit). Mais par la suite, lorsque la source de nourriture est épuisée, on observe une latence (fausse piste) le temps de l’évaporation des phéromones.

Toutes la difficultée réside dans le bon réglage entre le nombre de fourmis, la taille du terrain et la vitesse d’évaporation des phéromones.

Cela montre qu’avec un concept très simple, celui de marques (les phéromones) laissées sur une mémoire collective (le sol), la colonie de fourmis remplace avantageusement une mémoire individuelle (retour vers la zone de nourriture) et une coordination centralisée (la reine).