Méthode de la colonie de fourmis

La méthode de la colonie de fourmis simule le comportement de ces insectes qui, lorsque l'on pose un obstacle sur leur trajet, trouvent toujours le chemin le plus court pour le contourner.

Leur technique repose sur la pose de marqueurs chimiques, les phéromones, déposés sur les trajets parcourus. Cela peut paraître surprenant au premier abord mais un chemin plus court reçoit plus de phéromones qu'un chemin plus long. Les fourmis suivantes ayant tendance à emprunter les chemins les plus marqués, une solution va progressivement se dessiner.

Dans l'animation ci-contre, une fois l'ensemble de villes choisi (le désigner puis cliquer sur "Charger"), l'ensemble des segments est initialisé par une quantité de phéromones représentée en nuances de rouge (vif pour une quantité très forte, clair pour une quantité faible).

Par la suite, à chaque essai, 50 fourmis sont lancées sur le parcours puis le tableau des "odeurs" est modifié en fonction des trajets parcourus. Vous constaterez que suivant les réglages, les trajets s'approcheront plus ou moins vite d'une solution.

A chaque instant, le plus court trajet trouvé est représenté en bleu.

Choisir un parcours dans la liste, le charger, modifier
éventuellement les réglages puis cliquer sur "Tester".

Pourquoi les trajets plus courts sont-ils plus marqués

Supposons qu'un obstacle soit posé entre A et B, que le détour par C soit deux fois plus court que celui par D et que le trajet de A à B en passant par C prend une minute.

Si une fourmi part chaque seconde de A vers B, la moitié passant par C et l'autre moitié par D, au bout d'une minute les 30 fourmis ayant choisi le parcours par C sont arrivées en B alors que seules 15 fourmis ayant emprunté le parcours par D sont arrivées. Une fourmi allant de B vers A trouvera donc deux fois plus de phéromones sur le trajet BCA que sur le trajet BDA.

Les paramètres à prendre en compte

Un premier paramètre est celui du marquage initial.

Sans aucun marquage ou avec un marquage homogène où tous les segments auraient la même quantité de phéromones, le temps nécessaire pour que les fourmis s'approchent de la solution serait extrêmement long.
Une meilleure solution consiste à prendre un marquage initial où la quantité de phéromones est inversement proportionnelle à la distance. On peut imaginer pour cela que, pendant un certain temps, sur chaque segment, une fourmi effectue des allers et retours entre les extrémités. Un trajet deux fois plus court sera parcouru deux fois plus souvent et recevra donc deux fois plus de phéromones.

Un deuxième paramètre consiste à fixer une règle que les fourmis appliqueront pour choisir parmi tous les segments disponibles à un moment donné.

Une première idée consiste à choisir un segment de manière proportionnelle à son "odeur", de cette manière un segment 2 fois plus marqué a deux fois plus de chances d'être choisi.
Une seconde solution, un peu plus efficace, consiste à choisir un segment proportionnellement au carré de son odeur (un segment 2 fois plus marqué aura 4 fois plus de chances d'être choisi).

Il existe un autre paramètre très important , l'atténuation. En effet, les phéromones sont des substances chimiques qui se dégradent (ou s'évaporent ? ) et les marqueurs vont petit à petit s'estomper. Pour tester l'applet, vous pouvez donc faire varier ce taux :

Si le taux est trop important, les segments marqués s'effacent trop rapidement et les longueurs des trajets des souris vont rapidement converger vers une même valeur assez éloignée de la solution.
Si le taux est trop faible, de nombreux segments restent marqués et les longueurs des trajets s'améliorent peu.

Après plusieurs essais, il semblerait qu'une valeur correcte est de l'ordre de 0.5%.

De plus, j'ai placé une case à cocher "optimiser" que vous pouvez activer. Avec l''optimisation, à chaque étape, les trajets obtenus sont analysés et améliorés par les techniques d'optimisation locale que je décris au sujet de la méthode 2-opt. C'est la seule entorse réelle au comportement des fourmis mais sans cette optimisation, le meilleur parcours est très rarement trouvé, même dans le cas où le nombre de villes est assez faible.

Programmes et algorithmes

Vous trouverez ci-joint, sous forme compressée, les sources et les programmes écrits en Delphi et en Java que j'ai réalisé pour tester et préparer cet article :

L'applet Java présentée ci-dessus

Le programme correspondant en Delphi

Les deux programmes sont écrits selon le même principe et sont paramétrables, ils sont accompagnés de plusieurs ensembles de villes, ce qui permet de les utiliser aussi bien avec le défi des 250 villes qu'avec d'autres circuits plus classiques.

En conclusion

Je n'ai étudié la méthode des colonies de fourmis que quelques heures mais je pense avoir été honnête dans ma démarche et en ai respecté le comportement. Si vous remarquez des erreurs importantes, veuillez s'il vous plait me le signaler afin que je puisse effectuer les corrections nécessaires.

Pour ma part, je trouve la technique très intéressante sur le plan du concept et elle permet de trouver un parcours raisonnable assez rapidement. Par contre, les réglages sont assez délicats et l'optimum est rarement trouvé.

Jean-Luc Juveneton : Ingénierie Educative - CRDP - Grenoble (38) / imel@ac-grenoble.fr / 12 avril 2005