Une “ amibe électronique ” trouve une solution approximative au problème du voyageur de commerce en temps linéaire –

De nombreuses tâches d’application du monde réel telles que la planification et la planification dans la logistique et l’automatisation sont formulées mathématiquement sous forme de problèmes d’optimisation combinatoire. Les ordinateurs numériques conventionnels, y compris les supercalculateurs, sont insuffisants pour résoudre ces problèmes complexes dans un temps pratiquement permis, car le nombre de solutions candidates dont ils ont besoin pour évaluer augmente de manière exponentielle avec la taille du problème – également appelée explosion combinatoire. Ainsi, de nouveaux ordinateurs appelés «machines d’Ising», comprenant des «recuits quantiques», ont été activement développés ces dernières années. Ces machines nécessitent cependant un prétraitement compliqué pour convertir chaque tâche dans la forme qu’elles peuvent traiter et risquent de présenter des solutions illégales qui ne répondent pas à certaines contraintes et demandes, ce qui entraîne des obstacles majeurs aux applications pratiques.

Ces obstacles peuvent être évités en utilisant la nouvelle “amibe électronique”, un ordinateur analogique inspiré par un organisme amiboïde unicellulaire. L’amibe est connue pour maximiser efficacement l’acquisition de nutriments en déformant son corps. Il a montré qu’il trouvait une solution approximative au problème du voyageur de commerce (TSP), c’est-à-dire que, compte tenu d’une carte d’un certain nombre de villes, le problème est de trouver l’itinéraire le plus court pour visiter chaque ville exactement une fois et revenir à la ville de départ. Cette découverte a inspiré le professeur Seiya Kasai de l’Université d’Hokkaido à imiter électroniquement la dynamique de l’amibe à l’aide d’un circuit analogique, comme décrit dans la revue Scientific Reports. «Le noyau d’amibe recherche une solution dans l’environnement électronique où les valeurs de résistance aux intersections des barres transversales représentent les contraintes et les demandes du TSP», explique Kasai. En utilisant les barres transversales, la disposition de la ville peut être facilement modifiée en mettant à jour les valeurs de résistance sans prétraitement compliqué.

Kenta Saito, étudiante en doctorat dans le laboratoire du Kasaï, a fabriqué le circuit sur une maquette et a réussi à trouver l’itinéraire le plus court pour le TSP à 4 villes. Il a évalué les performances pour des problèmes de plus grande taille à l’aide d’un simulateur de circuit. Ensuite, le circuit a trouvé de manière fiable une solution légale de haute qualité avec une longueur de route nettement plus courte que la longueur moyenne obtenue par l’échantillonnage aléatoire. De plus, le temps nécessaire pour trouver une solution juridique de qualité n’a augmenté que linéairement avec le nombre de villes. En comparant le temps de recherche avec un algorithme TSP représentatif «2-opt», l’amibe électronique devient plus avantageuse à mesure que le nombre de villes augmente. «Le circuit analogique reproduit bien la capacité d’optimisation unique et efficace de l’amibe, que l’organisme a acquise grâce à la sélection naturelle», déclare Kasai.

“L’ordinateur analogique étant constitué d’un circuit simple et compact, il peut résoudre de nombreux problèmes du monde réel dans lesquels les entrées, les contraintes et les demandes changent de manière dynamique et peut être intégré dans des appareils IoT en tant que micropuce d’économie d’énergie”, déclare Masashi Aono qui dirige Amoeba Energy pour promouvoir l’utilisation pratique des ordinateurs inspirés des amibes.

Il s’agit d’une publication conjointe entre l’Université d’Hokkaido et Amoeba Energy Co., Ltd.

Source de l’histoire:

Matériaux fourni par Université de Hokkaido. Remarque: le contenu peut être modifié pour le style et la longueur.