Les chercheurs ont démontré qu'une amibe, un organisme unicellulaire composé principalement de protoplasme gélatineux, possède des capacités informatiques uniques qui pourraient un jour offrir une alternative compétitive aux méthodes utilisées par les ordinateurs conventionnels.

Les chercheurs, dirigé par Masashi Aono à l'Université Keio, attribué une amibe pour résoudre le problème du voyageur de commerce (TSP). Le TSP est un problème d'optimisation dans lequel le but est de trouver le trajet le plus court entre plusieurs villes, pour que chaque ville soit visitée exactement une fois, et les points de départ et d'arrivée sont les mêmes.

Le problème est NP-difficile, ce qui signifie qu'au fur et à mesure que le nombre de villes augmente, le temps nécessaire à un ordinateur pour le résoudre augmente de façon exponentielle. La complexité est due au grand nombre de solutions possibles. Par exemple, pour quatre villes, il n'y a que trois itinéraires possibles. Mais pour huit villes, le nombre d'itinéraires possibles passe à 2520.

Dans la nouvelle étude, les chercheurs ont découvert qu'une amibe peut trouver des solutions raisonnables (presque optimales) au TSP dans un laps de temps qui ne croît que linéairement à mesure que le nombre de villes passe de quatre à huit. Bien que les ordinateurs conventionnels puissent également trouver des solutions approximatives en temps linéaire, l'approche de l'amibe est complètement différente des algorithmes traditionnels. Comme l'expliquent les scientifiques, l'amibe explore l'espace solution en redistribuant en continu le gel dans son corps amorphe à un débit constant, ainsi qu'en traitant le retour optique en parallèle plutôt qu'en série.

Bien qu'un ordinateur conventionnel puisse toujours résoudre le TSP beaucoup plus rapidement qu'une amibe, surtout pour les petites tailles de problèmes, les nouveaux résultats sont intrigants et peuvent conduire au développement de nouveaux ordinateurs analogiques qui dérivent des solutions approximatives de problèmes informatiques complexes de tailles beaucoup plus grandes en temps linéaire.

Comment ça fonctionne

Le type particulier d'amibe que les scientifiques ont utilisé était un plasmodium ou "vraie moisissure visqueuse, " qui pèse environ 12 mg et consomme des flocons d'avoine. Cette amibe déforme continuellement son corps amorphe en fournissant et en retirant du gel à plusieurs reprises à une vitesse d'environ 1 mm/seconde pour créer des appendices ressemblant à des pseudopodes.

Dans leurs expériences, les chercheurs ont placé l'amibe au centre d'une puce étoilée, qui est une plaque ronde avec 64 canaux étroits faisant saillie vers l'extérieur, puis placé la puce sur une plaque de gélose. L'amibe est confinée dans la puce, mais peut toujours se déplacer dans les 64 canaux.

Afin de maximiser son absorption des nutriments, l'amibe essaie de se dilater à l'intérieur de la puce pour entrer en contact avec autant d'agar que possible. Cependant, l'amibe n'aime pas la lumière. Étant donné que chaque canal peut être éclairé de manière sélective par la lumière, il est possible de forcer l'amibe à se retirer des canaux éclairés.

Afin de modéliser le TSP, chaque canal de la puce stellaire représente une ville ordonnée dans l'itinéraire du vendeur. Par exemple, dans le cas de quatre villes étiquetées A-D, si l'amibe occupe les canaux A4, B2, C1, et D3, alors la solution correspondante au TSP est C, B, RÉ, UNE, C.

Afin de guider l'amibe vers une solution optimale ou presque optimale, la clé réside dans le contrôle de la lumière. Pour faire ça, les chercheurs utilisent un modèle de réseau neuronal dans lequel toutes les six secondes, le système met à jour les canaux illuminés. Le modèle intègre des informations sur la distance entre chaque paire de villes, ainsi que la rétroaction de la position actuelle de l'amibe dans les canaux.

Le modèle garantit que l'amibe trouve une solution valable au TSP de plusieurs manières. Par exemple, une fois que l'amibe a occupé une certaine fraction d'un canal particulier, dire A3, puis les canaux A1, A2, et tous les autres canaux "A" sont éclairés afin d'interdire à la ville A d'être visitée deux fois. Aussi, B3, C3, D3, et tous les autres canaux "3" sont éclairés pour interdire les visites simultanées dans plusieurs villes.

Le modèle tient compte des distances entre les villes en facilitant l'éclairage des canaux qui représentent les villes avec des distances plus longues qu'avec des distances plus courtes. Par exemple, disons que l'amibe occupe le canal B2, et a commencé à empiéter sur les canaux C3 et D3 à parts égales, et la distance entre les villes B et C est de 100 tandis que la distance entre les villes B et D est de 50. La distance plus longue entre B et C amène finalement le système à illuminer le canal C3, provoquant le retrait de l'amibe de ce canal mais lui permettant de continuer à se déplacer dans D3.

Globalement, la modélisation du TSP avec une amibe exploite la tendance naturelle de l'amibe à rechercher un équilibre stable. Comme les canaux représentant des itinéraires plus courts sont moins susceptibles d'être éclairés, l'amibe peut s'étendre dans ces canaux et continuer à explorer d'autres canaux non éclairés afin de maximiser sa surface sur la plaque de gélose.

Les chercheurs ont également développé une simulation informatique appelée AmoebaTSP qui imite certaines des principales caractéristiques de la façon dont l'amibe résout le problème, y compris le mouvement continu du gel lorsqu'il est fourni à un débit constant et retiré de divers canaux.

"Dans notre puce stellaire pour résoudre le m -ville TSP, la surface totale du corps de l'amibe devient m quand l'amibe trouve enfin une solution approximative, " Aono a dit Phys.org . "Il semble y avoir une 'loi' selon laquelle l'amibe fournit sa ressource gélatineuse pour se développer dans les canaux non éclairés à un rythme constant, dire, X . Cette loi serait maintenue même lorsque certaines ressources rebondiraient des canaux éclairés. Ensuite, le temps nécessaire pour élargir la zone du corps m représenter la solution devient m / X . Ce mécanisme serait à l'origine du temps linéaire, et il a été reproduit par notre modèle de simulation informatique.

"Mais reste, le mécanisme par lequel l'amibe maintient la qualité de la solution approximative, C'est, la longueur du trajet court, Reste un mystère. Il semble que les mouvements corrélés spatialement et temporellement des parties ramifiées de l'amibe situées dans des canaux éloignés soient la clé. Chacune de ces branches oscille son volume avec une certaine « mémoire » temporelle sur des expériences illuminées. Des groupes de branches effectuent la synchronisation et la désynchronisation pour partager des informations même s'ils sont spatialement distants."

À l'avenir, les chercheurs prévoient d'améliorer encore les capacités de calcul de l'amibe.

"Nous étudierons plus en détail comment ces dynamiques oscillatoires spatio-temporelles complexes améliorent les performances de calcul en trouvant des solutions de meilleure qualité en moins de temps, " a déclaré le co-auteur Song-Ju Kim à l'Université Keio. " Si cela pouvait être clarifié, les connaissances contribueront à créer de nouveaux ordinateurs analogiques qui exploitent la dynamique spatio-temporelle du courant électrique dans son circuit.

"Bien sûr, exécuter d'autres algorithmes sur des ordinateurs numériques traditionnels pour un temps linéaire, nous pouvons dériver des solutions approximatives de TSP. D'autre part, lors de l'exécution de nos modèles de simulation (AmoebaTSP ou ses versions développées) sur les ordinateurs traditionnels comme nous l'avons fait dans cette étude, les dynamiques spatio-temporelles analogiques et parallèles nécessitent un temps non linéaire pour les simuler en tant que processus numériques et sériels. Nous essayons donc d'obtenir des solutions de bien meilleure qualité que celles dérivées des solutions traditionnelles en exécutant nos modèles sur des ordinateurs analogiques pendant un temps linéaire ou plus court."

Les chercheurs s'attendent également à ce que, en fabriquant une puce plus grosse, l'amibe pourra résoudre les problèmes de TSP avec des centaines de villes, bien que cela nécessiterait des dizaines de milliers de canaux.

© 2018 Réseau Science X