Le métro de Tokyo et les routes des États-Unis modélisés par un micro-organisme

Si, comme moi, vous avez l'insigne honneur d'habiter en banlieue parisienne, vous avez sans doute un jour été confronté à l’aberration du réseau des transports publiques. Entre Paris et la banlieue, le réseau est plutôt performant, mais lorsque l'on voyage de banlieue à banlieue, on se retrouve souvent à faire des trajets complètements loufoques. A la moindre panne, c'est à dire tous les trois jours, c'est une pagaille apocalyptique. Certes, nous ne pouvions pas, à l'époque où les premiers tronçons ont été construits, prévoir l'évolution des besoins ni réaliser de jolies simulations sur ordinateur. Mais peut-être aurions-nous pu demander de l'aide à la créature la plus improbable qui soit : une moisissure gluante et visqueuse, Physarum polycephalum. 

Physarum et le réseau du métro de Tokyo

Comment optimiser un réseau de transport et de distribution ? Que ce soit dans le domaine de l'énergie, des télécommunications ou encore celui des transports en commun, c'est une question que se posent quotidiennement les informaticiens et mathématiciens spécialisés en réseaux. Ils se creusent sans arrêt les méninges pour concevoir de nouveaux algorithmes capables de fournir des solutions adaptées. C'est que la question n'est pas simple : pour une situation donnée, quelle est la configuration la mieux adaptée ? Et si nous posions la question à un micro-organisme ? Voilà l'intrigante idée qu'ont eue, en 2010, des chercheurs japonais et britanniques.

Physarum polycephalum dans son habitat naturel

L'équipe anglo-nipponne a soumis le problème de l'optimisation du réseau de métro de Tokyo à Physarum polycephalum, un micro-organisme unicellulaire qui, c'est le moins que l'on puisse dire, ne brille pas par son intelligence. Quelle forme ce réseau doit-il avoir pour garantir une efficacité de distribution maximale pour un coût minimal ?  Le problème est loin d'être simple : il faut tenir compte des densités de population, de la géographie (reliefs, fleuves etc.) et de la localisation des principaux points névralgiques. Il faut que le réseau soit à la fois robuste et flexible, pour pouvoir proposer des itinéraires alternatifs en cas de défauts ponctuels : variations du trafic, pannes matérielles, suicides ou accidents. Dites-vous bien que des ordis tournent à plein temps pour recracher des solutions potables à ce genre de problèmes. Et pourtant, en l'espace d'une journée, Physarum a élaboré un réseau aussi performant que celui proposé par les ingénieurs japonais ! Les résultats ont été publiés en 2010, dans la revue Science.

Physarum polycephalum est en effet habitué à résoudre un problème similaire : pour chercher de la nourriture et l'acheminer là où il en a besoin, il s'organise en réseau de petits tubes gluants. Pour des raisons évidentes, il ne s'épuise pas à construire un réseau aléatoire, au contraire : fort de ses millions d'années d'expérience, il est passé maitre dans l’art d'optimiser son réseau de distribution alimentaire. De façon générale, le réseau de Physarum est très réactif et dynamique : les branches changent sans cesse de forme et de taille, pour s'adapter aux variations des stocks de nourriture, et le réseau entier peut se déplacer de plusieurs centimètres en l'espace d'une heure ! Des chercheurs avaient déjà exhibé ses talents dans une expérience où le champignon devait trouver le chemin le plus court pour relier deux points de nourriture dans un labyrinthe :

Physarum dans un labyrinthe. Crédits : T. Nakagaki, H. Yamada and A. T´oth

Concrètement, voici comment les chercheurs ont procédé pour reproduire, à l'échelle de Physarum, la problématique du réseau de Tokyo, qui relie la capitale aux 36 villes voisines : ils ont disposé 37 points de nourriture, correspondants aux 36 villes et Tokyo, dans une boite de Petri, en essayant de respecter tant bien que mal la géographie de la région. Puis, ils ont implanté Physarum au point correspondant à Tokyo (le point jaune sur les photographies ci-dessous) et observé comment la moisissure se développait. Celle-ci se plait d'ordinaire dans l'obscurité, aussi, pour simuler les contraintes géographiques, les chercheurs ont éclairé certains points que Physarum a soigneusement évités. Dans les premières heures de l'expérience, Physarum a exploré son environnement en tissant un réseau fin et dense de petites branches, appelées plasmodia, sur toute la surface de la boite. Ce faisant, il a repéré les 36 autres points de nourriture. Puis, pour ne pas perdre son énergie futilement, Physarum a réduit au minimum les branches du réseau qui n'étaient quasiment pas utilisées (elles ont toutefois été conservées, pour pouvoir être facilement réactivées en cas de défaillance localisées) tout en renforçant les "tronçons" les plus utiles. Le résultat est visible dans la série de photographies suivante :

L'évolution du réseau de Physarum dans une boite de Petri représentant la région de Tokyo.

Le lendemain, le réseau construit par Physarum ressemblait comme deux gouttes d'eau au vrai réseau de Tokyo et semblait montrer la même efficacité dans l'acheminement et la distribution de la nourriture :

L'algorithme Physarum et les problèmes d'optimisation

Comme on ne peut décemment pas créer de nouveaux réseaux en s'appuyant sur un résultat visuel dans une boite de Petri, si bon fût-il, et qu'on ne peut pas non plus s'amuser à mettre en place un réseau de rails ou de câbles pour ensuite retirer ceux qui ne servent à rien, les scientifiques ont essayé de reproduire la stratégie de Physarum dans un algorithme informatique (une suite d'instructions élémentaires) extrêmement simple. Leur modèle mathématique va se révéler incroyablement efficace : ils parviennent non seulement à reproduire le réseau, mais à l'améliorer ! Comme le micro-organisme, l'algorithme commence par quadriller l'espace de façon aléatoire, puis renforce ou affaiblit les branches selon leur degré d'utilité. Puis, l'algorithme choisit deux villes au hasard et calcule le flux de liquide (dans ce cas, la nourriture) à travers le tube qui les relie. Pour cela, il se base sur des équations très simples de la mécanique des fluides, qui relient les proportions d'un tube (sa longueur et son diamètre) à la pression aux extrémités du tube. Enfin, l'algorithme procède à des ajustements : si le flux est important, le diamètre du tube est augmenté, sinon, il est diminué. Si la nouvelle configuration augmente l'efficacité globale du réseau, les changements sont conservés, sinon l'opération est répétée avec deux nouvelles villes choisies au hasard. Le calcul, simple et rapide, permet une économie de ressources informatiques conséquente. Voici ce qu'on peut lire dans l'article de Paloma Bertrand consacré à ce sujet sur le site Universcience :

« Cet algorithme est simple et beau », constate Bertrand Maury du Laboratoire de mathématiques de l'université Paris-Sud, « et la démarche est originale. S'inspirer de ce que fait une petite bestiole qui obéit à des mécanismes élémentaires pour élaborer un modèle capable de résoudre en temps réel des problèmes complexes, c'est assez osé. Mais leurs résultats, si l'on en croit la publication de Science, semblent concluants. » 

Modéliser le réseau routier au Royaume-Uni et aux États-Unis avec L'algorithme Physarum

Après le réseau du métro Tokyoïte, Andy Adamatzky et Jeff Jones, deux informaticiens de l'Université de Bristol, ont utilisé l’algorithme Physarum pour modéliser le réseau autoroutier en Angleterre. Dans leur étude, seules les 10 plus grandes villes du Royaume-Uni sont considérées. La moisissure virtuelle entame sa marche victorieuse à Londres bien évidemment. L'analyse des résultats montre que Physarum se débrouille plutôt bien encore une fois : le réseau obtenu ressemble au véritable réseau de routes, à la différence notable de l'autoroute reliant l'Angleterre à l'Ecosse. En introduisant des perturbations, les chercheurs observent comment le réseau pourrait être reconfiguré en cas de catastrophe naturelle ou d'accident majeur.

L'algorithme Physarum recréant le réseau routier anglais. Crédits : Andrew Adamatzky, Jeff Jones

Les deux chercheurs se sont aussi amusés à modéliser le réseau des autoroutes aux États-Unis, en utilisant la méthode de l'expérience nipponne. La moisissure commence cette fois son périple à New-York avant de coloniser le territoire entier, en reliant les points de nourriture. Le résultat est assez sympathique :

Les aventures de Physarum aux U.S.A. Crédits  : Andy Adamatzky et Jeff Jones

Puis, ils ont utilisé l'algorithme Physarum pour modéliser diverses situations. Dans la vidéo ci-dessous, on peut voir comment Physarum, larguée à New-York, envahit progressivement le territoire des États-Unis, où chaque grande ville est un centre d'approvisionnement. Le micro-organisme relie une à une les grandes villes et finit par établir un réseau stable et robuste, qui laisse cependant une immense parcelle complètement à l'abandon. 

Dans cette autre vidéo, un peu plus réaliste, on part d'une situation différente. Cette fois, Physarum est réparti de façon uniforme sur le territoire et doit s'adapter aux sources de nourriture, distribuées de façon irrégulière : abondantes dans les villes, elles sont au contraire très limitées dans les "campagnes". Au cours de la simulation, Physarum consomme rapidement les ressources rurales et le réseau se simplifie en se concentrant sur les grandes villes. Ces deux simulations ne reflètent pas tout à fait la réalité du réseau routier nord-américain, mais les résultats pourraient être exploités pour créer de futurs réseaux.

Aujourd'hui, Physarum polycephalum est utilisé dans l'analyse de réseaux de transports dans de nombreux pays. Les résultats sont également transposés dans des domaines où se posent des problèmes d'optimisation des réseaux de flux.

Références :

Tero et al. 2010. Rules for Biologically Inspired Adaptive Network Design. Science 10.1126/science.1177894
Les mathématiques du vivant, Ian Stewart, Éditions Flammarion
Path finding by tube morphogenesis in an amoeboid organism
A Mathematical Study of Physarum polycephalum
A New Physarum Learner for Network Structure Learning from Biomedical Data
Flow-network adaptation in Physarum amoebae
Road planning with slime mould: If Physarum built motorways it would route M6/M74 through Newcastle
Rebuilding Iberian motorways with slime mould