Adversarial Instance Generation and Robust Training for Neural Combinatorial Optimization with Multiple Objectives

Sintesi Tecnica: Generazione di Istanze Avversarie e Addestamento Robusto per l'Ottimizzazione Combinatoria Neurale con Molti Obiettivi

Definizione del Problema
Il Deep Reinforcement Learning (DRL) è emerso come un approccio promettente per risolvere i Problemi di Ottimizzazione Combinatoria Multi-Obiettivo (MOCOP), offrendo un'efficienza superiore rispetto agli algoritali euristici ed esatti tradizionali. Tuttavia, la robustezza di questi solver DRL rimane poco esplorata, in particolare per quanto riguarda le loro prestazioni su distribuzioni di problemi diverse e complesse. Gli studi esistenti sui problemi a obiettivo singolo suggeriscono che i modelli DRL possano soffrire di "apprendimento scorciatoia" (shortcut learning), ovvero l'overfitting su specifici indizi distribuzionali e il fallimento quando testati su istanze fuori distribuzione (OOD). Nel contesto dei MOCOP, dove l'obiettivo è approssimare una frontiera di Pareto che bilanci molteplici obiettivi contrastanti, la vulnerabilità dei solver neurali ai cambiamenti di distribuzione e la mancanza di una valutazione sistematica della robustezza pongono sfide significative al loro dispiegamento pratico.

Metodologia
Gli autori propongono un framework unificato composto da due componenti principali: un Attacco Avversario basato sulle Preferenze (PAA) per esporre le debolezze del solver e una Difesa Dinamica aumentata dalle Preferenze (DPD) per migliorare la robustezza.

1. Attacco Avversario basato sulle Preferenze (PAA):

   • Obiettivo: Generare istanze "difficili" che degradino specificamente le prestazioni dei solver DRL sotto specifiche condizioni di preferenza.
   • Meccanismo: Il metodo tratta l'input del problema (ad esempio, le coordinate dei nodi nel TSP) come una variabile apprendibile. Aggiorna iterativamente l'input $x$ tramite gradiente ascendente per massimizzare la perdita di rinforzo $\ell(x; \theta)$ di un target solver.
   • Funzione di Perdita: La perdita è definita come la perdita del sottoproblema normalizzata $L(\pi|x)$ divisa per un baseline, moltiplicata per la log-probabilità della soluzione. Massimizzando questo valore, l'attacco costringe il solver a produrre soluzioni con una scarsa qualità della frontiera di Pareto (misurata tramite Hypervolume, HV) per specifici vettori di preferenza $\lambda$.
   • Risultato: Il processo genera un pool di istanze avversarie su misura per diverse preferenze, riducendo efficacemente la qualità delle frontiere di Pareto risultanti.

2. Difesa Dinamica aumentata dalle Preferenze (DPD):

   • Obiettivo: Migliorare la generalizzabilità e la robustezza dei solver neurali attraverso l'addestramento avversario.
   • Meccanismo: DPD esegue il fine-tuning su un mix di istanze pulite e un pool avversario pre-generato.
   • Selezione delle Preferenze basata sulla Difficoltà (Hardness-Aware): Durante l'addestramento, per ogni istanza campionata e preferenza $\lambda$, il metodo genera un insieme di preferenze localmente aumentate $\{\lambda'_i\}$ applicando piccole perturbazioni casuali. Valuta i valori di Tchebycheff delle soluzioni generate sotto queste preferenze aumentate (con i parametri del modello fissi) e seleziona la preferenza $\lambda'_{adv}$ che produce la peggiore qualità della soluzione (massimo valore di Tchebycheff).
   • Addestramento: Il solver viene quindi aggiornato per minimizzare la perdita scalarizzata specificamente per questa preferenza aumentata "più difficile" all'interno del mini-batch. Questa strategia mira a prevenire l'overfitting su regioni di preferenza ristrette e costringe il modello a imparare rappresentazioni robuste attraverso lo spazio delle preferenze.

Contributi Chiave

• Metodo PAA: Introduzione di un metodo per generare sistematicamente istanze difficili per i MOCOP prendendo di mira specifiche preferenze, dimostrando che i solver neurali possono essere significativamente compromessi da cambiamenti di distribuzione mirati alle loro debolezze nei sottoproblemi.
• Metodo DPD: Proposta di una strategia di difesa che integra la selezione delle preferenze basata sulla difficoltà nell'addestramento avversario. Questo approccio mitiga l'overfitting e migliora le prestazioni fuori distribuzione senza richiedere modifiche all'architettura del modello sottostante.
• Valutazione Esaustiva: Il framework è validato attraverso tre classici MOCOP: il Problema del Commesso Viaggiatore Multi-Obiettivo (MOTSP), il Problema del Veicolo con Capacità Limitata Multi-Obiettivo (MOCVRP) e il Problema dello Zaino Multi-Obiettivo (MOKP).

Risultati Sperimentali

• Efficacia dell'Attacco: Il metodo PAA ha generato con successo istanze che hanno ridotto significativamente l'Hypervolume (HV) delle soluzioni prodotte da solver neurali competitivi (EMNH, PMOCO, CNH) rispetto alle istanze pulite e ad altre perturbazioni di distribuzione (log-normale, beta, gamma). In diversi casi, PAA ha superato i metodi di attacco basati sull'apprendimento esistenti come ROCO-RL.
• Prestazioni della Difesa: I modelli addestrati con DPD (ad esempio, PMOCO-DPD, CNH-DPD, EMNH-DPD) hanno dimostrato miglioramenti costanti nella robustezza.
  • Su istanze OOD gaussiane, i solver potenziati da DPD hanno ottenuto gap di ottimalità inferiori rispetto alle loro controparti non difese.
  • In particolare, su Bi-CVRP100, il modello WE-CA-DPD ha migliorato l'HV del 2,23% rispetto al baseline WS-LKH, il maggior guadagno osservato.
  • I modelli DPD hanno mantenuto forti prestazioni su istanze di scala maggiore (fino a 200 nodi) e su diverse istanze di benchmark (kroAB100, ecc.), spesso avvicinandosi alle prestazioni dei solver esatti pur mantenendo tempi di inferenza significativamente più bassi (secondi vs ore per i metodi esatti).
• Efficienza: Il metodo di difesa aggiunge un sovraccarico computazionale minimo durante l'addestramento e l'inferenza, con i modelli addestrati con DPD che operano ordini di grandezza più velocemente dei solver esatti non apprendibili (ad esempio, WS-DP).

Significatività e Rivendicazioni
Il documento sostiene che il framework proposto affronti una lacuna critica nella letteratura riguardante la robustezza dei solver MOCOP neurali. Esponendo esplicitamente le vulnerabilità del solver attraverso PAA e affrontandole sistematicamente tramite DPD, gli autori dimostrano che i solver neurali possono essere resi significativamente più robusti ai cambiamenti di distribuzione e alle variazioni di preferenza. I risultati suggeriscono che l'addestramento avversario con selezione delle preferenze basata sulla difficoltà è una strategia efficace per migliorare la generalizzabilità del decision-making basato su DRL, rendendo questi solver più idonei per applicazioni del mondo reale dove le distribuzioni dei problemi sono dinamiche e complesse. Gli autori concludono che il loro lavoro pone le basi per futuri sviluppi verso MOCOP reali dinamici e ambienti online.