‘Electronic Amoeba’ trouve une solution approximative au problème du voyageur de commerce en temps linéaire


Un organisme amiboïde unicellulaire, un plasmodium issu de la vraie moisissure visqueuse Physarum polycephalum. Crédit photo: Masashi Aono

Des chercheurs de l’Université d’Hokkaido et d’Amoeba Energy au Japon, inspirés par le comportement de recherche de nourriture efficace d’ amibe unicellulaire, ont développé un ordinateur analogique pour trouver une fiable et rapide au problème du de commerce – un problème d’optimisation combinatoire représentatif.

De nombreuses tâches d’application réelles 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 laps de temps pratiquement permis car le nombre de solutions candidates qu’ils doivent évaluer augmente de façon exponentielle avec la taille du problème – également appelée explosion combinatoire. Par conséquent, ces dernières années, de nouveaux ordinateurs appelés machines Ising comprenant des machines de recuit quantique ont été activement développés. Cependant, ces machines nécessitent un prétraitement compliqué pour convertir chaque tâche dans la forme qu’elles peuvent traiter, et il y a un risque que des solutions illégales soient présentées qui ne répondent pas à certaines contraintes et exigences, créant des obstacles importants aux applications pratiques. pistes.

Ces obstacles peuvent être évités avec la nouvelle « amibe électronique », un ordinateur analogique qui s’inspire d’un organisme amibe unicellulaire. Il est connu que l’amibe maximise efficacement l’absorption des nutriments en déformant son corps. Il a été démontré qu’il trouve une solution au problème du voyageur de commerce (TSP), c’est-à-dire qu’avec une carte d’un certain nombre de villes, le problème est de trouver l’itinéraire le plus court à visiter et vers chaque ville exactement une fois Retournez à 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 limites et les exigences du TSP», explique Kasai. Les barres transversales facilitent la modification de la configuration de la ville en mettant à jour les valeurs de résistance sans aucun prétraitement compliqué.

Schéma du circuit de l’amibe électronique (à gauche: noyau d’amibe, à droite: croix de résistance). Crédit photo: Amoeba Energy

Kenta Saito, Ph.D. L’étudiant du laboratoire du Kasaï a fait le circuit sur une maquette et a trouvé le chemin le plus court pour le TSP à 4 villes. Il a évalué les performances pour des problèmes majeurs à l’aide d’un simulateur de circuit. Le circuit a ensuite trouvé de manière fiable une solution légale de haute qualité avec une longueur de route significativement plus courte que la longueur moyenne obtenue par l’échantillon 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. Si l’on compare le temps de recherche avec un algorithme TSP « 2-opt » représentatif, 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.

La performance de la recherche de solution TSP de l’amibe électronique en fonction du nombre de villes N. (à gauche) La longueur de la route obtenue à partir de l’amibe électronique (points rouges) a été normalisée par la longueur moyenne calculée par échantillonnage aléatoire. (À droite) Temps de recherche de la solution d’amibe électronique (points rouges) et temps de 2 opt sur un ordinateur conventionnel (cercle blanc) avec l’axe vertical représentant l’incrément des résultats pour le TSP à 10 villes. Crédit photo: Masashi Aono

«Parce que l’ordinateur analogique se compose d’un circuit simple et compact, il peut résoudre de nombreux problèmes du monde réel dans lesquels les entrées, les restrictions et les exigences changent de manière dynamique, et peut être intégré comme une puce à faible puissance dans les appareils IoT», explique Masashi Aono, qui dirige Amoeba Energy pour promouvoir l’utilisation pratique des ordinateurs inspirés des amibes.


Amoeba trouve des solutions approximatives au problème NP-difficile en temps linéaire


Plus d’information:
Kenta Saito et coll. Système informatique électronique analogique inspiré d’Amoeba avec barre transversale de résistance intégrée pour résoudre le problème du voyageur de commerce Rapports scientifiques (2020). DOI: 10.1038 / s41598-020-77617-7

Fourni par l’Université d’Hokkaido

Citation: ‘ Amoeba’ trouve une solution approximative au problème du voyageur de commerce en temps linéaire (2020, 10 décembre), consulté le 13 décembre 2020 sur https://phys.org/news/2020-12-electronic-amoeba- vendeur-solution-approximative. html

Ce document est soumis au droit d’auteur. Sauf pour le commerce équitable à des fins d’étude ou de recherche privée, aucune partie ne peut être reproduite sans autorisation écrite. Le contenu est fourni à titre informatif uniquement.

Laisser un commentaire