Elektronisk amøbe finder en omtrentlig løsning på rejsende sælgers problem i lineær tid

Forskere ved Hokkaido University og Amoeba Energy i Japan har, inspireret af den effektive foderadfærd hos en encellet amøbe, udviklet en analog computer til at finde en pålidelig og hurtig løsning på det rejsende sælgers problem - et repræsentativt kombinatorisk optimeringsproblem.

Mange virkelige applikationsopgaver som planlægning og planlægning i logistik og automatisering er matematisk formuleret som kombinatoriske optimeringsproblemer. Konventionelle digitale computere, herunder supercomputere, er utilstrækkelige til at løse disse komplekse problemer på praktisk tilladt tid, da antallet af kandidatløsninger, de skal evaluere, stiger eksponentielt med problemstørrelsen - også kendt som kombinatorisk eksplosion. Således nye computere kaldet Ising -maskiner, herunder kvanteglødgere, er udviklet aktivt i de seneste år. Disse maskiner, imidlertid, kræver kompliceret forbehandling for at konvertere hver opgave til den form, de kan håndtere og have risiko for at præsentere ulovlige løsninger, der ikke opfylder nogle begrænsninger og anmodninger, resulterer i store hindringer for de praktiske anvendelser.

Disse forhindringer kan undgås ved hjælp af den nyudviklede 'elektroniske amøbe, 'en analog computer inspireret af en encellet amoeboid organisme. Amøben er kendt for at maksimere næringsindtagelse effektivt ved at deformere sin krop. Det har vist sig at finde en omtrentlig løsning på problemet med rejsende sælger (TSP), dvs. givet et kort over et bestemt antal byer, problemet er at finde den korteste rute til at besøge hver by nøjagtigt en gang og vende tilbage til startbyen. Dette fund inspirerede professor Seiya Kasai ved Hokkaido University til at efterligne amøben dynamisk elektronisk ved hjælp af et analogt kredsløb, som beskrevet i tidsskriftet Scientific Reports. "Amoeba -kernen søger efter en løsning under det elektroniske miljø, hvor modstandsværdier ved kryds i tværstænger repræsenterer begrænsninger og anmodninger fra TSP, "siger Kasai. Ved hjælp af tværstængerne, byens layout kan let ændres ved at opdatere modstandsværdierne uden kompliceret forbehandling.

Kenta Saito, en ph.d. studerende i Kasais laboratorium, fremstillede kredsløbet på et brødbræt og det lykkedes at finde den korteste rute til 4-bys TSP. Han vurderede ydelsen for større problemer ved hjælp af en kredsløbssimulator. Derefter fandt kredsløbet pålideligt en juridisk løsning af høj kvalitet med en betydeligt kortere rutelængde end den gennemsnitlige længde opnået ved stikprøveudtagningen. I øvrigt, den tid, der kræves for at finde en juridisk løsning af høj kvalitet, voksede kun lineært til antallet af byer. Sammenligning af søgetiden med en repræsentativ TSP-algoritme "2-opt, "den elektroniske amøbe bliver mere fordelagtig, efterhånden som antallet af byer stiger." Det analoge kredsløb gengiver godt den unikke og effektive optimeringsevne for amøben, som organismen har erhvervet gennem naturligt udvalg, "siger Kasai.

"Da den analoge computer består af et enkelt og kompakt kredsløb, det kan løse mange virkelige problemer, hvor input, begrænsninger, og anmodninger ændres dynamisk og kan integreres i IoT-enheder som en strømbesparende mikrochip, "siger Masashi Aono, der leder Amoeba Energy for at fremme den praktiske brug af amoeba-inspirerede computere.