Naturen kan hjælpe med at løse optimeringsproblemer

Dagens bedste digitale computere kæmper stadig med at løse, i en praktisk tidsramme, en bestemt problemklasse:kombinatoriske optimeringsproblemer, eller dem, der indebærer kæmning gennem store sæt muligheder for at finde den bedste løsning. Kvantecomputere har potentiale til at påtage sig disse problemer, men opskalering af antallet af kvantebit i disse systemer er stadig en hindring.

Nu, Forskere fra MIT Lincoln Laboratory har demonstreret et alternativ, analog-baseret måde at fremskynde beregningen af ​​disse problemer. "Vores computer fungerer ved at 'beregne med fysik' og bruger naturen selv til at hjælpe med at løse disse hårde optimeringsproblemer, "siger Jeffrey Chou, medleder forfatter til et papir om dette værk, der er offentliggjort i Nature's Videnskabelige rapporter . "Den er lavet af elektroniske standardkomponenter, tillader os at skalere vores computer hurtigt og billigt ved at udnytte den eksisterende mikrochipindustri. "

Det mest velkendte kombinatoriske optimeringsproblem er måske den rejsende sælgers problem. Problemet beder om at finde den korteste rute, en sælger kan tage gennem en række byer, starter og slutter ved den samme. Det kan virke enkelt med kun få byer, men problemet bliver eksponentielt svært at løse, efterhånden som antallet af byer vokser, bogser ned selv de bedste supercomputere. Alligevel skal optimeringsproblemer løses dagligt i den virkelige verden; løsningerne bruges til at planlægge vagter, minimere økonomisk risiko, opdage stoffer, planlægge forsendelser, reducere interferens på trådløse netværk, og meget mere.

"Det har været kendt i meget lang tid, at digitale computere grundlæggende er dårlige til at løse denne type problemer, "siger Suraj Bramhavar, også medforfatter. "Mange af de algoritmer, der er udviklet til at finde løsninger, skal afvikle løsningskvaliteten for tiden. At finde den absolut optimale løsning ender med at tage urimeligt lang tid, når problemstørrelserne vokser." At finde bedre løsninger og gøre det på dramatisk kortere tid kan spare industrier for milliarder af dollars. Dermed, forskere har ledt efter nye måder at bygge systemer designet specielt til optimering.

At finde takten

Naturen kan lide at optimere energi, eller opnå mål på den mest effektive og distribuerede måde. Dette princip kan ses i naturens synkronisering, som hjerteceller der slår sammen eller fiskeskoler, der bevæger sig som én. Tilsvarende hvis du sætter to pendulure på den samme overflade, uanset hvornår den enkelte pendula sættes i gang, de vil til sidst blive lullet ind i en synkroniseret rytme, når deres spids på samme tid, men bevæger sig i modsatte retninger (eller ude af fase). Dette fænomen blev først observeret i 1665 af den hollandske videnskabsmand Christiaan Huygens. Disse ure er et eksempel på koblede oscillatorer, indrettet på en sådan måde, at energi kan overføres mellem dem.

"Vi har hovedsageligt bygget en elektronisk, programmerbar version af denne [uropsætning] ved hjælp af koblede ikke -lineære oscillatorer, "Chou siger, viser en YouTube -video af metronomer, der viser et lignende fænomen. "Ideen er, at hvis du opretter et system, der koder for dit problems energilandskab, så vil systemet naturligvis forsøge at minimere energien ved at synkronisere, og ved at gøre det, vil nøjes med den bedste løsning. Vi kan derefter læse denne løsning op. "

Laboratoriets prototype er en type Ising -maskine, en computer baseret på en model i fysik, der beskriver et netværk af magneter, som hver har en magnetisk "spin" -retning, der kun kan pege op eller ned. Hvert spins endelige orientering afhænger af dets interaktion med hvert andet spin. De enkelte spin-to-spin interaktioner er defineret med en specifik koblingsvægt, hvilket angiver styrken i deres forbindelse. Målet med en Ising -maskine er at finde, givet et specifikt koblingsstyrkenetværk, den korrekte konfiguration af hvert spin, op eller ned, der minimerer den samlede systemenergi.

Men hvordan løser en Ising -maskine et optimeringsproblem? Det viser sig, at optimeringsproblemer kan kortlægges direkte på Ising -modellen, så et sæt spins med visse koblingsvægte kan repræsentere hver by og afstanden mellem dem i problemet med den rejsende sælger. Dermed, At finde den laveste energikonfiguration af spins i Ising-modellen oversætter direkte til løsningen for sælgerens hurtigste rute. Imidlertid, at løse dette problem ved individuelt at kontrollere hver af de mulige konfigurationer bliver uoverkommeligt svært, når problemerne vokser til selv beskedne størrelser.

I de seneste år, der har været bestræbelser på at bygge kvantemaskiner, der er tilknyttet Ising -modellen, den mest bemærkelsesværdige af dem er en fra det canadiske selskab D-Wave Systems. Disse maskiner kan tilbyde en effektiv måde at søge i det store løsningsrum og finde det korrekte svar, selvom de fungerer ved kryogene temperaturer.

Laboratoriets system kører en lignende søgning, men gør det ved hjælp af simple elektroniske oscillatorer. Hver oscillator repræsenterer et spin i Ising -modellen, og tager på samme måde en binær fase, hvor oscillatorer, der er synkroniserede, eller i fase, repræsenterer "spin up" -konfigurationen, og dem, der er ude af fase, repræsenterer "spin down" -konfigurationen. For at indstille systemet til at løse et optimeringsproblem, problemet er først kortlagt til Ising -modellen, oversætte det til programmerbare koblingsvægte, der forbinder hver oscillator.

Med koblingsvægte programmeret, oscillatorerne får lov til at køre, ligesom pendularmen for hvert ur, der frigives. Systemet slapper derefter naturligt af til sin samlede minimale energitilstand. Elektronisk aflæsning af hver oscillators sidste fase, repræsenterer "spin up" eller "spin down" "præsenterer svaret på det stillede spørgsmål. Da systemet kørte mod mere end 2, 000 problemer med tilfældig optimering, det kom til den korrekte løsning 98 procent af tiden.

Tidligere har forskere ved Stanford University demonstrerede en Ising -maskine, der bruger lasere og elektronik til at løse optimeringsproblemer. Dette arbejde afslørede potentialet for en betydelig hastighed i forhold til digital computing, selvom, ifølge Chou, systemet kan være svært og dyrt at skalere til større størrelser. Målet med at finde et enklere alternativ antændte laboratoriets forskning.

Opskalere

Det individuelle oscillatorkredsløb, teamet brugte i deres demonstration, ligner kredsløb, der findes inde i mobiltelefoner eller Wi-Fi-routere. En tilføjelse, de har foretaget, er en tværstangsarkitektur, der gør det muligt at koble alle oscillatorer i kredsløbet direkte til hinanden. "Vi har fundet en arkitektur, der både er skalerbar at fremstille og kan muliggøre fuld forbindelse til tusinder af oscillatorer, "Siger Chou. Et fuldt tilsluttet system gør det let at kortlægge det til en lang række optimeringsproblemer.

"Dette arbejde fra Lincoln Laboratory gør innovativ brug af en tværstangsarkitektur i sin konstruktion af en analog-elektronisk Ising-maskine, "siger Peter McMahon, en adjunkt i anvendt og teknisk fysik ved Cornell University, der ikke var involveret i denne forskning. "Det bliver interessant at se, hvordan fremtidens udvikling af denne arkitektur og platform fungerer."

Laboratoriets prototype Ising -maskine bruger fire oscillatorer. Teamet udarbejder nu en plan for at skalere prototypen til et større antal oscillatorer, eller "noder, "og fremstille det på et printkort." Hvis vi kan komme til, sige, 500 noder, der er en chance for, at vi kan begynde at konkurrere med eksisterende computere, og ved 1, 000 noder, vi kan muligvis slå dem, "Siger Bramhavar.

Teamet ser en klar vej frem til skalering, fordi teknologien er baseret på standard elektroniske komponenter. Det er også ekstremt billigt. Alle dele til deres prototype kan findes i et typisk elektriske ingeniørlaboratorium og blev købt online for omkring $ 20.

"Det, der begejstrer mig, er enkelheden, "Tilføjer Bramhavar." Kvantecomputere forventes at demonstrere fantastisk ydeevne, men de videnskabelige og tekniske udfordringer, der kræves for at skalere dem, er ret hårde. Demonstrerer selv en lille brøkdel af de præstationsgevinster, der forestilles med kvantecomputere, men gør det ved hjælp af hardware fra den eksisterende elektronikindustri, ville være et stort spring fremad. At udnytte disse kredsløbs naturlige adfærd til at løse virkelige problemer er et meget overbevisende alternativ til, hvad den næste æra af computing kan være. "

Denne historie er genudgivet med tilladelse fra MIT News (web.mit.edu/newsoffice/), et populært websted, der dækker nyheder om MIT -forskning, innovation og undervisning.