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

Le , par Olivier Famien, Chroniqueur Actualités
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


Vous avez aimé cette actualité ? Alors partagez-la avec vos amis en cliquant sur les boutons ci-dessous :


 Poster une réponse Signaler un problème

Avatar de Sodium Sodium - Membre extrêmement actif https://www.developpez.com
le 25/12/2018 à 14:53
Curieux qu'il n'y ait aucune mention du blob sur lequel des recherches similaires ont été menées.
http://sweetrandomscience.blogspot.c...outes-des.html
Avatar de dourouc05 dourouc05 - Responsable Qt & Livres https://www.developpez.com
le 25/12/2018 à 15:12
Quelle est la qualité de leur solution (écart par rapport à l'optimum) ? Je doute qu'ils arrivent à une quelconque preuve formelle, vu le contexte, mais ça reste une analyse intéressante de leur approche.

Pour la complexité, on ne peut pas extrapoler grand-chose de résultats sur quatre et huit villes, c'est trop petit… N'empêche, si leur temps est effectivement linéaire, ça serait un progrès remarquable (je ne connais pas d'heuristique qui ait une meilleure complexité que O(n log n) pour n villes).

À titre de comparaison, on a pu trouver, dans les années nonante, la solution optimale à des problèmes d'une quinzaine de villes en quelques centièmes de seconde (http://www.math.uwaterloo.ca/tsp/con...s/bench99.html), pas beaucoup plus pour une vingtaine de villes… Pourtant, la complexité est exponentielle, mais on ne le remarque qu'avec des dizaines ou centaines de milliers de villes.

Sinon, quid d'autres problèmes, intéressants, eux ? Genre, tournée de véhicules, beaucoup plus difficiles à optimiser (malgré sa classe de complexité, le TSP est assez simple à résoudre en pratique, sauf cas pathologique).
Avatar de pierre-y pierre-y - Membre éclairé https://www.developpez.com
le 25/12/2018 à 16:41
Citation Envoyé par Sodium Voir le message
Curieux qu'il n'y ait aucune mention du blob sur lequel des recherches similaires ont été menées.
http://sweetrandomscience.blogspot.c...outes-des.html
J'allais dire la même chose.
Avatar de Vulcania Vulcania - Membre confirmé https://www.developpez.com
le 25/12/2018 à 17:01
Si cette amibe est nourrie avec du café, pourrait-on la considérer comme un/une développeur(se) ?
Avatar de ptah35 ptah35 - Membre éclairé https://www.developpez.com
le 27/12/2018 à 0:13
Citation Envoyé par Sodium Voir le message
Curieux qu'il n'y ait aucune mention du blob sur lequel des recherches similaires ont été menées.
http://sweetrandomscience.blogspot.c...outes-des.html
L'article de 2010 est cité dans celui de 2018 et dans les deux cas il s'agit de Physarum polycephalum.
Avatar de Johnny P. Johnny P. - Membre actif https://www.developpez.com
le 28/12/2018 à 13:06
L'un des problèmes qui m'a donné des cauchemars à la fac
Avatar de bes51 bes51 - Membre à l'essai https://www.developpez.com
le 28/12/2018 à 15:21
Je suis impressionné du temps passé sur ce type de réflexion !
Quelle est l'application pratique ? Les livraisons d' Amazon ?
La belle affaire ! Vous croyez que c'est optimisé d'avoir 50 sociétés de livraison pour le dernier kilomètre en déplaçant une camionnette et un livreur pour transporter un colis de 300 g, qui plus est pas pressé mais qu'on veut avoir dans les 24 heures ?

On n'est pas sûr d'avoir la solution optimale pour livrer 20 clients dans la journée et on repasse deux fois chez le tiers des clients ; belle optimisation ! Il suffit de décrocher son téléphone plutôt que de faire de savants calculs.
Ou peut-être d'avoir un seul service de livraison finale mais efficace : ça s'appelle le facteur... ; malheureusement, il n'ont pas toujours fait leur boulot correctement et on a créé de nombreux services parallèles.
Avatar de Sodium Sodium - Membre extrêmement actif https://www.developpez.com
le 28/12/2018 à 15:34
La curiosité scientifique tout simplement. Toutes les recherches scientifiques n'ont pas pour but d'aboutir à une application pratique, d'autant plus qu'en sciences on trouve souvent des applications pratiques par accident. Le fait qu'un organisme unicellulaire sans cerveau parvienne à résoudre des problèmes mathématiques est déjà suffisamment passionnant.
Avatar de dourouc05 dourouc05 - Responsable Qt & Livres https://www.developpez.com
le 28/12/2018 à 15:47
Tu prends l'exemple des livraisons Amazon, mais justement ce type de problème apparaît pour déterminer des tournées optimales. C'est un problème de recherche (tant académique qu'industrielle) très actif, comme maintenant. Même la Poste s'y met (au moins en Belgique, avec bpost), avec leur système Géoroute.

Les tournées, c'est un problème bien plus complexe que le voyageur de commerce. Cependant, pas mal de techniques de résolution se basent sur de la génération de colonnes, des relâchements, des heuristiques diverses et variées, dans l'objectif d'utiliser un problème plus simple à résoudre (comme un voyageur de commerce, potentiellement avec l'une ou l'autre contrainte supplémentaire) pour apporter de l'information sur le problème d'origine. Tu as une petite liste d'applications sur le site de Guy Desaulniers, par exemple : https://www.gerad.ca/~guyd/pub.html.
Avatar de ManPaq ManPaq - Futur Membre du Club https://www.developpez.com
le 01/01/2019 à 4:56
Pour trouver un augure de qualité autant le récupérer dans les plus archaïques, le résultat n'en sera que plus mystérieux: l'alignement des étoiles est-il pris en compte? L'influence de Jupiter? Les scientifiques étaient certes auréolés d'une sainteté climatique mais prenons garde à ne pas les confondre avec les oracles des temps modernes (sans doute mieux que les politiques)...
Contacter le responsable de la rubrique Accueil

Partenaire : Hébergement Web