Toshibas banebrydende algoritme realiserer verdens hurtigste, kombinatorisk optimering i størst skala

Toshiba Corporation har realiseret et stort gennembrud inden for kombinatorisk optimering – valget af de bedste løsninger blandt et enormt antal kombinatoriske mønstre – med udviklingen af ​​en algoritme, der leverer verdens hurtigste og største ydeevne, og en ca. 10 gange forbedring i forhold til nuværende metoder. Toshibas nye metode kan anvendes til så skræmmende, men væsentlige opgaver som at identificere effektive leveringsruter, at bestemme de mest effektive molekylære strukturer til at undersøge i udvikling af nye lægemidler, og opbygning af porteføljer af profitable finansielle produkter.

Den nyudviklede teknik, den simulerede bifurkationsalgoritme, opnår hurtigt meget nøjagtige omtrentlige løsninger (gode løsninger) til komplekse kombinatoriske optimeringsproblemer i stor skala - problemer, der har modstået løsningen i lang tid, og det er meget vanskeligt at løse ved hjælp af konventionelle teknikker. Potentielt endnu vigtigere, Algoritmen realiserer også fremragende skalerbarhed til en lav pris ved at bruge nuværende computere, som kan revolutionere nuværende optimeringsprocesser.

Toshiba vil bruge Simulated Bifurcation Algorithm til at bygge en serviceplatform, der hurtigt kan løse forskellige sociale og forretningsmæssige problemer, sigter mod kommercialisering i 2019.

Detaljer om den nye teknologi er offentliggjort i det akademiske onlinetidsskrift Videnskabens fremskridt .

Mange problemer kan kun løses ved at gennemsøge et stort antal muligheder for at finde de bedste kombinationer. Disse omfatter realisering af effektiv logistik (det rejsende sælgerproblem i matematik), dirigere trafikken for at lette trængsel, anvendelse af molekylært design til udvikling af lægemidler, og optimering af finansielle porteføljer. I dag, at realisere en sådan kombinatorisk optimering kræver en enorm mængde beregning, og det er stadig svært at bruge nuværende computere til at finde løsninger.

Der er voksende forventninger til, at næste generation af computerenheder, såsom kvantecomputere, vil vise vejen til bedre løsninger, og nuværende forskning sigter mod at udvikle computere specielt designet til kombinatorisk optimering ved brug af superledende kredsløb, lasere, og halvlederbaserede digitale computere. På trods af disse anstrengelser, det er fortsat en udfordring at øge størrelsen af ​​det løselige problem og at reducere beregningstiden.

For eksempel, det er stadig svært for kvantecomputere med superledende kredsløb at løse komplekse problemer i stor skala. Og mens nutidens halvlederbaserede digitale computere har gjort det nemmere at øge størrelsen af ​​det løselige problem, nuværende algoritmer til kombinatorisk optimering er svære at parallelisere, gør det svært at bruge parallel computing til at fremskynde problemløsning.

Toshiba har løst disse problemer ved at udvikle en ny kombinatorisk optimeringsalgoritme, den simulerede bifurkationsalgoritme. Det er meget paralleliserbart, og kan derfor nemt fremskynde problemløsning på standard digital computer gennem parallel beregning. Da nuværende storskala beregningssystemer kan bruges som de er, der er ingen grund til at installere nyt udstyr, gør det nemt at skalere op til en lav pris.

For eksempel, ved at bruge feltprogrammerbare gate arrays (FPGA'er), en god løsning på et optimeringsproblem med 2, 000 fuldt forbundne variabler (ca. 2 millioner forbindelser) kan opnås på kun 0,5 millisekunder. Dette er cirka 10 gange hurtigere end den laserbaserede kvantecomputer, der er anerkendt som verdens hurtigste, kan løse det samme problem. Ud over, ved hjælp af en klynge på otte GPU'er, Toshiba fik en god løsning på et storstilet problem, der involverede 100, 000 fuldt forbundne variabler (ca. 5 milliarder forbindelser) på kun få sekunder. Disse resultater åbner op for nye måder at løse store kombinatoriske optimeringsproblemer på i mange forskellige anvendelsesområder.

Den simulerede bifurkationsalgoritme udnytter bifurkationsfænomener, adiabatiske processer, og ergodiske processer i klassisk mekanik for hurtigt at finde meget præcise løsninger. Toshiba udledte princippet fra en teori om en kvantecomputer foreslået af virksomheden selv. Denne opdagelse i klassisk mekanik inspireret af kvantemekanik er en akademisk interessant, meget nyt resultat, der antyder eksistensen af ​​ukendte matematiske teoremer.

Fremad i år, Toshiba sigter nu mod at bruge dette nøgleteknologiske gennembrud til at realisere og kommercialisere en serviceplatform, der opfylder alle optimeringsbehov inden for logistik, finansiere, og andre områder af det moderne samfund.