Onderzoekers van Hokkaido University en Amoeba Energy in Japan hebben, geïnspireerd door het efficiënte foerageergedrag van een eencellige amoebe, ontwikkelde een analoge computer voor het vinden van een betrouwbare en snelle oplossing voor het handelsreizigersprobleem - een representatief combinatorisch optimalisatieprobleem.

Veel praktische toepassingstaken, zoals planning en planning in logistiek en automatisering, zijn wiskundig geformuleerd als combinatorische optimalisatieproblemen. Conventionele digitale computers, inclusief supercomputers, zijn ontoereikend om deze complexe problemen in praktisch toelaatbare tijd op te lossen, aangezien het aantal kandidaatoplossingen dat ze moeten evalueren exponentieel toeneemt met de probleemomvang - ook wel combinatorische explosie genoemd. Dus nieuwe computers genaamd Ising-machines, inclusief kwantumuitgloeiers, zijn de afgelopen jaren actief ontwikkeld. Deze machines, echter, ingewikkelde voorbewerking vereisen om elke taak om te zetten in de vorm die ze aankunnen en het risico lopen illegale oplossingen te presenteren die niet voldoen aan bepaalde beperkingen en verzoeken, met als gevolg grote belemmeringen voor de praktische toepassingen.

Deze obstakels kunnen worden vermeden met behulp van de nieuw ontwikkelde 'elektronische amoebe, ' een analoge computer geïnspireerd door een eencellig amoeboïde organisme. Het is bekend dat de amoebe de opname van voedingsstoffen efficiënt maximaliseert door zijn lichaam te vervormen. Het heeft aangetoond een benaderende oplossing te vinden voor het handelsreizigerprobleem (TSP), d.w.z., gegeven een kaart van een bepaald aantal steden, het probleem is om de kortste route te vinden om elke stad precies één keer te bezoeken en terug te keren naar de startstad. Deze bevinding inspireerde professor Seiya Kasai van de Hokkaido University om de dynamiek van de amoebe elektronisch na te bootsen met behulp van een analoog circuit, zoals beschreven in het tijdschrift Scientific Reports. "De kern van de amoebe zoekt naar een oplossing in de elektronische omgeving waar weerstandswaarden op kruispunten van dwarsbalken beperkingen en verzoeken van de TSP vertegenwoordigen, " zegt Kasai. Met behulp van de dwarsbalken, de stadslay-out kan eenvoudig worden gewijzigd door de weerstandswaarden bij te werken zonder ingewikkelde voorbewerking.

Kenta Saito, een doctoraat student in Kasai's lab, fabriceerde het circuit op een breadboard en slaagde erin de kortste route voor de 4-steden TSP te vinden. Hij evalueerde de prestaties voor grotere problemen met behulp van een circuitsimulator. Vervolgens vond het circuit een betrouwbare juridische oplossing van hoge kwaliteit met een aanzienlijk kortere routelengte dan de gemiddelde lengte die werd verkregen door de willekeurige steekproeftrekking. Bovendien, de tijd die nodig was om een ​​juridische oplossing van hoge kwaliteit te vinden, groeide slechts lineair met het aantal steden. Door de zoektijd te vergelijken met een representatief TSP-algoritme "2-opt, " de elektronische amoebe wordt voordeliger naarmate het aantal steden toeneemt. "Het analoge circuit reproduceert goed het unieke en efficiënte optimalisatievermogen van de amoebe, die het organisme heeft verkregen door natuurlijke selectie, ' zegt Kasaï.

"Omdat de analoge computer uit een eenvoudig en compact circuit bestaat, het kan veel echte problemen aanpakken waarbij inputs, beperkingen, en verzoeken veranderen dynamisch en kunnen worden ingebed in IoT-apparaten als een energiebesparende microchip, ", zegt Masashi Aono, die Amoeba Energy leidt om het praktische gebruik van de op amoebe geïnspireerde computers te promoten.