Calculer sans neurone

Piste bleue Le 25 juin 2017  - Ecrit par  Goaoc Xavier Voir les commentaires (1)

Le physarum polycephalum est un champignon gélatineux de nos sous-bois humides. Cet organisme unicellulaire, dont la taille peut atteindre celle de la paume d’une main, étonne de nombreux scientifiques par sa capacité d’apprentissage [1].

Nous allons voir ici comment son aptitude à trouver son chemin dans un labyrinthe, mise en évidence en biologie, modélisée via la physique et analysée par les mathématiques, ouvre de nouvelles perspectives en informatique.

Si le texte principal de l’article est en piste bleue, les blocs déroulants sont plutôt en piste rouge.

L’expérience

Cette histoire commence par l’expérience d’une équipe nippo-hongroise de biologistes confrontant notre champignon à des labyrinthes [2].

Il ne s’agit pas de le déposer au milieu d’un labyrinthe et de chronométrer le temps qu’il met à en sortir. L’expérience, plus radicale, consiste à découper le physarum en morceaux (d’environ 1cm x 1cm) et d’en tapisser le sol du labyrinthe. La physiologie du physarum lui permet de « recoller les morceaux » quand ils sont proches, et d’adopter ainsi la forme du labyrinthe. On badigeonne ensuite les murs de vinaigre (qu’il déteste) pour éviter qu’il ne les escalade, puis on présente des flocons d’avoine (dont il raffole) à deux entrées du labyrinthe. Le physarum grandit pour couvrir l’avoine, puis commence à réorganiser le « système de distribution » interne qui irrigue les différentes parties de sa cellule. Après quelques heures, on constate que ce système de distribution se réduit à un simple chemin, sans embranchement, qui relie les deux réserves d’avoine. Plusieurs vidéos permettent de visualiser le déroulement d’une telle expérience (par exemple ici en 20 secondes ou là en 2 minutes).

JPEG - 68.4 ko

En répétant cette expérience avec une dizaine de labyrinthes différents, on remarque que le physarum trouve à chaque fois le plus court chemin global joignant les deux entrées du labyrinthe. Ce travail a valu aux professeurs Nakagaki, Yamada et Tóth le prix Ig-Nobel 2008 de sciences cognitives. [3]

Plus courts chemins et graphes

Qu’entend-on par « plus court chemin » ? L’idée sous-jacente est que l’on peut modéliser le labyrinthe par un graphe ayant un sommet à chaque angle ou croisement, et une arête entre chaque paire de sommets voisins dans le labyrinthe.

Graphes

Un graphe peut se comprendre comme un ensemble de points, ou sommets, dont certains sont joints entre eux par des chemins, ou arêtes. Formellement, un graphe décrit juste l’ensemble de sommets et l’ensemble d’arêtes, sans préciser la manière dont il est dessiné (position des points, tracé des arêtes). Dans notre cas, ce point de vue géométrique fait l’affaire car le dessin du graphe du labyrinthe est donné naturellement par sa définition. L’étude des graphes est l’objet de la théorie des graphes. Voir aussi ici ou sur IdM.

Dans cette modélisation, on peut associer à chaque arête une longueur, c’est à dire la distance entre ses deux sommets. Déterminer le plus court chemin entre deux sommets revient à trouver la séquence d’arêtes qui mène d’un sommet à l’autre tout en minimisant la somme des longueurs des arêtes empruntées.

La recherche de plus court chemin dans les graphes est un problème classique en informatique, qu’il faut résoudre quotidiennement par exemple dans les systèmes de navigation par GPS. Les algorithmes connus pour résoudre ce problème (par exemple ici ou ) sont relativement simples, mais semblent néanmoins hors de portée d’un organisme unicellulaire.

Le physarum est-il effectivement capable de trouver son chemin dans n’importe quel labyrinthe ? On ne peut a priori exclure que les labyrinthes testés par les biologistes ne soient trop simples ou particuliers. Cependant, si cette capacité est avérée, ce champignon exploite sans doute une idée qui a échappé à des générations d’algorithmiciens...

Réseaux de flots

Le physarum gère sa nourriture via un système de canaux internes, qu’il construit et adapte. On peut comprendre sa structure comme un réseau de tuyaux qui relient ses diverses sources de nourriture. Il peut adapter le « diamètre » d’un tuyau à la quantité de nourriture qui doit y transiter. C’est cette faculté à « adapter des diamètres » que l’on interprète comme une capacité de calcul.

On peut modéliser ce réseau comme un graphe ayant un sommet à chaque jonction entre tuyaux, et une arête entre chaque paire de sommets entre lesquels il y a un tuyau. On peut envisager qu’une fois que le physarum épouse la forme du labyrinthe, le graphe de son réseau interne coïncide avec celui du labyrinthe. Cette modélisation associe aussi à chaque arête une capacité, c’est à dire le diamètre du tuyau entre ces deux sommets. (En première approximation, on considère que le diamètre est constant entre deux sommets.) L’ajout de ces capacités transforme le graphe en réseau de flot.

Réseau de flot

Formellement, un réseau de flot est un graphe dont chaque arête est munie d’une capacité (un réel positif) et dont certains sommets sont distingués comme sources ou puits. Un flot dans un réseau de flot est la donnée pour chaque arête d’une orientation et d’une quantité, aussi appelée flot, qui satisfait deux conditions :

  1. le flot de chaque arête est inférieur à sa capacité, et
  2. en chaque sommet autre que source ou puits, la somme des flots entrants égale la somme des flots sortants.

En théorie des réseaux de flot, il est classique de considérer un réseau avec des capacités et deux sommets distingués, une source et un puits, en se posant deux questions. D’une part, quel débit ce réseau permet-il de la source vers le puits ? D’autre part, comment se répartit le flot à l’équilibre ?

Tout cela n’est pas sans rappeler la loi de Kirchoff et la théorie des réseaux électriques. Un des jolis résultats en théorie des réseaux de flot (aussi appelés réseaux de transport) est le théorème flot maximal-coupe minimale, cas particulier de la dualité en programmation linéaire. Cet article d’IdM vous en dira plus sur les coupes minimales dans les graphes.

Lors de chaque expérience, on constate que le physarum fait évoluer son réseau de flot vers un réseau très particulier : la capacité est maximale (disons 1) pour les arêtes du plus court chemin entre les deux sommets correspondant aux entrées proches des tas de flocons d’avoine, et minimale (disons 0) ailleurs. Le physarum semble donc disposer d’une dynamique qui « calcule » le plus court chemin.

Modélisation et simulation de la dynamique

Une équipe de mathématiciens appliqués [4] a proposé de modéliser cette dynamique en associant l’évolution du diamètre des tuyaux à la répartition du flot : les tuyaux s’adaptent au flot, et vice-versa. Mathématiquement, il s’agit de coupler la quantité de flot qui s’accumule en chaque sommet et les capacités des arêtes qui y sont reliées. On fait cela au moyen d’un système d’équations différentielles.

Loi de variation des diamètres.

Numérotons les arêtes du graphe $e_1$, $e_2, \ldots, e_n$. Notons, respectivement, $D_i(t)$ et $F_i(t)$ le diamètre de l’arête $e_i$ et l’intensité du flot qui la parcourt à l’instant $t$. Chaque arête est orientée arbitrairement et le signe de $F_i$ indique si le flot descend ou remonte $e_i$. La loi d’évolution que l’on cherche est de la forme

\[\frac{d}{dt}D_i(t) = f(|F_i(t)|) - D_i(t)\]

où $f$ est une fonction continue croissante telle que $f(0)=0$. Cette équation traduit l’idée que le diamètre tend à s’ajuster à l’intensité du flot ; la valeur absolue indique que le sens d’écoulement du flot n’a pas d’influence sur l’évolution du diamètre.

L’identité est un exemple simple de fonction $f$ satisfaisant ces conditions. Même dans ce cas, le système d’équations ne se résout pas simplement puisque les $F_i(t)$ dépendent non-linéairement des $D_i(t)$. Il est possible d’associer à chaque sommet un potentiel de sorte que chaque intensité $F_i$ dépende linéairement de la différence entre les potentiels des sommets de $e_i$... Bref, on met à profit la théorie des réseaux électriques !

Une fois ce modèle posé, on peut le simuler informatiquement via des techniques d’analyse numérique. S’affranchir de la construction des labyrinthes (sans parler de la découpe des physarum !) permet d’examiner des graphes de bien plus grande taille, voire des graphes qui ne sont pas réalisables dans le plan (car impliquant des croisements). Simulation faite, on constate que ce système converge infailliblement vers le plus court chemin pour des dizaines de milliers de graphes, comptant jusqu’à des dizaines de milliers de sommets et des centaines de milliers d’arêtes.

À ce stade, que le modèle proposé soit fidèle ou non à la biologie, il semble y avoir là un théorème à démontrer. Des informaticiens [5] s’y sont attelés et ont prouvé que ce système converge effectivement vers le plus court chemin et ce, pour tout graphe ! [6]

Idée de la preuve

Fixons un graphe $G$, distinguons deux de ses sommets $s$ et $p$, puis désignons (arbitrairement) $s$ comme source et $p$ comme puits. Fixons des capacités arbitraires sur les arêtes et appliquons la dynamique précédente.

On peut associer à ce système une énergie qui décroît en fonction du temps, et le conduit donc vers une solution d’énergie minimale. Il s’avère que les états d’énergie minimale sont les superpositions d’états « supportés » par des plus courts chemins entre $s$ et $p$ dans $G$. Dans le cas le plus courant, où il y a un seul plus court chemin, cela prouve la convergence. Les cas pathologiques sont plus épineux à étudier.

Les informaticiens seront peut-être surpris d’apprendre que le théorème flot maximal-coupe minimale se cache derrière cette énergie...

Algorithmes naturels

Au final, l’étude de cet organisme unicellulaire donne de nouvelles idées pour un problème qui fait sécher les informaticiens depuis quelques décennies : calculer de manière décentralisée le plus court chemin dans un graphe. La décentralisation exige, ici, que chaque noeud effectue une partie du calcul en se basant uniquement sur l’information dont il dispose localement. Cet algorithme d’inspiration biologique est un exemple assez spectaculaire d’algorithme naturel, [7] dont l’étude laisse encore de belles pages à écrire.

Post-scriptum :

Article édité par Dujardin Romain et Xavier Goaoc. Merci à Pierre-Antoine Guihéneuf et Denis Chadebec pour leurs relectures attentives et leurs nombreuses suggestions.

Notes

[1Tout ce que vous avez toujours voulu savoir sur le blob sans jamais oser le demander Audrey Dussitour, Éditions des Équateurs, 2017

[2T. Nakagaki, H. Yamada, and Á. Tóth. Maze-solving by an amoeboid organism. Nature, 407:470, 2000.

[3Les prix Ig-Nobel distinguent chaque année des travaux scientifiques qui font rire, puis réfléchir. La liste des récipiendaires est disponible ici (jetez un œil au prix Ig-Nobel 2010 en logistique « transportation planning »).

[4A. Tero, R. Kobayashi, and T. Nakagaki. A mathematical model for adaptive transport network in path finding by true slime mold. Journal of Theoretical Biology, pages 553–564, 2007, voir aussi ici.

[5V. Bonifaci, K. Mehlhorn, and G. Varma. Physarum can compute shortest paths. Journal of Theoretical Biology, 309:121–133, 2012. Voir aussi ici.

[6Cf l’exposé de Kurt Melhorn au Collège de France, qui a largement inspiré cette chronique.

[7Cf le cours de Bernard Chazelle sur ce sujet au Collège de France

Partager cet article

Pour citer cet article :

Goaoc Xavier — «Calculer sans neurone» — Images des Mathématiques, CNRS, 2017

Crédits image :

Image à la une - Frankenstoen (flickr) [CC BY 2.5 (http://creativecommons.org/licenses/by/2.5)], via Wikimedia Commons
img_17287 - Daniel Brunner

Commentaire sur l'article

  • Calculer sans neurone

    le 28 juin à 12:23, par Gérard L

    Pourquoi parler de calcul, voire d’algorithme dans ce que fait cet organisme ...?
    Ce n’est vraisemblablement pas cette manière que le problème est résolu dans la nature.
    Créons un parallèle (à valider) avec un cheminement de courant électrique. Remplaçons chaque distance à parcourir par la résistance électrique associée. Appliquons une différence de potentiel entre le point de départ et celui d’arrivée souhaité. Les densités de courant s’établiront (sans calcul) d’elles-mêmes et privilégieront le parcours le plus efficace (celui minimisant la résistance rencontrée à chaque nœud et finalement le total). Un dispositif sensible à cette densité de courant dans chaque branche fournirait une représentation (plus ou moins naturelle) de ce parcours.
    Pas d’algorithme, ni de calcul...les lois de la physique font le travail.

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM