Modélisation du problème

Prenons une fourmi : Elle se déplace sur le nid. Elle rencontre soudain un objet. Elle va le prendre avec d’autant plus de chance que l’objet est isolé. Elle continue son chemin et va déposer sa charge près d’autres objets avec une probabilité d’autant plus grande qu’il y a des objets du même type dans le voisinage.

Le problème est de déterminer la probabilité de prendre un objet ou de le déposer en fonction de l’environnement. Pour cela on dote notre fourmi d’une mémoire à cout terme (ça ne se rapproche pas vraiment de la réalité mais on MODÉLISE !) lui permettant de se rappeler des derniers objets rencontrés.

Du coup, le "taux d’isolement" d’un objet est calculable grâce à cette mémoire en divisant le nombre d’objets rencontré par la taille de la mémoire.

On peut maintenant calculer la probabilité à notre fourmi de prendre un objet :

Soit f le taux d’occupation de l’objet, la probabilité de s’emparer d’un objet est : p1 = (K1/(K1+f))² où K1 est une constante.

On voit que plus l’objet est isolé (f->0), plus la fourmi a de chance de s’en emparer (p1->1).

De la même façon la probabilité de déposer un objet est : p2 = (f/(K2+f))² avec K2 une constante.

On remarque que plus la concentration de l’objet est forte (f->1) plus la fourmi a de chance de déposer l’objet.

Ci dessous un représentation des lois de probabilités pour différentes valeurs de K1 et K2 :

Bien sûr d’autres lois peuvent être utilisés, à vous d’essayer ...

Notamment les lois de probabilités p1 = (1-x)³ et p2 = x³ donnent des résultats performants et rapides.

Archives

L’archive complète est disponible à : ants-0.2.4.tar.gz ;

Les anciennes versions sont aussi disponibles : ants-0.2.3.tar.gz, ants-0.2.1.tar.gz.

Ce quoi qu’on doit avoir ?

Vous vous retrouvez tout de suite devant un nid modélisé, chacune des lettres représente un objet (oeuf, larve ou cocon). Des dizaines de fourmis s’y déplacent et comme prévu c’est le désordre total !

Les fourmis entrent par le coin supérieur gauche du nid. Ca bouge de partout et nos fourmis semblent complètement folles.

Après quelques instants, des petits tas se forment.

Quelques minutes, les tas deviennent plus gros et les objets de même type se regroupent.

Encore quelques minutes et c’est gagné !

Améliorations possibles

En fait une fourmi peut utiliser son odorat pour se déplacer et donc n’a pas un mouvement complètement désordonné. Une amélioration serait donc de rechercher les objets les plus proche de la fourmi et de diriger celle-ci vers celui-ci.

D’autre part la fourmi doit pouvoir estimer ’l’isolement’ d’un objet qu’elle rencontre grâce à son odorat (concentration en odeur) ou grâce à une exploration tactile des environs et non par mémoire.