Amøbe-inspireret computersystem overgår konventionelle optimeringsmetoder

(Phys.org) – Forskere har designet og implementeret en algoritme, der løser computerproblemer ved hjælp af en strategi inspireret af den måde, en amøbe forgrener sig for at få ressourcer på. Den nye algoritme, kaldet AmoebaSAT, kan løse tilfredsstillelsesproblemet (SAT) - et vanskeligt optimeringsproblem med mange praktiske anvendelser - ved at bruge størrelsesordener færre trin end det antal trin, der kræves af en af ​​de hurtigste konventionelle algoritmer.

Forskerne forudser, at det amøbe-inspirerede computersystem kan byde på flere fordele, såsom høj effektivitet, miniaturisering, og lavt energiforbrug, der kunne føre til et nyt computerparadigme for højhastighedsproblemløsning i nanoskala.

Anført af Masashi Aono, Associate Principal Investigator ved Earth-Life Science Institute, Tokyo Institute of Technology, og hos PRESTO, Japan Science and Technology Agency, forskerne har offentliggjort en artikel om det amøbe-inspirerede system i et nyligt nummer af Nanoteknologi .

"Vi demonstrerede en måde at udnytte den enorme beregningskraft af naturlige fænomener med hensyn til kompleksitet og energi, " fortalte Aono Phys.org .

Motivationen for denne forskning kommer i høj grad fra den igangværende tendens med elektronisk miniaturisering. Som forskerne forklarer, transistorer er blevet så små, at de nærmer sig den skala, hvor termiske udsving kan forstyrre deres drift. Disse udsving skal adresseres, men i stedet for at forsøge at minimere deres indvirkning, nyere forskning har antydet, at et bedre alternativ kan være at sameksistere med dem. Mange biologiske systemer, såsom de molekylære motorer involveret i muskelsammentrækning, har gjort dette med succes i millioner af år.

I deres undersøgelse, forskerne designet et computersystem i nanoskala bestående af en elektrisk Brownsk skralde, som bruger den samme grundlæggende mekanisme som en biologisk molekylær motor, at generere strøm fra fluktuerende elektroner. I en elektrisk Brownsk skralde, termisk energi i en nanotråd får tilfældigt elektroner til enten at bevæge sig i én retning (f.eks. venstre men ikke højre) eller blive på samme sted. Gentagelse af denne proces flere gange genererer en rettet elektronstrøm, resulterer i en elektrisk strøm med stokastiske (tilfældige) udsving. Som tidligere forskning har vist, så længe der ikke overføres energi uden for systemet, processen overtræder ikke termodynamikkens anden lov.

For at implementere deres amøbe-inspirerede computersystem, forskerne designet et netværk af elektriske Brownske skralder med adskillige "grene" eller ledninger. Grenene svarer til en amøbes pseudopoder, som kan strække sig over store arealer for at maksimere næringsoptagelsen. På lignende måde, grenene af skraldenetværket kan levere strøm (som repræsenterer den binære værdi "1") eller ingen strøm (repræsenterer "0") på en stokastisk måde. Samlet set, begge systemer bruger tilfældig bevægelse, kombineret med dynamisk feedback kontrol, at udføre computeropgaver.

For at evaluere AmoebaSAT-systemets computerevne, forskerne brugte det til at løse et vanskeligt kombinatorisk optimeringsproblem kaldet SAT-problemet, hvilket grundlæggende involverer at bestemme, om en given formel bestående af adskillige logiske variabler og begrænsninger er "tilfredsstillende". SAT-problemet og dets afledte problemer har en bred vifte af applikationer inden for områder, herunder robotteknologi, modellering, elektronisk handel, og andre.

"For at søge efter en løsning på SAT -problemet, hver enhed i systemet skal opføre sig på en stokastisk måde og lave en 'fejl' for at udforske et bredere tilstandsrum; fejlen angiver, at ressourcen ikke tilføres, selv når det hæmmende styresignal ikke anvendes, " Aono forklarede. "I denne forbindelse, den elektriske Brownske skralde er en af ​​de bedste enheder til at løse problemerne, fordi den implementerer stokastiske operationer med fejl, som udsat for tilfældig termisk støj. Desuden, denne enhed er fordelagtig, fordi den bruger lave niveauer af energi, som kan sammenlignes med termisk energi; det letter integration i stor skala for at løse store problemer."

Tests viste, at AmoebaSAT-systemet havde en succesrate på 100 % i at finde en løsning på forskellige 50-variable SAT-problemer, løse disse problemer med et gennemsnit på omkring 3, 000 skridt. En modificeret version af algoritmen, som mere effektivt kan håndtere fejlinducerende tilfældig støj, fungerede endnu bedre, i gennemsnit færre end 1800 skridt. Til sammenligning, en af ​​de hurtigste kendte lokale søgealgoritmer, WalkSAT, krævede størrelsesordener flere trin for at løse de samme problemer. I øvrigt, AmoebaSAT udkonkurrerer WalkSAT mere markant, efterhånden som antallet af variabler stiger.

Forskerne foreslår, at AmoebaSAT's overlegne ydeevne stammer fra dens "samtidige søgefunktion", henviser til dens evne til at opdatere flere variabler samtidigt. I modsætning, WalkSAT-algoritmer og andre metoder, der kører på konventionelle digitale computere, kan kun opdatere én variabel ved hvert trin. Denne "serielle" funktion kan spores tilbage til Turing-maskinen, som definerede det konventionelle begreb om beregning. I fremtiden, forskerne planlægger at udforske oprindelsen af ​​den nye naturinspirerede algoritmes ydeevnefordele yderligere.

En anden fordel ved den nye algoritme, der gør den særligt lovende for fremtidige udviklinger, er dens potentielle skalerbarhed. Mange naturlige computere, såsom hjerne-inspirerede neurale netværk, kræver et stort antal indbyrdes forbundne ledninger, der vokser hurtigt, efterhånden som problemets kompleksitet vokser, begrænser skalerbarheden af ​​disse netværk. Den amøbe-inspirerede arkitektur undgår dette problem, fordi antallet af sammenkoblede enheder kun vokser lineært, efterhånden som kompleksiteten øges.

Med alle disse fordele, forskerne håber, at amøbe-inspireret computing vil tilbyde mere end blot en computernyhed, men en praktisk måde at implementere fremtidens nanoskala computerteknologi.

"I øjeblikket, vi har lige designet systemet og kontrolleret, at det fungerer ganske godt, selvom den korrekte drift af de elektriske Brownske skralder allerede er blevet bekræftet, " sagde Aono. "I den nærmeste fremtid, vi fremstiller det faktiske AmoebaSAT-system implementeret ved hjælp af den elektriske Brownske skralde og demonstrerer, at det med succes opnår sine fremragende præstationer med hensyn til effektivitet, miniaturisering, og reduktioner i energiforbruget."

© 2015 Phys.org