Une amibe vient de trouver un moyen totalement nouveau de résoudre un problème informatique classique

Une amibe vient de trouver un moyen totalement nouveau de résoudre un problème informatique classique

(Université Masashi Aono / Keio)

Une forme de vie gélatineuse unicellulaire vient de résoudre un problème de plus en plus complexe que beaucoup les chercheurs utilisent pour tester des algorithmes .

Encore plus impressionnant est le fait que, le problème devenant plus difficile à résoudre, l’amibe à moisissure visqueuse résolut le problème d’une manière totalement différente - et sans doute plus efficace - que la plupart des algorithmes.

Le résultat suggère que ces formes de vie simples pourraient en réalité offrir une méthode de traitement alternative aux ordinateurs conventionnels.

Ou, pour le dire plus simplement, nos appareils électroniques à la pointe de la technologie pourraient en réalité apprendre quelque chose d’une amibe. Aie.

Pour être clair, l'amibe n'était pas plus rapide que les ordinateurs, pas par un long étirement (regardez à quelle vitesse ils bougent dans la vidéo ci-dessous).

Mais bien que le problème soit devenu de plus en plus complexe, le temps de traitement de l'amibe n'a augmenté que de manière linéaire. Vous pouvez voir pourquoi c'est une grande différence ci-dessous:

Scénarios de croissance linéaire de la ligne bleue et de la ligne rouge exponentielle

Graphique linéaire vs exponentiel non lié ( Luo, Researchgate )

Le problème qu’il devait résoudre était le Problème de vendeur itinérant ou TPS en abrégé. Il s’agit essentiellement d’un problème d’optimisation qui nécessite un ordinateur qui consulte une liste de villes et calcule l’itinéraire le plus court, de sorte que chaque ville soit visitée une seule fois.

De plus en plus de villes sont ajoutées à l'itinéraire, le problème devient de plus en plus complexe - avec quatre villes sur la liste, il n'y a que trois itinéraires possibles à choisir. Mais pour huit villes, la situation saute à 2.520 itinéraires.

En d’autres termes, cela devient exponentiellement plus difficile et prendrait beaucoup plus de temps à la plupart des systèmes pour déterminer le meilleur itinéraire.

Mais une équipe de chercheurs de l’Université Keio au Japon a décidé de confier le problème à une «vraie moisissure visqueuse»: une amibe Physarum polycephalum et ont été surpris de constater qu’au fur et à mesure que les villes passaient de quatre à huit, l’organisme unicellulaire n’avait besoin que de suffisamment de temps pour trouver un itinéraire raisonnable (presque optimal).

"Dans cette étude, nous montrons que le temps nécessaire à Plasmodium pour trouver une solution de TSP de qualité raisonnablement élevée augmente linéairement à mesure que la taille du problème passe de quatre à huit". les chercheurs écrivent dans Royal Society Open Science .

"Ces résultats pourraient conduire au développement de nouveaux ordinateurs analogiques permettant de résoudre approximativement des problèmes d'optimisation complexes en temps linéaire."

Bien sûr, les amibes ne savent pas ce que sont les villes (autant que nous sachions), alors dans cette version du TSP, les "villes" étaient 64 canaux étroits (huit "villes" contenant chacune huit canaux) dans une plaque ronde placée sur sommet de la gélose.

Pour avoir accès à la gélose et absorber efficacement les nutriments, l'amibe pénètre dans les canaux.

Le «parcours» du vendeur qu’il choisit est la forme de son corps qui change constamment. Ainsi, il crée une forme de corps lorsqu’il pénètre dans un canal, une forme de corps différente lorsqu’il pénètre ensuite dans un second canal, etc.

Capture d'écran 2018 12 21 à 15h23,36

(Aono et al. Royal Society Open Science )

Pour s'assurer que l'amibe entrait de manière optimale dans les "villes", les chercheurs ont utilisé la lumière (ce que l'amibe n'aime pas) pour éclairer certains canaux trop éloignés ou qu'elle avait déjà visités, et pour l'empêcher d'entrer. plusieurs canaux simultanément.

À l’étonnement de l’équipe, l’amibe n’a pas mis plus de temps à trouver un moyen raisonnable (presque optimal) d’entrer huit canaux différents que quatre, malgré l’augmentation du nombre de configurations possibles.

"Intéressant" l'équipe a ajouté , "la qualité de la solution ne se dégrade pas malgré l'expansion explosive de l'espace de recherche."

Pour être honnête, les ordinateurs conventionnels sont plutôt astucieux et peuvent également résoudre le problème en temps linéaire, car il devient exponentiellement plus difficile.

Mais, en réalité, ils le faisaient d'une manière complètement différente: l'amibe testait constamment de nouvelles formes corporelles à une vitesse constante et traitait en même temps le retour optique, ce dont les ordinateurs pourraient tirer parti.

Les chercheurs affirment qu'ils ont limité l'expérience à huit canaux, car ils ne pouvaient pas créer une plaque assez grande pour en tester davantage. Mais s'ils le pouvaient, ils pensent que l'envie naturelle de l'amibe de rechercher un équilibre stable lui permettrait de calculer des itinéraires optimaux. des centaines de «villes».

Ils ont même mis au point une simulation informatique appelée AmoebaTSP qui reproduit certains des processus de traitement de l'amibe, mais nous avons encore beaucoup à apprendre.

"Le mécanisme par lequel l'amibe maintient la qualité de la solution approximative, c'est-à-dire la longueur du trajet, reste un mystère", a déclaré le chef de l'équipe, Masashi Aono. a dit Lisa Zyga à Phys.org.

L'équipe Keio n'est pas la seule à être excitée par le potentiel.

Dans leur papier, Aono et son équipe citer des groupes de recherche suggérant que les circuits électriques inspirés de l'amibe pourraient aider à résoudre des énigmes classiques tels que le problème de satisfaction de contrainte , Problème de satisfiabilité booléenne , et même aider à trouver des manœuvres de marche pour robots multi-jambes .

Ça fera des moisissures, ça ira.

La recherche a été publiée dans Royal Society Open Science .

Loading ..

Recent Posts

Loading ..