Optimisation par colonies de fourmis : comment une piste de phéromone trouve un chemin court

Stigmergie, expérience du double pont, système de fourmis de Dorigo, rôle des paramètres α, β et ρ et variantes améliorées — sur un circuit passant par les chefs-lieux de région tchèques et sur 60 villes, en comparaison avec le recuit simulé.

13 minutes Matěj Žalmánek 2026-10-15

Série Bases de l’IA Partie 29 sur 52

1. Carte de l’intelligence artificielle : qu’est-ce qui est quoi et comment tout s’emboîte
2. Brève histoire de l’intelligence artificielle : de Turing aux modèles de langage
3. Données, modèle, entraînement, inférence : les notions de base sur un seul exemple
4. Lire la notation mathématique : symboles, indices, sommes et quantificateurs
5. Ensembles et relations : les briques dont sont faites les définitions en IA
6. Fonctions et applications : pourquoi tout modèle d’IA est une fonction
7. Logique et démonstrations : les règles selon lesquelles on raisonne en IA
8. Graphes et arbres : la structure sur laquelle reposent la recherche et les réseaux de neurones
9. Algèbre linéaire pour l’apprentissage automatique : vecteurs, matrices et pourquoi l’IA multiplie surtout
10. Dérivées, gradient et règle de dérivation en chaîne : comment un modèle sait dans quelle direction apprendre
11. Descente de gradient : comment un modèle apprend
12. Qu’est-ce que la probabilité : du lancer de dé aux axiomes de Kolmogorov
13. Probabilité conditionnelle et théorème de Bayes : comment réviser une estimation quand on apprend du nouveau
14. Variable aléatoire et fonction de répartition : une seule fonction qui dit tout de la loi
15. Fonction de densité et fonction de masse : pourquoi une variable continue a une probabilité nulle en chaque point
16. Espérance, variance et covariance : où se situe une loi, quelle est sa largeur et ce qui varie avec quoi
17. Panorama des lois de probabilité : Bernoulli, binomiale, Poisson, uniforme, normale et exponentielle
18. Loi des grands nombres et théorème central limite : pourquoi les moyennes sont si prévisibles
19. Statistique et estimation de paramètres : maximum de vraisemblance, MAP et intervalles de confiance
20. Théorie de l’information : entropie, entropie croisée et divergence KL — d’où viennent les fonctions de perte
21. Recherche dans l’espace d’états : BFS, DFS, UCS et A* en animations
22. Jeux et adversaires : minimax, élagage alpha-bêta et Monte Carlo tree search
23. Satisfaction de contraintes : backtracking, propagation de contraintes et AC-3 sur un sudoku et une carte des régions tchèques
24. Logique et systèmes à base de connaissances : chaînage avant et arrière, résolution et systèmes experts
25. Planification : STRIPS, monde des blocs, heuristiques par relaxation et planification dans les agents IA
26. Recherche locale et recuit simulé : un voyageur de commerce à travers les chefs-lieux de région tchèques
27. Algorithmes génétiques : population, croisement, mutation et sélection sur un sac à dos de randonnée
28. Stratégies d’évolution et programmation génétique : de la règle du cinquième à la loi de Kepler
29. Optimisation par colonies de fourmis : comment une piste de phéromone trouve un chemin court
30. Optimisation par essaim de particules : inertie, expérience propre et expérience de l’essaim
31. Neuroévolution : faire évoluer les poids et la forme des réseaux de neurones, et l’algorithme NEAT
32. Ensembles flous et fonctions d’appartenance : comment écrire « un peu chaud »
33. Logique floue et probabilité : pourquoi « un peu chaud » ne veut pas dire « probablement chaud »
34. Logique floue : t-normes, implications et règles SI–ALORS
35. Commande floue : Mamdani et Sugeno, du ventilateur au pendule inversé sur un chariot
36. Clustering flou : l’algorithme fuzzy c-means et les points entre les clusters
37. Systèmes neuro-flous (ANFIS) : des règles floues qui apprennent à partir des données
38. Chaînes de Markov : matrice de transition, distribution stationnaire et PageRank
39. Modèles de Markov cachés : l’algorithme de Viterbi et le casino malhonnête
40. Réseaux bayésiens : pourquoi l’herbe est mouillée et ce que cela implique pour l’arroseur
41. Le filtre de Kalman : comment estimer, à partir de mesures imprécises, où se trouve une voiture et à quelle vitesse elle roule
42. Types d’apprentissage automatique : supervisé, non supervisé, semi-supervisé et plus
43. Prompts, contexte et RAG : comment donner au modèle les bonnes informations
44. Autoencodeurs variationnels (VAE) : de nouvelles images à partir d’un espace latent continu
45. Réseaux antagonistes génératifs (GAN) : le faussaire contre le détective
46. Modèles de diffusion : comment une image naît du bruit pur
47. Processus de décision markoviens : états, actions, récompenses et équations de Bellman
48. Q-learning et DQN : apprendre la valeur des actions, du tableau au réseau de neurones
49. Policy gradient et PPO : apprendre directement la politique
50. Comment fonctionne un agent IA : un modèle de langage en boucle avec des outils
51. Programmer avec des agents IA : consigne, tests et vérification
52. Évaluation et sécurité des systèmes d’IA : comment mesurer et comment surveiller

Programme complet de la série 52 sur 83 sujets publiés

Une fourmi seule n’a pas de carte, ne sait pas compter et voit à peine quelques centimètres devant elle. La colonie trouve pourtant de manière fiable le chemin le plus court de la fourmilière à la nourriture. Aucune fourmi ne le connaît — il naît de la façon dont toutes ensemble marquent le terrain. Au début des années quatre-vingt-dix, Marco Dorigo, de l’École polytechnique de Milan, a remarqué que la même astuce pouvait s’appliquer au problème du voyageur de commerce. Ainsi est née l’optimisation par colonies de fourmis et, avec elle, tout le domaine de l’intelligence en essaim.

Cet article fait suite à Recherche locale et recuit simulé. Nous résolvons la même tâche — un circuit passant par les chefs-lieux de région, avec un optimum de 1 060,4 km —, ce qui permettra de voir comment les fourmis s’en sortent face au recuit.

1. Communiquer par la trace

Définition — stigmergie

La stigmergie est une communication indirecte par l’environnement : un individu modifie l’environnement, et cette modification influence ce que feront plus tard les autres (ou lui-même). Le terme a été introduit par Pierre-Paul Grassé en 1959 lors de l’étude de la construction des termitières.

2. L’expérience du double pont

En 1989, Goss, Deneubourg et leurs collègues ont construit pour des fourmis d’Argentine deux ponts entre la fourmilière et la nourriture — l’un deux fois plus long que l’autre. Au bout d’un moment, la majeure partie de la colonie passait par le plus court. Pourquoi ? Une fourmi qui a choisi la branche courte arrive plus tôt à la nourriture et, quand elle revient, la branche courte est déjà marquée du côté de la nourriture. Le chemin court se marque plus vite et commence à gagner.

Définition — modèle du choix de branche (Deneubourg et al.)

Si les branches courte et longue portent au départ les quantités de phéromone A et B, une fourmi choisit la branche courte avec la probabilité

P = (k + A)^h / ((k + A)^h + (k + B)^h),

où k détermine la force avec laquelle une fourmi réagit à une piste faible et h > 1 amplifie les différences. La fourmi dépose de la phéromone au début de la branche choisie et à sa fin lorsqu’elle arrive.

P = (k + A)^h / ((k + A)^h + (k + B)^h)

P

la probabilité que la fourmi suivante prenne la branche courte — la fourmi ne décide pas à coup sûr, seulement avec un poids ; la branche longue reçoit le reste 1 − P

A

la phéromone sur la branche courte — la seule chose que la fourmi « sait » du chemin ; plus il y en a, plus la branche courte attire

B

la phéromone sur la branche longue — au dénominateur, elle rivalise avec la courte, si bien que c’est le rapport des pistes qui décide, pas leur quantité absolue

k

un « seuil d’attention » — ajouté à égalité aux deux branches, de sorte que les premières molécules de phéromone ne changent presque pas le rapport ; sans lui, la toute première fourmi déciderait pour la colonie entière

h

l’amplificateur — une puissance supérieure à 1 exagère la différence ; c’est elle qui transforme un petit avantage dû au hasard en rétroaction positive

Exemple — comment décident k = 30 et h = 2

La branche courte porte A = 20 unités de phéromone, la longue B = 10 :

P = (30 + 20)² / ((30 + 20)² + (30 + 10)²) = 2 500 / (2 500 + 1 600) = 2 500 / 4 100 ≈ 0,610.

• Pistes égales (A = B, par exemple toutes deux nulles) : P = 0,500 — pur hasard.
• Cinq unités contre zéro : P = 35² / (35² + 30²) ≈ 0,576 — une petite piste ne décide presque rien, c’est le travail de k.
• A = 60, B = 10 : P = 8 100 / (8 100 + 1 600) ≈ 0,835 — déjà une nette supériorité.
• Sans amplification (h = 1), avec A = 20, B = 10, on n’obtiendrait que 50 / 90 ≈ 0,556 au lieu de 0,610.

Une simulation du modèle (k = 30, h = 2, dix fourmis par pas, branche courte de 5 pas, longue de 10) montre la part de phéromone sur la branche courte pour huit colonies :

Sept colonies se sont stabilisées sur la branche courte, une sur la longue : les toutes premières fourmis ont choisi par hasard la branche longue, et la rétroaction positive l’a « verrouillée ». Sur cent colonies, 85 ont fini sur la branche courte et 9 sur la longue. Lorsque les deux branches ont la même longueur, les colonies se répartissent à peu près moitié-moitié (46 et 42) — c’est le hasard qui brise la symétrie. La longueur du chemin oriente donc le résultat, mais ne le garantit pas. Nous verrons la même faiblesse dans l’algorithme.

3. Le système de fourmis

Le système de fourmis de Dorigo (Ant System, 1992) envoie des fourmis virtuelles sur un graphe de villes. Chacune construit un circuit complet et, selon sa brièveté, dépose de la phéromone sur ses arêtes.

Définition — circuit et longueur

On se donne n villes et des distances d_ij = d_ji > 0. Un circuit est un ordre des villes π = (π₁, …, π_n) dans lequel chaque ville figure exactement une fois ; sa longueur est

L(π) = d_π1π2 + d_π2π3 + … + d_πnπ1

— le dernier terme ramène le voyageur chez lui. Une arête (i, j) appartient au circuit si i et j s’y suivent directement. Le problème du voyageur de commerce cherche un circuit de longueur minimale.

Définition — règle de transition

Une fourmi dans la ville i va vers une ville j pas encore visitée avec la probabilité

p_ij = τ_ij^α · η_ij^β / ∑_l τ_il^α · η_il^β,

où τ_ij est la phéromone sur l’arête, η_ij = 1 / d_ij la visibilité (les villes proches sont plus attirantes), et la somme porte sur toutes les villes non visitées l. Les paramètres α et β pondèrent la piste face à la distance.

p_ij = τ_ij^α · η_ij^β / ∑_{l ∈ Ni} τ_il^α · η_il^β

p_ij

la probabilité d’un pas de i vers j — on tire au sort au lieu de prendre le meilleur, pour que la colonie continue d’essayer aussi d’autres circuits

τ_ij^α

la mémoire de la colonie — la phéromone porte l’expérience des fourmis précédentes ; l’exposant α dit à quel point s’y fier (α = 0 la désactive complètement)

η_ij^β

l’avidité — η = 1 / d favorise les villes proches ; c’est un conseil gratuit dès la première itération, quand la phéromone ne sait encore rien

∑ … sur N_i

la somme des poids de toutes les villes pas encore visitées — la division transforme les poids en probabilités de somme 1 ; les villes visitées n’y figurent pas, donc la fourmi n’y revient pas

Exemple — une décision de fourmi

Une fourmi se trouve dans la ville i et il lui reste trois villes : à 50, 100 et 150 km, avec une phéromone τ = 1, 3 et 2. La constante de la visibilité se simplifie dans la fraction ; calculons donc avec η = 100 / d, soit 2, 1 et 2/3. Avec α = 1 et β = 3 :

• poids : 1 · 2³ = 8,000, 3 · 1³ = 3,000, 2 · (2/3)³ ≈ 0,593 ;
• leur somme 11,593 ;
• probabilités 0,690, 0,259 et 0,051.

La ville la plus proche l’emporte, bien qu’elle ait le moins de phéromone. Avec β = 1, on obtiendrait 0,316, 0,474 et 0,211 — la phéromone mène. Et avec β = 0, seule la piste décide : 0,167, 0,500 et 0,333 (proportions 1 : 3 : 2).

Définition — mise à jour de la phéromone

Après chaque itération, la phéromone s’évapore partout, et chaque fourmi m ajoute sur les arêtes de son circuit de longueur L_m une quantité proportionnelle à 1 / L_m :

τ_ij ← (1 − ρ) · τ_ij + ∑_{m : (i, j) ∈ circuit m} Q / L_m,

où ρ ∈ (0, 1) est le taux d’évaporation.

τ_ij ← (1 − ρ) · τ_ij + ∑_{m : (i, j) ∈ circuit m} Q / L_m

τ_ij à gauche

la nouvelle phéromone sur l’arête — ce sur quoi se décideront les fourmis de l’itération suivante

(1 − ρ)

l’évaporation — chaque itération retire à chaque piste la même fraction ρ ; l’expérience ancienne s’estompe ainsi géométriquement et la colonie peut réapprendre

τ_ij à droite

la phéromone existante — la mémoire est seulement corrigée, on ne repart pas de zéro

∑_m

une somme sur les fourmis qui ont emprunté l’arête — chaque fourmi n’ajoute que sur les arêtes de son propre circuit ; une arête utilisée par davantage de fourmis reçoit davantage — c’est ici que se dépouille le « vote » de la colonie

Q / L_m

une récompense inversement proportionnelle à la longueur du circuit — circuit plus court = piste plus forte ; la constante Q ne fixe que l’échelle

Exemple — une mise à jour

Une arête a τ = 1, ρ = 0,3, Q = 1 000, et deux fourmis l’ont empruntée avec des circuits de 1 100 et 1 300 km :

τ ← 0,7 · 1 + 1 000 / 1 100 + 1 000 / 1 300 ≈ 0,700 + 0,909 + 0,769 = 2,378.

Une arête que personne n’a empruntée n’a plus que 0,7 après la même itération. La fourmi au circuit le plus court a ajouté davantage (0,909 contre 0,769).

import random

def postav_okruh(start, n, tau, d, alfa=1, beta=3):
    okruh, volna = [start], set(range(n)) - {start}
    while volna:
        i = okruh[-1]
        kandidati = list(volna)
        vahy = [tau[i][j] ** alfa * (1 / d[i][j]) ** beta for j in kandidati]
        j = random.choices(kandidati, weights=vahy)[0]
        okruh.append(j)
        volna.remove(j)
    return okruh

def aktualizuj(tau, okruhy, delka, rho=0.3, Q=1.0):
    for radek in tau:
        for j in range(len(radek)):
            radek[j] *= 1 - rho                 # évaporation
    for okruh in okruhy:
        L = delka(okruh)
        for a, b in zip(okruh, okruh[1:] + okruh[:1]):
            tau[a][b] += Q / L                  # circuit plus court, piste plus forte
            tau[b][a] += Q / L

Le système de fourmis complet ne fait ensuite qu’alterner construction des circuits et mise à jour, et retient le meilleur circuit jamais construit par quiconque :

def mravenci_system(n, d, mravencu, iteraci, tau0):
    tau = [[tau0] * n for _ in range(n)]      # partout pareil au départ
    nejlepsi = None
    for it in range(iteraci):
        okruhy = [postav_okruh(m % n, n, tau, d) for m in range(mravencu)]
        aktualizuj(tau, okruhy, delka)        # évaporation + nouvelle piste
        kandidat = min(okruhy, key=delka)
        if nejlepsi is None or delka(kandidat) < delka(nejlepsi):
            nejlepsi = kandidat
    return nejlepsi

4. Les fourmis sur les chefs-lieux de région

Lâchons 13 fourmis (une depuis chaque ville) pendant 100 itérations avec α = 1, β = 3 et ρ = 0,3. La carte montre la phéromone sur les arêtes après la 1^re, la 5^e, la 20^e et la 100^e itération — plus le trait est épais, plus il y a de phéromone :

À la première itération, la piste est répartie presque partout et le meilleur circuit mesure 1 292,6 km. Dès la cinquième itération, l’une des fourmis trouve l’optimum de 1 060,4 km. La phéromone se concentre ensuite sur les arêtes des bons circuits — les traits faibles disparaissent, les forts restent — et la fourmi moyenne construit un circuit d’environ 1 250 km. La colonie ne converge pas complètement, elle continue d’essayer un peu.

Trace de l’exécution par itération — le meilleur circuit trouvé jusque-là et le circuit moyen des treize fourmis dans l’itération donnée :

Le meilleur circuit s’améliore par sauts (la troisième itération n’a rien apporté de nouveau, la quatrième a retranché 111 km), tandis que la moyenne baisse plus lentement et de façon irrégulière : les fourmis tirent au sort, si bien que même lors d’une bonne itération certaines construisent de mauvais circuits. L’écart entre la moyenne et le meilleur est précisément l’exploration qui empêche la colonie de se figer complètement.

Cela ne se passe pas toujours aussi bien. Sur vingt exécutions avec des graines différentes, seules 7 ont trouvé l’optimum ; la moyenne était de 1 073,9 km et le pire résultat de 1 083,0 km. Le recuit, avec 98 sur 100 sur la même tâche, était plus fiable. Pour situer : le « plus proche voisin » glouton, qui va toujours vers la ville non visitée la plus proche, donne de 1 120 à 1 336 km selon le départ. Les fourmis sont nettement meilleures, mais le système de fourmis de base n’est pas à lui seul un champion — c’est pourquoi ses variantes améliorées ont vu le jour.

5. À quoi servent α, β et ρ

Sur treize villes, on peut résoudre beaucoup de choses même sans phéromone. Seule une tâche plus grande montre la différence — les mêmes 60 villes aléatoires que dans l’article sur le recuit, 30 fourmis, 150 itérations, moyenne de trois exécutions :

• Sans phéromone (α = 0), les fourmis ne sont que des voyageurs gloutons aléatoires et n’apprennent rien — des circuits plus longs d’un tiers.
• Sans distances (β = 0), la colonie n’a aucun point d’appui : les premiers circuits sont complètement aléatoires et la phéromone qu’ils laissent mène à d’autres circuits aléatoires.
• Une évaporation lente conserve trop longtemps les pistes des premiers circuits, mauvais, et la colonie apprend lentement. Une évaporation rapide, à l’inverse, oublie aussi ce qui est bon.

Combien de temps la colonie se souvient, cela se calcule exactement. Il suffit de suivre une seule arête.

Théorème — phéromone stationnaire et demi-vie de l’évaporation

Si une arête reçoit à chaque itération le même apport Δ ≥ 0, c’est-à-dire τ_t+1 = (1 − ρ) τ_t + Δ, alors

τ_t = Δ/ρ + (1 − ρ)^t (τ₀ − Δ/ρ) → Δ/ρ quand t → ∞.

Sans apport (Δ = 0), la piste tombe à la moitié en t_½ = ln 2 / (−ln(1 − ρ)) itérations.

Démonstration. En soustrayant Δ/ρ des deux membres de la récurrence, on obtient τ_t+1 − Δ/ρ = (1 − ρ)(τ_t − Δ/ρ), car (1 − ρ)Δ/ρ + Δ = Δ/ρ. L’écart à Δ/ρ est donc multiplié à chaque itération par le nombre 1 − ρ ∈ (0, 1) et décroît géométriquement vers zéro. La demi-vie est la solution de (1 − ρ)^t = ½. ∎

τ^* = Δ / ρ

τ^*

le niveau auquel se stabilise la phéromone de l’arête — apport et évaporation s’équilibrent

Δ

ce que l’arête reçoit par itération — les arêtes des circuits fréquents et courts ont un Δ grand, et donc aussi un niveau élevé

ρ

au dénominateur : une évaporation lente laisse les pistes monter haut, et les différences entre arêtes mettent longtemps à s’aplanir ; une évaporation rapide les maintient basses et dépendantes des seules dernières itérations

Une arête avec τ₀ = 1 et ρ = 0,3 : l’une reçoit Δ = 1 à chaque itération, l’autre n’est utilisée par personne.

L’arête utilisée s’approche de 1/0,3 ≈ 3,33 ; celle qui ne l’est pas tombe en dix itérations sous trois centièmes. La demi-vie de l’évaporation pour les lignes du tableau plus haut : avec ρ = 0,3, elle est de 1,94 itération, avec ρ = 0,02 de 34,31 itérations entières — les pistes des premiers circuits aléatoires règnent donc encore pendant des dizaines d’itérations —, et avec ρ = 0,9 de 0,30 itération seulement, si bien que la colonie ne se souvient pratiquement que du dernier tour.

Le meilleur réglage a donné de 2 194 à 2 314 km — comparable au recuit de l’article précédent, qui sur les mêmes villes a fini entre 2 210 et 2 270 km.

6. De meilleures fourmis

• La stratégie élitiste ajoute un supplément de phéromone sur le meilleur circuit trouvé jusque-là, pour qu’il ne se perde pas.
• MAX–MIN Ant System (Stützle et Hoos, 2000) ne laisse déposer de la phéromone qu’à la meilleure fourmi et maintient τ entre une borne inférieure et une borne supérieure. La borne inférieure garantit qu’aucune arête ne disparaît complètement, et la colonie ne se fige donc pas prématurément — comme celle qui, dans l’expérience du pont, a fini sur la branche longue.
• Ant Colony System (Dorigo et Gambardella, 1997) choisit avec une certaine probabilité directement la meilleure arête et retire de la phéromone dès la construction du circuit, pour que les autres fourmis essaient ailleurs.
• Recherche locale. En pratique, chaque circuit construit par une fourmi est encore peaufiné par des mouvements 2-opt de l’article sur le recuit. Les fourmis trouvent une bonne région, l’algorithme de la colline l’affine — dans les années quatre-vingt-dix, cette combinaison figurait parmi les meilleures méthodes pour le voyageur de commerce.

Définition — stratégie élitiste et MAX–MIN Ant System

La stratégie élitiste ajoute à la mise à jour habituelle encore e · Q / L^best sur chaque arête du meilleur circuit trouvé jusque-là, de longueur L^best ; e est le nombre de « fourmis élitistes ».

MAX–MIN Ant System ne dépose de la phéromone que selon le seul meilleur circuit et rogne le résultat à l’intervalle [τ_min, τ_max] :

τ_ij ← min(τ_max, max(τ_min, (1 − ρ) τ_ij + Δ_ij)), où Δ_ij = 1 / L^best pour les arêtes du meilleur circuit, 0 sinon.

Stützle et Hoos choisissent comme borne supérieure τ_max = 1 / (ρ L^best) — exactement la valeur stationnaire Δ/ρ du théorème ci-dessus pour une arête qui se trouve à chaque fois dans le meilleur circuit. La borne inférieure est une petite fraction de la supérieure ; de plus, la phéromone est initialisée à τ_max pour que les premières itérations explorent le plus largement possible.

Définition — règles d’Ant Colony System

Règle proportionnelle pseudo-aléatoire : une fourmi dans la ville i tire q dans [0, 1). Si q ≤ q₀, elle va directement vers la ville de plus grand poids, j = arg max_{l ∈ Ni} τ_il · η_il^β ; sinon, elle tire au sort selon la règle de transition du système de fourmis.

Mise à jour locale : juste après le passage par l’arête (i, j), τ_ij ← (1 − ξ) τ_ij + ξ τ₀, de sorte qu’une arête empruntée s’affaiblit un peu vers la valeur initiale τ₀.

Mise à jour globale après une itération, uniquement sur les arêtes du meilleur circuit : τ_ij ← (1 − ρ) τ_ij + ρ / L^best.

Dorigo et Gambardella (1997) utilisent dans l’article original q₀ = 0,9, β = 2 et ρ = ξ = 0,1 — neuf pas sur dix, la fourmi prend donc la meilleure arête, et ce n’est qu’au dixième qu’elle explore.

7. Où travaillent les fourmis

• Routage dans les réseaux. L’algorithme AntNet (Di Caro et Dorigo, 1998) envoie à travers le réseau de petits paquets-fourmis qui mesurent les délais et mettent à jour les tables de routage. Le réseau s’adapte ainsi en continu à la congestion.
• Tournées de véhicules et ordonnancement. Livraison de marchandises, collecte des déchets ou ordre des commandes en production — des tâches apparentées au voyageur de commerce, où les algorithmes de fourmis sont utilisés avec la recherche locale.
• Intelligence en essaim. Une colonie de fourmis est l’un des exemples de la manière dont un comportement intelligent de l’ensemble naît d’individus simples et de règles locales. Un autre, l’essaim de particules, est le sujet du prochain article.

8. Résumé

• Les fourmis communiquent par des traces dans l’environnement (stigmergie) : un chemin plus court se marque plus vite et la rétroaction positive le renforce.
• Dans le modèle du double pont, 85 colonies sur 100 se stabilisent sur la branche courte — mais le hasard peut aussi verrouiller la longue.
• Le système de fourmis choisit la ville suivante selon la phéromone τ^α et la distance η^β ; la phéromone s’évapore au taux ρ et les circuits courts en ajoutent davantage.
• Sur les chefs-lieux de région, il a trouvé l’optimum, mais seulement dans 7 exécutions sur 20 ; sur 60 villes, il a fait jeu égal avec le recuit. Sans phéromone comme sans distances, nettement moins bien.
• Les variantes utilisées en pratique (MAX–MIN, ACS) empêchent le figement prématuré et combinent les fourmis avec la recherche locale.

Envie de mettre la main à la pâte ? Demandez à un agent IA d’écrire une simulation du double pont et essayez ce qui se passe quand vous « fermez » la branche courte au milieu de l’expérience — la colonie parvient-elle à repasser sur la longue ?

Vous voyez les choses autrement ? Écrivez à support@coden-app.com.