Riepilogo Tecnico: Colmare il divario tra problemi di routing sintetici e reali tramite la generazione di istanze guidata da LLM e l'adattamento progressivo

Definizione del Problema

I metodi di Ottimizzazione Combinatoria Neurale (NCO) hanno raggiunto prestazioni allo stato dell'arte sui problemi di Vehicle Routing (VRP) sintetici, in particolare quelli con nodi distribuiti uniformemente. Tuttavia, persiste un significativo divario di generalizzazione quando questi modelli vengono applicati a scenari di routing del mondo reale, come i benchmark TSPLib e CVRPLib. Gli attuali solver neurali faticano ad adattarsi ai pattern strutturali eterogenei e non uniformi inerenti ai dataset autentici. Sebbene i Large Language Models (LLM) abbiano mostrato potenziale nell'evolvere euristiche e nel risolvere problemi di Ottimizzazione Combinatoria (COP) direttamente, essi spesso falliscono nel gestire istanze di media o grande dimensione (ad es. >50 nodi) a causa dei limiti di contesto e dei problemi di coerenza nell'elaborazione di descrizioni testuali estese. Di conseguenza, è necessario un framework che colmi il divario distributivo tra i dati di addestramento sintetici e i benchmark del mondo reale senza richiedere modifiche architettoniche ai solver o affidarsi esclusivamente al fine-tuning diretto, che spesso produce miglioramenti limitati.

Metodologia: EvoReal

Gli autori propongono EvoReal, un framework data-centric che sfrutta gli LLM per evolvere i generatori di dati piuttosto che per risolvere direttamente i problemi di routing. Il framework è composto da due componenti primarie: un modulo evolutivo guidato da LLM per la sintesi delle istanze e una strategia di fine-tuning progressivo per l'adattamento.

1. Sintesi di Istanze Evolutiva Guidata da LLM

Invece di sollecitare (prompting) gli LLM per risolvere istanze TSP o CVRP, EvoReal li sollecita per generare generatori di dati basati su codice che producono istanze sintetiche che mimano le distribuzioni del mondo reale.

• Rappresentazione del Generatore: Ogni generatore è definito da una descrizione della funzione, un'implementazione del codice (basata su PyTorch) e un punteggio di fitness.
• Allineamento Strutturale: Il processo evolutivo mira a minimizzare la divergenza tra la distribuzione sintetica generata dall'LLM ($D(h_\phi(Z))$) e la distribuzione target del mondo reale ($D_{real}$). La divergenza è misurata tramite metriche proxy, specificamente il gap di ottimalità medio su un set di validazione.
• Modularizzazione e Categorizzazione: Per catturare diversi pattern strutturali, il set di validazione (TSPLib/CVRPLib) viene segmentato in categorie basate su caratteristiche statistiche:
  • Energia FFT: Misura la periodicità globale o la ripetitività.
  • NN-Ratio (Coefficiente di Variazione): Misura la variazione nelle distanze del vicino più prossimo per distinguere tra layout a griglia, casuali o raggruppati (clustered).
  • In base a queste metriche, le istanze sono categorizzate in tipi (ad es. S1 per strutture ripetitive, S2 per strutture debolmente raggruppate/a griglia, S3 per aggregazioni locali). Sono stati evoluti generatori specializzati per ogni categoria.
• Processo Evolutivo: Il framework adatta l'approccio ReEvo (Reflective Evolution) con modifiche specifiche:
  • Selezione basata sul Rank: Seleziona la prole in base alla classifica di fitness per accelerare la convergenza.
  • Selezione Ritardata: La selezione avviene dopo il crossover e la mutazione per prevenire l'eliminazione prematura di candidati diversificati.
  • Meccanismi di Riflessione: Utilizza la riflessione a breve termine (confronto tra coppie di genitori) e la riflessione a lungo termine (distillazione di intuizioni per guidare la mutazione) per raffinare iterativamente i generatori.

2. Strategia di Fine-Tuning Progressivo

Una volta identificati i generatori ottimali, i solver neurali pre-addestrati (POMO e LEHD) subiscono un processo di fine-tuning progressivo in due fasi per colmare il gap sintetico-reale:

• Fase Uno (Adattamento Strutturale): Il modello viene sottoposto a fine-tuning su dati sintetici su larga scala generati dai generatori evoluti guidati dall'LLM. Questa fase espone il modello a pattern strutturali diversificati in stile TSPLib (distribuzioni miste di S1, S2, S3) senza modificare l'architettura del modello. L'obiettivo è allineare le rappresentazioni interne del modello con i prior strutturali dei dati del mondo reale.
• Fase Due (Adattamento Diretto): Il modello, ora adattato a strutture diverse, viene ulteriormente sottoposto a fine-tuning direttamente sulle istanze di benchmark reali (TSPLib/CVRPLib). Questa fase consente al modello di passare da compiti sintetici "facili" a casi reali "difficili", restringendo efficacementamente l'ultimo gap di performance.

Contributi Chiave

1. Framework EvoReal: L'introduzione di un nuovo framework che utilizza gli LLM per evolvere generatori di dati anziché solver. Questo approccio sintetizza istanze di VRP strutturalmente realistiche che mimano statisticamente le distribuzioni del mondo reale, affrontando la causa radice del divario di generalizzazione.
2. Strategia di Fine-Tuning Progressivo: Una strategia di adattamento in due fasi che prima allinea i solver neurali con distribuzioni diverse evolute dall'LLM e poi li affina sui dati reali di benchmark. Ciò consente un efficace adattamento del dominio senza modifiche architettoniche, superando il fine-tuning diretto sui soli dati reali.
3. Prestazioni allo Stato dell'Arte: Il framework dimostra miglioramenti significativi nella generalizzazione attraverso un ampio spettro di scale dei problemi su TSPLib e CVRPLib, raggiungendo nuovi risultati allo stato dell'arte per i solver neurali.

Risultati Sperimentali

Gli autori hanno valutato EvoReal su 70 problemi TSPLib e 100 problemi CVRPLib SetX, confrontandolo con i solver classici (Concorde, LKH-3, ORTools) e vari baseline neurali (POMO, LEHD, SGBS, CNF, ecc.).

• Performance TSPLib:
  • LEHD (nostro) con 50 iterazioni RRC ha raggiunto un gap di ottimalità complessivo dell'1,05% su TSPLib, superando significativamente altri metodi basati sull'apprendimento e restringendo il divario con Concorde.
  • POMO (nostro) ha ridotto il gap complessivo all'11,59%, un miglioramento sostanziale rispetto al POMO pre-addestrato (26,66%).
  • Il metodo ha mostrato una forza particolare su istanze di grande scala (1000–5000 nodi), dove i tradizionali solver neurali tipicamente degradano significativamente.
• Performance CVRPLib:
  • LEHD (nostro) ha raggiunto un gap complessivo del 2,71% su CVRPLib SetX, superando tutti gli altri solver neurali e rimanendo competitivo con ORTools.
  • La strategia di fine-tuning progressivo ha ridotto notevolmente la disparità di performance tra istanze piccole e grandi.
• Studi di Ablazione:
  • Rimuovendo la Fase 1 o la Fase 2 della strategia di fine-tuning, le performance sono peggiorate, confermando la necessità dell'approccio progressivo.
  • Confrontando i generatori evoluti con i generatori di distribuzione ingenui (Gaussian, Beta, ecc.), si è visto che i generatori evoluti tramite LLM hanno costantemente ottenuto gap di ottimalità inferiori, validando la loro capacità di catturare complessi caratteri strutturali.
  • Il framework si è dimostrato robusto tra diversi LLM, con OpenAI o3 che ha fornito le migliori prestazioni del generatore.

Significato e Rivendicazioni

Il documento afferma che EvoReal riesce a colmare il divario di generalizzazione tra problemi di routing sintetici e reali spostando l'attenzione dall'evoluzione dei solver all'evoluzione delle distribuzioni di dati. Gli autori sottolineano che il loro approccio:

• Automatizza la Scoperta: Permette la scoperta automatizzata di generatori di dati che si allineano con i prior strutturali del mondo reale, un compito difficile da raggiungere con la progettazione manuale di euristiche.
• Efficienza: Ottiene questi guadagni senza richiedere un costoso ri-addestramento da zero o modifiche architettoniche ai già esistenti solver neurali SOTA.
• Scalabilità: Il metodo è efficace su una vasta gamma di dimensioni dei problemi, affrontando specificamente il degrado dei solver neurali su istanze di grande scala dove precedentemente fallivano nella generalizzazione.
• Superiorità rispetto al Fine-Tuning Diretto: I risultati dimostrano che l'adattamento dei modelli tramite distribuzioni sintetiche evolute (Fase 1) prima del fine-tuning diretto (Fase 2) produce una migliore generalizzazione rispetto al fine-tuning diretto sui dati reali, suggerendo che il "curriculum" di adattamento strutturale è critico per la robustezza.

Gli autori concludono che questa pipeline di adattamento basata su generatori offre una direzione promettente per migliorare l'applicabilità pratica dei metodi NCO in scenari logistici e di trasporto reali.