Forskare vid Hokkaido University och Amoeba Energy i Japan har, inspirerad av det effektiva födosöksbeteendet hos en encellig amöba, utvecklat en analog dator för att hitta en pålitlig och snabb lösning på problemet med resande säljare – ett representativt kombinatoriskt optimeringsproblem.

Många verkliga applikationsuppgifter som planering och schemaläggning inom logistik och automation är matematiskt formulerade som kombinatoriska optimeringsproblem. Konventionella digitala datorer, inklusive superdatorer, är otillräckliga för att lösa dessa komplexa problem inom praktiskt taget tillåten tid eftersom antalet kandidatlösningar de behöver för att utvärdera ökar exponentiellt med problemstorleken – även känd som kombinatorisk explosion. Alltså nya datorer som kallas Ising-maskiner, inklusive kvantglödgningsmedel, har utvecklats aktivt under senare år. Dessa maskiner, dock, kräver komplicerad förbehandling för att konvertera varje uppgift till den form de kan hantera och riskerar att presentera olagliga lösningar som inte uppfyller vissa begränsningar och önskemål, resulterar i stora hinder för praktiska tillämpningar.

Dessa hinder kan undvikas med den nyutvecklade "elektroniska amöban, ' en analog dator inspirerad av en encellig amöboidorganism. Amöban är känd för att maximera näringsinsamlingen effektivt genom att deformera sin kropp. Det har visat sig att hitta en ungefärlig lösning på resandeförsäljarproblemet (TSP), d.v.s. ges en karta över ett visst antal städer, problemet är att hitta den kortaste vägen för att besöka varje stad exakt en gång och återvända till startstaden. Detta fynd inspirerade professor Seiya Kasai vid Hokkaido University att efterlikna amöbans dynamik elektroniskt med hjälp av en analog krets, som beskrivs i tidskriften Scientific Reports. "Amöbankärnan söker efter en lösning under den elektroniska miljön där motståndsvärden vid korsningar av tvärbalkar representerar begränsningar och krav från TSP, säger Kasai. Med hjälp av tvärbalkarna, stadslayouten kan enkelt ändras genom att uppdatera resistansvärdena utan komplicerad förbearbetning.

Kenta Saito, en doktorsexamen student i Kasais labb, tillverkade kretsen på en breadboard och lyckades hitta den kortaste vägen för 4-city TSP. Han utvärderade prestandan för större problem med hjälp av en kretssimulator. Sedan hittade kretsen på ett tillförlitligt sätt en högkvalitativ laglig lösning med en betydligt kortare väglängd än den genomsnittliga längden som erhölls genom stickprovet. Dessutom, tiden som krävdes för att hitta en rättslig lösning av hög kvalitet växte bara linjärt till antalet städer. Jämför söktiden med en representativ TSP-algoritm "2-opt, " den elektroniska amöban blir mer fördelaktig när antalet städer ökar. "Den analoga kretsen återger väl amöbans unika och effektiva optimeringsförmåga, som organismen har förvärvat genom naturligt urval, säger Kasai.

"Då den analoga datorn består av en enkel och kompakt krets, den kan ta itu med många verkliga problem där input, begränsningar, och förfrågningar förändras dynamiskt och kan bäddas in i IoT-enheter som ett energibesparande mikrochip, säger Masashi Aono som leder Amoeba Energy för att främja den praktiska användningen av de amöba-inspirerade datorerna.