(Phys.org)—Onderzoekers hebben een algoritme ontworpen en geïmplementeerd dat computerproblemen oplost met behulp van een strategie die is geïnspireerd op de manier waarop een amoebe zich vertakt om hulpbronnen te verkrijgen. Het nieuwe algoritme, genaamd AmoebaSAT, kan het verzadigbaarheidsprobleem (SAT) oplossen - een moeilijk optimalisatieprobleem met veel praktische toepassingen - met ordes van grootte minder stappen dan het aantal stappen dat nodig is voor een van de snelste conventionele algoritmen.

De onderzoekers voorspellen dat het op amoeben geïnspireerde computersysteem verschillende voordelen kan bieden, zoals hoge efficiëntie, miniaturisatie, en een laag energieverbruik, dat zou kunnen leiden tot een nieuw computerparadigma voor probleemoplossing op nanoschaal met hoge snelheid.

Onder leiding van Masashi Aono, Associate Principal Investigator bij het Earth-Life Science Institute, Tokio Instituut voor Technologie, en bij PRESTO, Japans bureau voor wetenschap en technologie, de onderzoekers hebben een artikel gepubliceerd over het door amoeben geïnspireerde systeem in een recent nummer van Nanotechnologie .

"We hebben een manier gedemonstreerd om de enorme rekenkracht van natuurlijke fenomenen te benutten in termen van complexiteit en energie, "Aono vertelde" Phys.org .

De motivatie voor dit onderzoek komt voor een groot deel voort uit de aanhoudende trend van elektronische miniaturisering. Zoals de wetenschappers uitleggen, transistors zijn zo klein geworden dat ze de schaal naderen waarop thermische fluctuaties hun werking kunnen verstoren. Deze schommelingen moeten worden aangepakt, maar in plaats van te proberen hun impact te minimaliseren, recent onderzoek heeft gesuggereerd dat een beter alternatief zou kunnen zijn om met hen samen te leven. Veel biologische systemen, zoals de moleculaire motoren die betrokken zijn bij spiercontractie, doen dit al miljoenen jaren met succes.

In hun studie hebben ontwierpen de onderzoekers een computersysteem op nanoschaal dat bestaat uit een elektrische Browniaanse ratel, die hetzelfde basismechanisme gebruikt als een biologische moleculaire motor, om stroom op te wekken uit fluctuerende elektronen. In een elektrische Browniaanse ratel, thermische energie in een nanodraad zorgt ervoor dat elektronen willekeurig in één richting bewegen (bijv. links maar niet rechts) of op dezelfde plaats blijven. Door dit proces meerdere keren te herhalen, ontstaat er een gerichte elektronenstroom, resulterend in een elektrische stroom met stochastische (willekeurige) fluctuaties. Zoals eerder onderzoek heeft aangetoond, zolang er geen energie wordt overgedragen buiten het systeem, het proces is niet in strijd met de tweede wet van de thermodynamica.

Om hun op amoeben geïnspireerde computersysteem te implementeren, de onderzoekers ontwierpen een netwerk van elektrische Brownse ratels met talrijke "takken" of draden. De takken komen overeen met de pseudopoden van een amoebe, die zich over grote delen van de ruimte kan uitstrekken om de opname van voedingsstoffen te maximaliseren. Op een soortgelijke manier, de takken van het ratelnetwerk kunnen op stochastische wijze stroom leveren (die de binaire waarde "1" vertegenwoordigt) of geen stroom (die "0" voorstelt). Algemeen, beide systemen gebruiken willekeurige beweging, in combinatie met dynamische feedbackregeling, computertaken uit te voeren.

Om de rekencapaciteit van het AmoebaSAT-systeem te evalueren, de onderzoekers pasten het toe om een ​​moeilijk combinatorisch optimalisatieprobleem op te lossen, het SAT-probleem, wat in feite inhoudt dat wordt bepaald of een bepaalde formule die uit talrijke logische variabelen en beperkingen bestaat, 'bevredigbaar' is. Het SAT-probleem en de afgeleide problemen ervan hebben een breed scala aan toepassingen op gebieden, waaronder robotica, modellering, elektronische handel, en anderen.

"Om een ​​oplossing voor het SAT-probleem te zoeken, elke eenheid van het systeem moet zich op een stochastische manier gedragen en een 'fout' maken bij het verkennen van een bredere toestandsruimte; de fout geeft aan dat de bron niet wordt geleverd, zelfs als het remmende besturingssignaal niet wordt toegepast, " legde Aono uit. "In dit opzicht, de elektrische Browniaanse ratel is een van de beste apparaten om de problemen op te lossen, omdat het stochastische bewerkingen met fouten implementeert, zoals blootgesteld aan willekeurige thermische ruis. Verder, dit apparaat is voordelig omdat het weinig energie verbruikt, die vergelijkbaar zijn met thermische energie; het vergemakkelijkt grootschalige integratie om grote problemen op te lossen."

Tests toonden aan dat het AmoebaSAT-systeem een ​​succespercentage van 100% had bij het vinden van een oplossing voor verschillende SAT-problemen met 50 variabelen, het oplossen van deze problemen met een gemiddelde van ongeveer 3, 000 stappen. Een aangepaste versie van het algoritme, die effectiever kan omgaan met fout-inducerende willekeurige ruis, nog beter gepresteerd, gemiddeld minder dan 1800 stappen. Ter vergelijking, een van de snelst bekende lokale zoekalgoritmen, LopenSAT, vereiste orden van grootte meer stappen om dezelfde problemen op te lossen. Bovendien, de AmoebaSAT presteert significant beter dan WalkSAT naarmate het aantal variabelen toeneemt.

De onderzoekers stellen voor dat de superieure prestaties van de AmoebaSAT afkomstig zijn van de "gelijktijdige zoekfunctie", verwijzend naar de mogelijkheid om meerdere variabelen tegelijk bij te werken. In tegenstelling tot, WalkSAT-algoritmen en andere methoden die op conventionele digitale computers worden uitgevoerd, kunnen bij elke stap slechts één variabele bijwerken. Deze "seriële" functie is terug te voeren op de Turing-machine, die de conventionele notie van berekening definieerde. In de toekomst, de onderzoekers zijn van plan om de oorsprong van de prestatievoordelen van het nieuwe, op de natuur geïnspireerde algoritme verder te onderzoeken.

Een ander voordeel van het nieuwe algoritme dat het bijzonder veelbelovend maakt voor toekomstige ontwikkelingen, is de potentiële schaalbaarheid. Veel natuurlijke computers, zoals hersengeïnspireerde neurale netwerken, vereisen een groot aantal onderling verbonden draden die snel groeien naarmate de complexiteit van het probleem toeneemt, waardoor de schaalbaarheid van deze netwerken wordt beperkt. De op amoeben geïnspireerde architectuur vermijdt dit probleem omdat het aantal onderling verbonden eenheden alleen lineair groeit naarmate de complexiteit toeneemt.

Met al deze voordelen, de onderzoekers hopen dat op amoeben geïnspireerde computers meer zullen bieden dan alleen een nieuwigheid op het gebied van computergebruik, maar een praktische manier om toekomstige computertechnologie op nanoschaal te implementeren.

"Momenteel, we hebben zojuist het systeem ontworpen en geverifieerd dat het redelijk goed werkt, hoewel de correcte werking van de elektrische Brownse ratels al is bevestigd, " zei Aono. "In de nabije toekomst, we zullen het daadwerkelijke AmoebaSAT-systeem fabriceren dat is geïmplementeerd met behulp van de elektrische Browniaanse ratel en aantonen dat het met succes zijn uitstekende prestaties behaalt in termen van efficiëntie, miniaturisatie, en vermindering van het energieverbruik."

© 2015 Fys.org