Amoeba finder omtrentlige løsninger på NP-hårdt problem i lineær tid

Forskere har påvist, at en amøbe-en encellet organisme, der hovedsagelig består af gelatinøs protoplasma-har unikke computerkapaciteter, der en dag kan tilbyde et konkurrencedygtigt alternativ til de metoder, der bruges af konventionelle computere.

Forskerne, ledet af Masashi Aono ved Keio University, tildelt en amøbe til at løse Traveling Salesman Problem (TSP). TSP er et optimeringsproblem, hvor målet er at finde den korteste rute mellem flere byer, så hver by besøges nøjagtigt en gang, og start- og slutpunkterne er de samme.

Problemet er NP-hårdt, hvilket betyder, at når antallet af byer stiger, den tid, det tager for en computer at løse den, vokser eksponentielt. Kompleksiteten skyldes det store antal mulige løsninger. For eksempel, for fire byer, der er kun tre mulige ruter. Men for otte byer, antallet af mulige ruter stiger til 2520.

I den nye undersøgelse, forskerne fandt ud af, at en amøbe kan finde rimelige (næsten optimale) løsninger på TSP'en i et tidsrum, der kun vokser lineært, når antallet af byer stiger fra fire til otte. Selvom konventionelle computere også kan finde omtrentlige løsninger i lineær tid, amoebas tilgang er helt anderledes end traditionelle algoritmer. Som forskerne forklarer, amøben udforsker opløsningsrummet ved kontinuerligt at omfordele gelen i dens amorfe legeme med en konstant hastighed, samt ved at behandle optisk feedback parallelt i stedet for serielt.

Selvom en konventionel computer stadig kan løse TSP meget hurtigere end en amøbe, især for små problemstørrelser, de nye resultater er spændende og kan føre til udvikling af nye analoge computere, der udleder omtrentlige løsninger på beregningsmæssigt komplekse problemer af meget større størrelser i lineær tid.

Hvordan det virker

Den særlige type amøbe, som forskerne brugte, var et plasmodium eller "sand slimform, "som vejer cirka 12 mg og bruger havreflager. Denne amøbe deformerer hele tiden sit amorfe legeme ved gentagne gange at levere og trække gel ud med en hastighed på ca. 1 mm/sekund for at skabe pseudopodlignende vedhæng.

I deres eksperimenter, forskerne placerede amøben i midten af ​​en stjerne -chip, som er en rund plade med 64 smalle kanaler, der rager udad, og placerede derefter chippen oven på en agarplade. Amøben er begrænset i chippen, men kan stadig bevæge sig ind i de 64 kanaler.

For at maksimere dets næringsoptagelse, amøben forsøger at udvide inde i chippen for at komme i kontakt med så meget agar som muligt. Imidlertid, amøben kan ikke lide lys. Da hver kanal selektivt kan belyses af lys, det er muligt at tvinge amøben til at trække sig tilbage fra de belyste kanaler.

For at modellere TSP'en, hver kanal i stjernechippen repræsenterer en bestilt by på sælgerens rute. For eksempel, i tilfældet med fire byer mærket A-D, hvis amøben indtager kanalerne A4, B2, C1, og D3, så er den tilsvarende løsning til TSP'en C, B, D, EN, C.

For at guide amøben mod en optimal eller næsten optimal løsning, nøglen ligger i at kontrollere lyset. At gøre dette, forskerne bruger en neural netværksmodel, hvor systemet hvert sjette sekund opdaterer, hvilke kanaler der er belyst. Modellen indeholder oplysninger om afstanden mellem hvert par byer, samt feedback fra amøben nuværende position i kanalerne.

Modellen sikrer, at amøben finder en gyldig løsning på TSP på få måder. For eksempel, når amøben har indtaget en bestemt brøkdel af en bestemt kanal, sig A3, derefter kanalerne A1, A2, og alle andre "A" -kanaler belyses for at forhindre by A i at blive besøgt to gange. Også, B3, C3, D3, og alle andre "3" kanaler belyses for at forbyde samtidige besøg i flere byer.

Modellen redegør for afstandene mellem byer ved at gøre det lettere at belyse kanaler, der repræsenterer byer med længere afstande end med kortere afstande. For eksempel, sige amøben indtager kanal B2, og er begyndt at trænge ind i kanalerne C3 og D3 i lige store mængder, og afstanden mellem byerne B og C er 100, mens afstanden mellem byerne B og D er 50. Den længere afstand mellem B og C får til sidst systemet til at belyse kanal C3, får amøben til at trække sig tilbage fra den kanal, men tillader den at fortsætte med at bevæge sig ind i D3.

Samlet set, modellering af TSP'en med en amøbe udnytter amøbens naturlige tendens til at opsøge en stabil ligevægt. Da kanaler, der repræsenterer kortere ruter, er mindre tilbøjelige til at blive belyst, amøben kan sprede sig i disse kanaler og fortsætte med at udforske andre ikke-belyste kanaler for at maksimere sit overfladeareal på agarpladen.

Forskerne udviklede også en computersimulering kaldet AmoebaTSP, der efterligner nogle af hovedtrækkene i, hvordan amøben løser problemet, herunder den kontinuerlige bevægelse af gel, da den tilføres med en konstant hastighed og trækkes tilbage fra forskellige kanaler.

"I vores stjerne -chip til løsning af n -by TSP, det samlede areal af amoebens krop bliver n når amøben endelig finder en omtrentlig løsning, "Fortalte Aono Phys.org . "Der ser ud til at være en" lov "om, at amøben leverer sin gelatinøse ressource til at ekspandere i de ikke-belyste kanaler med en konstant hastighed, sige, x . Denne lov ville blive holdt, selv når nogle ressourcer hopper tilbage fra belyste kanaler. Derefter den tid, der kræves for at udvide kropsområdet n at repræsentere løsningen bliver n / x . Denne mekanisme ville være oprindelsen til den lineære tid, og det blev gengivet af vores computersimuleringsmodel.

"Men stadig, den mekanisme, hvormed amøben opretholder kvaliteten af ​​den omtrentlige løsning, det er, den korte rute længde, forbliver et mysterium. Det ser ud til, at rumligt og tidsmæssigt korrelerede bevægelser af de forgrenede dele af amøben placeret på fjerne kanaler er nøglen. Hver af disse grene svinger sit volumen med en vis tidsmæssig 'hukommelse' på belyste oplevelser. Grupper af filialerne udfører synkronisering og desynkronisering til deling af oplysninger, selvom de er rumligt fjerne. "

I fremtiden, forskerne planlægger yderligere at forbedre amøbernes computerevner.

"Vi vil undersøge nærmere, hvordan disse komplekse spatiotemporale oscillatoriske dynamikker forbedrer beregningsydelsen ved at finde løsninger af højere kvalitet på kortere tid, "sagde medforfatter Song-Ju Kim ved Keio University." Hvis det kunne afklares, viden vil bidrage til at skabe nye analoge computere, der udnytter den spatiotemporale dynamik af elektrisk strøm i dets kredsløb.

"Selvfølgelig, kører nogle andre algoritmer på traditionelle digitale computere i lineær tid, vi kan udlede omtrentlige løsninger til TSP. På den anden side, når vi kører vores simuleringsmodeller (AmoebaTSP eller dens udviklede versioner) på de traditionelle computere, som vi gjorde i denne undersøgelse, den analoge og parallelle spatiotemporale dynamik kræver ikke -lineær tid til at simulere dem som digitale og serielle processer. Så vi forsøger at opnå løsninger af meget højere kvalitet end dem, der stammer fra de traditionelle, ved at køre vores modeller på de analoge computere i lineær tid eller kortere. "

Forskerne forventer også, at ved at fremstille en større chip, amøben vil være i stand til at løse TSP -problemer med hundredvis af byer, selvom dette ville kræve titusinder af kanaler.

© 2018 Science X Network