Entre dans la forêt
Pistes de fourmis
Copié sur la nature

Pistes de fourmis

Des insectes sans carte qui apprennent aux ordinateurs à trouver leur chemin

✦ Confirmé

Aucune fourmi ne connaît de carte. Pourtant, toute la colonie trouve le chemin le plus court vers la nourriture. Un jeune Italien a transformé cette astuce en programme informatique.

Qui : Jean-Louis Deneubourg, Marco Dorigo · Quand : 1989–1992 · Où : Bruxelles, Belgique et Milan, Italie

Découvre l'histoire illustréephotos, animations et expériences à faire soi-même

La nature et l'invention

Les fourmis marquent le chemin avec une odeur, une phéromone. Sur le chemin le plus court, les fourmis reviennent plus vite, donc l'odeur s'intensifie et en attire d'autres. Le chemin plus long s'évapore peu à peu.

Les algorithmes de colonies de fourmis, c'est-à-dire des programmes où des fourmis virtuelles cherchent de bons itinéraires pour des camions, des plannings de production et le trafic dans les réseaux informatiques.

Le récit

À la fin des années 1980, l'équipe belge de Jean-Louis Deneubourg a posé un problème à des fourmis d'Argentine : deux ponts menaient du nid à la nourriture, un court et un long. Au début, les fourmis empruntaient les deux chemins à parts égales.

Au bout de quelques minutes, presque toute la colonie avait choisi le pont le plus court. Personne ne dirigeait. Il a suffi que les fourmis sur le chemin le plus court reviennent plus vite et le marquent plus souvent.

Marco Dorigo, doctorant à l'École polytechnique de Milan, a jugé que c'était une recette toute prête pour des problèmes mathématiques difficiles. En 1992, dans sa thèse, il a décrit le premier algorithme de colonies de fourmis : des fourmis virtuelles parcourent une carte de villes, laissent une odeur numérique, et l'odeur s'évapore.

Aujourd'hui, les algorithmes de colonies de fourmis forment l'une des familles de méthodes d'optimisation. On les utilise pour planifier des tournées de livraison, répartir des tâches et étudier le routage dans les réseaux informatiques.

Comment ça marche

  1. Odeur: Chaque fourmi qui revient avec de la nourriture marque le chemin. Les fourmis suivantes préfèrent les pistes qui sentent plus fort.
  2. Renforcement: Le chemin court est parcouru plus vite, donc il reçoit plus d'odeur dans le même temps. Un bon itinéraire se renforce de lui-même.
  3. Évaporation: Dans le programme, l'odeur disparaît lentement. Ainsi, les fourmis virtuelles ne restent pas bloquées sur le premier itinéraire, choisi au hasard, et continuent d'en chercher un meilleur.

Vérifie par toi-même

  1. Deux chemins vers le sucre: En été, dépose une goutte de miel à deux distances d'une piste de fourmis, avec deux bâtonnets en guise de ponts : un court et un long. Au bout d'un quart d'heure, compte les fourmis sur chaque pont.
  2. Efface la piste: Passe le doigt en travers d'une piste de fourmis sur une dalle de trottoir. Regarde comment les fourmis se perdent à cet endroit et cherchent l'odeur.
  3. Des fourmis sur papier: Dessine cinq villes sur une feuille et cherche le chemin le plus court qui passe par toutes. Compte combien d'itinéraires sont possibles. Avec vingt villes, il y en a plus que de grains de sable sur une plage.

Ce que l'on sait avec certitude

Les expériences des ponts ont été décrites par Goss, Aron, Deneubourg et Pasteels en 1989. L'algorithme de colonies de fourmis a été proposé par Marco Dorigo en 1992 et, depuis, c'est une méthode largement utilisée pour résoudre de façon approchée des problèmes d'itinéraires. Il ne donne pas toujours le meilleur résultat, mais en général un bon, et rapidement.

Sources