Inspirés par l’intelligence sociale de la fourmi, des informaticiens tessinois ont trouvé le moyen d’aider les grands distributeurs à livrer leurs magasins. Explications.
Partager:
Depuis quelques années, ce sont des fourmis qui guident les camions de la Migros et du producteur de pâtes Barilla. Issue de l’Institut de recherche en intelligence artificielle Idsia, basé à Lugano, la start-up AntOptima commercialise des logiciels d’optimisation logistique inspirés par les colonies de fourmis.
Elle s’est attaquée à l’une des questions les plus inextricables des mathématiques: le problème du voyageur de commerce. Comment trouver la meilleure route qui passe par chaque ville exactement une fois? Cette question intéresse évidemment un grand distributeur qui doit livrer ses magasins le plus efficacement possible malgré l’imprédictibilité des bouchons et autres pannes…
«Il n’existe aucune stratégie pour être certain d’obtenir rapidement la bonne réponse lorsque le nombre de villes devient considérable, explique Gianni Di Caro, chercheur à l’Idsia. Il faudrait chercher parmi toutes les routes possibles, et le nombre de combinaisons devient vite bien trop grand: pour 20 villes, il dépasse le nombre de secondes écoulées depuis le big-bang. Pour l’Italie et ses 16’800 villes, un ordinateur rapide aura besoin de plus de deux mois pour déterminer la solution exacte! Mais des méthodes basées sur les fourmis trouvent rapidement des solutions approximatives suffisamment bonnes pour être utilisées en pratique.»
Dans la nature, une fourmi cherche plus ou moins au hasard, tout en étant attirée par les phéromones, ces marqueurs chimiques laissés sur le sol par ses congénères lorsqu’ils se déplacent. Une fois la nourriture trouvée, elle retrace son chemin pour revenir à la fourmilière. Un insecte ayant emprunté une route relativement courte sera plus vite de retour, et ce trajet sera doublement chargé de phéromones. Celles-ci y attirent d’autres fourmis, qui renforcent encore la concentration des marqueurs.
D’une manière collective, la colonie arrive ainsi à déterminer les chemins les plus courts entre la fourmilière et la nourriture. Comme les phéromones s’évaporent petit à petit, ce processus peut s’adapter à un environnement changeant (une source se tarit, une route devient impraticable, etc.).
La méthode d’optimisation de l’Idsia généralise ce processus sur l’ordinateur: des «fourmis» informatiques se déplacent sur une carte routière virtuelle pour déterminer à l’aide de «phéromones» les trajets les plus rapides.
L’algorithme bénéficie également d’informations sur la situation réelle: équipés de GPS, les camions transmettent leurs phéromones par radio à l’unité centrale qui réactualise deux fois par jour leur feuille de route – et tient même compte de la probabilité d’un bouchon, d’une panne ou d’un magasin exceptionnellement fermé.
Les chercheurs de l’Idsia ont également appliqué cette approche pour améliorer la gestion du trafic de données sur internet – car là aussi, il s’agit d’éviter les bouchons.
«Notre travail a intéressé des géants tels que Cisco, Nortel et HP, souligne Gianni Di Caro. Contrairement aux problèmes de logistique pouvant compter sur une unité centrale, il s’agirait ici d’une intelligence entièrement distribuée, car seuls les paquets de données contiendraient l’information. Mais cette approche n’est pas encore mûre pour le marché: il faudrait modifier la méthode d’échange de données sur internet (le processus TCP-IP) pour pouvoir y encoder l’information nécessaire à l’algorithme. Et cela, une seule entreprise ne peut pas le faire.»
«En exagérant un peu, on pourrait dire que, dans la vie, tout est une question d’optimisation, glisse le chercheur. Même la séquence de décisions que vous prenez lorsque vous cuisinez peut être traduite en un arbre à plusieurs branches. Le chemin le plus court entre les racines et une feuille correspondrait au meilleur plat réalisable avec certains ingrédients…» Pensez-y la prochaine fois qu’une colonne de fourmis fait irruption dans votre cuisine.