Contributo dell'Istituto di automazione, Accademia cinese delle scienze

Qubit |. Account pubblico QbitAI

Ci vogliono solo 15 secondi per risolvere il problema della pianificazione stocastica, che è 1440 volte più veloce dei metodi tradizionali!

Una nuova ricerca dell’Istituto di automazione dell’Accademia cinese delle scienze ha utilizzato la GCN per ottenere nuove scoperte in tali problemi. Il documento è stato selezionato per ICML 2024, la principale conferenza sull’intelligenza artificiale.

Ciò significa che è possibile ottenere un processo decisionale efficiente anche in condizioni incerte.

Il processo decisionale in condizioni di incertezza è un tipo importante di problema decisionale, che richiede ai decisori di considerare pienamente tutte le situazioni casuali e prendere la decisione più ragionevole.

Nel campo della matematica, una soluzione comunemente utilizzata è la programmazione stocastica, che include variabili casuali nei modelli di programmazione matematica.

Tra questi, la Programmazione stocastica a due stadi (2SP) è un metodo efficace per modellare tali problemi decisionali ed è ampiamente utilizzato.

Questo risultato dell'Istituto di Automazione, Accademia Cinese delle Scienze, il modello HGCN2SP (HGCN sta per Hierarchical Graph Convolution Network), è esattamente la combinazione del metodo 2SP eimmagineCombinato con le reti convoluzionali, il modello può essere utilizzato per risolvere tali problemi in modo più efficiente.

Il primo autore dell'articolo è Wu Yang, uno studente di dottorato presso l'istituto, e il ricercatore Zhang Yifan è l'autore corrispondente.

Cos'è la programmazione stocastica a due stadi?

L'idea di base della pianificazione stocastica è convertire le possibili situazioni future del problema in diversi scenari campione, quindi ottimizzare ciascuno scenario campione e infine integrare i risultati di ottimizzazione di tutti gli scenari per guidare le decisioni attuali.

Le sue aree di applicazione includono la gestione della catena di approvvigionamento, gli investimenti finanziari, il dispacciamento di energia, la gestione delle emergenze in caso di catastrofi, ecc.

La pianificazione stocastica a due fasi, come suggerisce il nome, divide il processo in due fasi.

Nello specifico, queste due fasi richiedono che vengano prese decisioni macro e micro rispettivamente per minimizzare i costi totali o massimizzare i benefici totali.

Le decisioni nella prima fase vengono prese prima che si manifesti l’incertezza, con l’obiettivo di ottimizzare la decisione iniziale per accogliere una varietà di possibili scenari futuri.

Le decisioni nella seconda fase vengono prese dopo che emerge l’incertezza e vengono adeguate in base alle decisioni della prima fase e a ciò che è effettivamente accaduto per ottimizzare il risultato complessivo.

Attraverso il modello 2SP, i decisori devono considerare pienamente l’impatto dei diversi scenari che possono verificarsi durante il processo decisionale, migliorando così la robustezza e la flessibilità del processo decisionale e prendendo decisioni più scientifiche ed efficienti.

Ad esempio, supponiamo di voler selezionare alcune delle 10 località candidate per costruire magazzini per soddisfare le esigenze di 20 aree circostanti.

Ciò che deve essere deciso nella prima fase è quale di queste 10 località candidate dovrebbe essere selezionata;

Nella seconda fase, deve essere determinata la relazione di distribuzione tra il magazzino e la regione. A questo punto, il numero di variabili decisionali arriva fino a 200 (ovvero, se il magazzino i distribuisce alla regione j).

△Immagine generata da DALL·E

Matematicamente, il problema 2SP è solitamente espresso come:

Tra questi, Q(x,ξ) rappresenta il problema di ottimizzazione del secondo stadio data la decisione del primo stadio x e lo scenario ξ, e la sua forma è:

Nella soluzione effettiva, vengono generalmente campionate N scene per calcolare il valore Q corrispondente per approssimare l'aspettativa.

Ovviamente, maggiore è N, più credibile è l'approssimazione. Tuttavia, all'aumentare del numero di scenari, la dimensione del problema si espande rapidamente, il che porterà ad un aumento significativo del tempo di soluzione.

Usiamo il problema della selezione dell'ubicazione del magazzino per illustrare. Per prendere decisioni migliori sulla selezione dell'ubicazione, dobbiamo prendere in considerazione fattori incerti come la domanda, il tempo, il flusso di persone, il traffico, ecc., e i cambiamenti in ciascun fattore corrispondono a un scenario.

Ciò significa che è necessario campionare ampiamente N diversi scenari per simulare il più fedelmente possibile la situazione reale. A questo punto, il numero totale di variabili decisionali nella seconda fase sarà pari a 200 N, rendendo il tempo di soluzione estremamente lungo.

Infatti, quando N è 500, anche utilizzando il più avanzato solutore commerciale Gurobi, saranno necessarie almeno 6 ore per prendere la decisione ottimale.

I metodi tradizionali utilizzano solitamente tecniche di campionamento casuale o clustering per selezionare un numero limitato di scenari (ad esempio 10 o 20) per una soluzione approssimativa. Sebbene il tempo sia ridotto, la qualità delle decisioni risultanti spesso non è ideale.

Sulla base di ciò, deriva l'idea progettuale del modello HGCN2SP: riducendo il numero di scene di campionamento, si ottengono risultati accurati nel modo più approssimativo possibile.

Utilizzo di reti convoluzionali a grafo per risolvere il problema 2SP

Il gruppo di ricerca ha proposto il modello HGCN2SP basato sulla rete di convoluzione del grafico gerarchico per risolvere il problema della programmazione stocastica a due stadi.

Nello specifico in termini di progettazione dell'algoritmo, il team ha caratterizzato il problema 2SP costruendo un grafico gerarchico, in cui il grafico inferiore è stato utilizzato per rappresentare le caratteristiche di ciascuna scena, mentre il grafico superiore è stato utilizzato per rappresentare la relazione tra le scene.

Quindi, la rete convoluzionale del grafico gerarchico (HGCN) viene utilizzata per estrarre le informazioni di incorporamento del sottografo della scena sottostante e le informazioni strutturali dello spazio della scena di livello superiore per estrarre la rappresentazione della scena.

Il decodificatore basato sul meccanismo dell'attenzione viene utilizzato per selezionare le scene in ordine. Non solo può trovare scene rappresentative per semplificare il problema, ma anche migliorare la selezione della base iniziale quando si risolve il problema con il metodo del simplesso ottimizzando l'ordine delle scene. scene. Migliora significativamente i tempi di soluzione.

△Struttura del modello HGCN2SP

Il team ha inoltre combinato l'apprendimento per rinforzo (RL) per esaminare in modo completo la qualità del processo decisionale e il tempo di soluzione per ottimizzare i parametri del modello, migliorando significativamente l'efficienza e la qualità della risoluzione dei problemi.

Nel problema dell'ubicazione del magazzino di cui sopra, sebbene HGCN2SP abbia selezionato solo 10 scenari, la differenza tra i risultati della sua decisione e la decisione presa dal solutore Gurobi in 6 ore era solo dell'1,7% e il tempo di soluzione era di soli 15 secondi, che equivale alla velocità Il miglioramento è di 1440 volte, il che riflette pienamente l'efficacia di questo metodo.

Inoltre, nell’esperimento del Network Design Problem (NDP), HGCN2SP ha ottenuto effetti decisionali simili in meno della metà del tempo rispetto ai metodi esistenti.

Soprattutto in casi su larga scala e in un gran numero di scenari, HGCN2SP mantiene ancora forti capacità di generalizzazione.

La proposta di HGCN2SP fornisce una nuova idea e uno strumento per risolvere complessi problemi 2SP e ha ampie prospettive di applicazione.

Il gruppo di ricerca prevede di ottimizzare ulteriormente il modello, ridurre i costi di formazione ed esplorare la sua applicazione in problemi più pratici.

Indirizzo cartaceo:
https://openreview.net/forum?id=8onaVSFTEj