🐜 Colonie de Fourmis

Le Problème du Voyageur de Commerce (PVC) demande : étant donné N villes, quel est le circuit fermé le plus court qui visite chaque ville exactement une fois et revient au point de départ ? Il est NP-difficile, ce qui signifie qu'aucun algorithme exact en temps polynomial connu n'existe pour un grand N ; le nombre de circuits possibles croît comme (N−1)!/2. Pour 20 villes, cela représente plus de 60 000 milliards de circuits. L'ACO trouve généralement des solutions quasi optimales bien plus rapidement qu'une recherche exhaustive, ce qui le rend pratique pour des problèmes logistiques réels comportant des centaines ou des milliers de villes.

Un taux d'évaporation élevé (ρ proche de 1) signifie que la phéromone se dissipe rapidement, gardant toutes les arêtes presque également attractives et encourageant une large exploration mais ralentissant la convergence. Un taux faible (ρ proche de 0) laisse la phéromone s'accumuler sur de nombreuses itérations, renforçant les meilleurs chemins trouvés tôt mais risquant la stagnation. En pratique, des valeurs de 0,1 à 0,3 tendent à bien équilibrer exploration et exploitation pour des instances de PVC de taille moyenne.

α est l'exposant qui contrôle avec quelle force les fourmis favorisent les arêtes à forte phéromone ; β contrôle avec quelle force elles favorisent les arêtes courtes (coût faible). Avec β=5 et α=1 (valeurs typiques de l'article original de Dorigo), l'heuristique de distance domine au début lorsque la phéromone est uniforme, donnant des circuits initiaux raisonnables, tandis que la phéromone déplace progressivement l'équilibre. Fixer α trop haut fait reposer l'algorithme trop lourdement sur des dépôts de phéromone précoces, potentiellement médiocres.

Oui — l'ACO a été adapté à la coloration de graphes, à l'ordonnancement d'ateliers, à la prédiction de structure des protéines, et même à l'optimisation continue (ACOR). Dans le routage réseau, le routage basé sur les fourmis (ABR) envoie des « paquets éclaireurs » qui sondent les chemins et déposent une phéromone numérique, redirigeant dynamiquement le trafic autour des congestions. Cisco a mis en œuvre des variantes de cette idée dans des algorithmes de routage adaptatif pour les réseaux de télécommunications.

La stigmergie est une coordination indirecte par modification de l'environnement — les agents communiquent en modifiant l'environnement partagé plutôt que par signalisation directe. Les traces de phéromone des fourmis en sont l'exemple canonique : chaque fourmi répond aux traces laissées par les fourmis précédentes, et sa propre trace influence les fourmis futures, sans contrôleur central. La stigmergie est aussi observée dans la construction des termitières, la construction des nids de guêpes, et a inspiré des architectures d'informatique distribuée.

L'ACO peut souffrir de stagnation, où toutes les fourmis convergent vers un circuit sous-optimal et la diversité de phéromone s'effondre. Il nécessite aussi un réglage minutieux des paramètres (α, β, ρ, nombre de fourmis), et sa vitesse de convergence est généralement plus lente que celle d'algorithmes spécialisés pour des problèmes bien étudiés comme le PVC. Les systèmes ACO hybrides qui combinent la recherche par fourmis avec des heuristiques d'amélioration locale (mouvements 2-opt ou 3-opt) performent généralement bien mieux que l'ACO pur sur de grandes instances.

Une règle empirique courante consiste à utiliser une fourmi par ville. Davantage de fourmis augmentent la diversité des solutions et réduisent le risque de convergence prématurée, mais augmentent aussi le calcul par itération. Les recherches ont montré que pour le PVC, 10 à 50 fourmis donnent souvent de bons résultats sur des instances allant jusqu'à 200 villes, tandis que de très grandes instances peuvent bénéficier de centaines de fourmis avec un calcul parallèle. Le nombre idéal interagit avec ρ : une évaporation plus rapide peut compenser un nombre de fourmis plus faible en maintenant la diversité.