I nuovi algoritmi di Toshiba forniscono rapidamente soluzioni altamente accurate a problemi complessi

I nuovi algoritmi di Toshiba forniscono rapidamente soluzioni altamente accurate a problemi complessi
Il bSBM è circa 10 volte più veloce dell’aSBM nella risoluzione di un problema a 2000 bit. Credito: Toshiba Corporation

Toshiba Corporation e Toshiba Digital Solutions Corporation (collettivamente Toshiba), leader del settore nelle soluzioni per problemi di ottimizzazione su larga scala, hanno annunciato oggi il Ballistic Simulated Bifurcation Algorithm (bSB) e il Discrete Simulated Bifurcation Algorithm (dSB), nuovi algoritmi che superano di gran lunga le prestazioni del precedente algoritmo di biforcazione simulata (SB) di Toshiba. I nuovi algoritmi verranno applicati per trovare soluzioni a problemi altamente complessi in aree diverse come la gestione del portafoglio, lo sviluppo di farmaci e la gestione della logistica.

Introdotto nell’aprile 2019, il precedente SB ha aperto nuove strade come piattaforma per trovare soluzioni a problemi di ottimizzazione combinatoria, superando di un fattore 10 altri approcci. Toshiba ha ora esteso questo risultato con due nuovi algoritmi che applicano approcci innovativi, come un -effetto tunneling quantistico, al miglioramento delle prestazioni, consentendo loro di acquisire soluzioni ottimali (soluzioni esatte) per problemi di ottimizzazione combinatoria su larga scala che sfidano le capacità del loro predecessore. Implementato su una macchina da 16 GPU, dSB può trovare una soluzione quasi ottimale di un problema da un milione di bit, il problema combinatorio su scala più grande del mondo mai riportato in articoli scientifici, in 30 minuti攁 di calcolo che richiederebbero 14 mesi su una tipica CPU basato su computer. I risultati della ricerca sono stati pubblicati sulla rivista accademica online, Progressi scientifici, il 3 febbraio

I nuovi algoritmi hanno caratteristiche diverse. bSB è ottimizzato e denominato per la velocità di funzionamento e trova buone soluzioni approssimative in breve tempo. Genera meno errori rispetto a un algoritmo di biforcazione simulato adiabatico (aSB) riportato in precedenza e quindi restituisce risultati più rapidi e accurati. Implementato su un campo di gate programmabile array (FPGA), soprannominato la macchina di biforcazione simulata balistica (bSBM), ottiene una buona soluzione a un problema di 2.000 bit circa 10 volte più veloce della precedente macchina aSB (aSBM) (Figura 1).

I nuovi algoritmi di Toshiba forniscono rapidamente soluzioni altamente accurate a problemi complessi
dSBM confrontato con altre macchine per i tempi di calcolo per ottenere soluzioni ottimali per vari problemi. Credito: Toshiba Corporation

dSB è un algoritmo ad alta precisione. Sebbene implementato in un computer classico, arriva comunque a soluzioni ottimali più velocemente delle attuali macchine quantistiche. Il suo nome deriva dalla sostituzione delle variabili continue con variabili discrete nelle equazioni del moto. Questo mostra un effetto tunnel quasi quantistico che rompe i limiti degli approcci basati sulla meccanica classica, raggiungendo la soluzione ottimale del problema a 2000 bit.

Toshiba ha implementato dSB su un FPGA e costruito una macchina di biforcazione simulata discreta (dSBM) che raggiunge una velocità maggiore rispetto ad altre macchine in termini di tempi di calcolo necessari per ottenere soluzioni ottimali per vari problemi (Figura 2).

Implementato su una macchina da 16 GPU, il dSBM ha risolto un problema da un milione di bit, il più grande mai riportato in articoli scientifici, ed è arrivato a una soluzione quasi ottimale in 30 minuti? 0.000 volte più veloce di una macchina di ricottura simulata basata su CPU, che richiederebbero 14 mesi per eseguire il calcolo (Figura 3).

I nuovi algoritmi di Toshiba forniscono rapidamente soluzioni altamente accurate a problemi complessi
Tempi di calcolo per un problema da un milione di bit. Credito: Toshiba Corporation

Nell’applicare i due algoritmi ai problemi del mondo reale, Toshiba propone bSB per applicazioni che richiedono una risposta immediata e dSB per applicazioni che richiedono un’elevata precisione, anche se richiede tempi un po’ più lunghi.

Toshiba si aspetta che i nuovi algoritmi apportino maggiore efficienza all’industria, al business e ai processi decisionali complessi, affrontando problemi di ottimizzazione combinatoria in campi come i portafogli di investimento, lo sviluppo di farmaci e la pianificazione del percorso di consegna.

Commentando gli algoritmi, Hayato Goto, Chief Research Scientist presso il Corporate Research & Development Center di Toshiba Corporation, ha dichiarato: “Affrontiamo molti problemi del mondo reale in cui dobbiamo trovare la soluzione ottimale tra un numero enorme di scelte e dobbiamo anche affrontare esplosione combinatoria, in cui il numero di schemi di combinazione aumenta esponenzialmente all’aumentare della scala di un problema. Ecco perché la ricerca su computer speciali per l’ottimizzazione combinatoria viene condotta in tutto il mondo. Il nostro obiettivo è sviluppare una soluzione software攁lgoritmi in grado di risolvere grandi -ridimensionare i problemi di ottimizzazione combinatoria in modo rapido e preciso e contribuire alla realizzazione di maggiori efficienze.”

Toshiba offrirà gli algoritmi di biforcazione simulata di nuova concezione come servizio cloud basato su GPU e come versione locale implementata su un FPGA entro il 2021.


Leave a Reply