DEG: Diffusion-Enhanced GFlowNet per risolvere i problemi di instradamento dei veicoli

Abstract degli autori

I solutori neurali tradizionali per i problemi di instradamento dei veicoli (VRP) spesso soffrono di una diversità limitata delle soluzioni, il che ha motivato lo sviluppo di modelli basati su Generative Flow Network (GFlowNet). Tuttavia, l’efficacia di questi modelli è spesso limitata da un’espansione insufficiente del flusso nelle regioni ad alta ricompensa, che riduce la loro capacità di distribuire la probabilità tra percorsi di soluzione promettenti. Un’esplorazione più approfondita potrebbe portare a risultati superiori. I modelli di diffusione, al contrario, offrono indicazioni strutturali più efficaci per l’esplorazione. Questi due paradigmi sono naturalmente complementari: GFlowNet può fornire segnali a livello di arco da incorporare nel processo di diffusione, mentre la diffusione può guidare un’esplorazione più ampia. Sfruttando questa sinergia, proponiamo Diffusion-Enhanced GFlowNet (DEG), un nuovo framework che integra GFlowNet con un modello di diffusione per favorire una maggiore espansione del flusso verso le regioni ad alta ricompensa e ottenere soluzioni di qualità superiore. In particolare, DEG sfrutta la diversità intrinseca di GFlowNet per generare segnali retrogradi specifici per ciascun arco, applica a questi segnali il programma stocastico di rumore della diffusione per perturbarli e poi li denoisa nel paradigma GFlowNet. Per migliorare ulteriormente la scalabilità, introduciamo un decodificatore specializzato, in grado di adattarsi dinamicamente a problemi di dimensioni diverse. Valutazioni sperimentali approfondite su dataset sintetici e del mondo reale, comprendenti istanze con un massimo di 10.000 nodi, dimostrano che DEG ottiene sistematicamente prestazioni favorevoli rispetto ai metodi di riferimento.