Des chercheurs utilisent une amibe pour résoudre le problème du voyageur de commerce énoncé avec huit villes

Un problème d'optimisation très complexe

Des chercheurs japonais utilisent une amibe pour résoudre le problème du voyageur de commerce énoncé avec huit villes,
un problème d’optimisation très complexe

Alors que la recherche dans le domaine de l’informatique quantique bat son plein afin de trouver des solutions aux problèmes classiques difficiles à traiter avec les ordinateurs actuels, des chercheurs ont préféré suivre un autre chemin afin de résoudre un problème de mathématique extrêmement difficile. En informatique, le problème du voyageur de commerce pose un problème d’optimisation. Pour un sujet donné, il s’agit de parcourir un ensemble de villes séparées par des distances et trouver le plus court chemin pour parcourir ces villes une seule fois et revenir dans la ville de départ.

A priori, le problème paraît simple lorsque le nombre des villes est peu élevé. Mais plus le nombre de villes croit, plus le nombre de solutions augmente de manière exponentielle. Par exemple pour 4 villes données, il n’existe que 3 solutions possibles. Mais pour 6 villes, le nombre de solutions s’élève à 360. Vu qu’il n’existe pas d’algorithme permettant de trouver une solution exacte rapidement dans tous les cas, une équipe de chercheurs japonais de l’université de Keio à Tokyo s’est servie d’une amibe afin de chercher à trouver des solutions au problème. En principe, les amibes sont des organismes unicellulaires qui ne ressemblent en rien à un système nerveux central, ce qui les rend moins aptes à résoudre un casse-tête aussi complexe. Cependant, l’expérience des chercheurs japonais a permis de démontrer que cet organisme est un candidat idéal pour calculer des solutions presque optimales au problème du voyageur de commerce dans huit villes au maximum.

Il faut préciser que cet organisme unicellulaire du nom de Physarum polycephalum est capable de déformer son corps amorphe afin de pouvoir atteindre un point donné. Les chercheurs ont donc placé l’amibe dans une puce de 64 canaux. Et le tout a été positionné dans un environnement riche en nutriments afin d’amener l’organisme à s’étendre pour aller chercher de la nourriture. Par analogie au problème du voyageur de commerce, les canaux représentent les différentes villes à parcourir avant de revenir à la ville initiale. Les canaux ont été codifiés de A à H désignant chaque ville. Et pour définir l’ordre et le nombre de villes, un numéro de 1 à 8 est également attribué à chaque lettre pour déterminer les différentes étapes que l’amibe a suivies pour chercher et trouver la nourriture. Ainsi, si l’amibe étendait ses branches dans les canaux A3, B2, C4 et D1, la solution correcte au problème du voyageur de commerce serait D, B, A et C, car D1 indique que D est la première ville a avoir été parcourue, B2 indique que B est la deuxième ville, A3 indique que A devrait être la troisième ville et C4 indique que C est la quatrième avoir été parcourue.

Il faut souligner en outre que l’amibe est assez réticente au métal et attirée par les sources de nourritures, ce qui fait qu’elle reste sur la puce. Par ailleurs, elle a également montré une aversion pour les stimuli lumineux, ce qui fait qu’elle se rétractera lorsqu’une voie sera éclairée et sera prompte à s’étendre lorsqu’une piste ne le sera pas. Pour ne pas influencer volontairement l’organisme dans sa progression, tous les stimuli lumineux ont été mis à jour de manière synchrone sur la base d’un réseau de neurones.


Après avoir mené l’expérience avec ces 64 canaux, les chercheurs ont remarqué que le temps nécessaire au micro-organisme pour trouver une solution de qualité raisonnablement élevée au problème du commis voyageur (dans notre cas étendre son corps pour trouver le circuit de canaux le plus court afin d’atteindre les nutriments et revenir au point de départ) augmente de façon linéaire lorsque la taille du problème passe de quatre à huit villes. Et le fait le plus intéressant pour les chercheurs est que la qualité de la solution trouvée par le plasmodium ne s’est pas dégradée, même lorsque la taille du problème est devenue plus grande. Selon les chercheurs, ces résultats suggèrent que le plasmodium a la capacité de rechercher une solution de qualité raisonnablement élevée à un faible coût d’exploration.

Le souhait des chercheurs serait d’extrapoler l’expérience en construisant un modèle beaucoup plus grand représentant un nombre de villes beaucoup plus élevé afin de voir si les mêmes conclusions se confirment et trouver des applications informatiques à ce procédé.

Source : Royal Society

Et vous ?

Que vous suggère cette expérience ?

Pensez-vous que la prochaine révolution informatique pourrait se trouver dans les dispositifs informatiques basés sur la biologie ?

Voir aussi

À 18 ans, il montre qu'un algorithme classique peut être aussi performant qu'un algorithme quantique et relance le débat sur la suprématie quantique
Des chercheurs de Harvard ont créé un nouvel algorithme d'optimisation qui augmente de manière exponentielle la vitesse de calcul des ordinateurs
OpenAI conçoit un algorithme basé sur l'IA qui permet à un robot d'imiter des tâches réalisées par des humains dans un environnement virtuel
Des chercheurs trouvent un algorithme qui pourrait expliquer l'intelligence humaine et avancer le domaine de l'intelligence artificielle
Des chercheurs du MIT créent un algorithme permettant d'avoir « du visible dans l'invisible », le code disponible en open source