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

Technische Samenvatting: Adversariële Instantiegeneratie en Robuuste Training voor Neurale Combinatorische Optimalisatie met Meerdere Doelstellingen

Probleemstelling
Deep Reinforcement Learning (DRL) is een veelbelovende aanpak geworden voor het oplossen van Multi-Objective Combinatorial Optimization Problems (MOCOPs), waarbij het een superieure efficiëntie biedt vergeleken met traditionele exacte en heuristische algoritmen. De robuustheid van deze DRL-solvers blijft echter onderbelicht, met name wat betreft hun prestaties over diverse en complexe probleemdistributies heen. Bestaande studies naar single-objective problemen suggereren dat DRL-modellen kunnen lijden onder "shortcut learning", waarbij ze overfitten op specifieke distributieve aanwijzingen en falen wanneer ze worden getest op out-of-distribution (OOD) instanties. In de context van MOCOPs, waar het doel is om een Pareto-front te benaderen die meerdere conflicterende doelstellingen balanceert, vormen de kwetsbaarheid van neurale solvers voor distributieverschuivingen en het gebrek aan systematische robuustheidsevaluatie aanzienlijke uitdagingen voor hun praktische inzetbaarheid.

Methodologie
De auteurs stellen een verenigd framework voor bestaande uit twee kerncomponenten: een Preference-based Adversarial Attack (PAA) om zwakheden van de solver bloot te leggen en een Dynamic Preference-augmented Defense (DPD) om de robuustheid te verbeteren.

1. Preference-based Adversarial Attack (PAA):

   • Doel: Om "harde" instanties te genereren die specifiek de prestaties van DRL-solvers onder specifieke voorkeurscondities verslechteren.
   • Mechanisme: De methode behandelt de probleeminput (bijv. knoopcoördinaten in TSP) als een leerbare variabele. Het werkt iteratief de input $x$ bij via gradiënt-ascent om de reinforcement loss $\ell(x; \theta)$ van een doel-solver te maximaliseren.
   • Verliesfunctie: De loss wordt gedefinieerd als de genormaliseerde subprobleem loss $L(\pi|x)$ gedeeld door een baseline, vermenigvuldigd met de log-waarschijnlijkheid van de oplossing. Door dit te maximaliseren, dwingt de aanval de solver om oplossingen te produceren met een slechte kwaliteit van het Pareto-front (gemeten via Hypervolume, HV) voor specifieke voorkeursvectoren $\lambda$.
   • Resultaat: Het proces genereert een adversariële instantie-pool die is afgestemd op verschillende voorkeuren, waardoor de kwaliteit van de resulterende Pareto-fronts effectief wordt verlaagd.

2. Dynamic Preference-augmented Defense (DPD):

   • Doel: Om de generaliseerbaarheid en robuustheid van neurale solvers te verbeteren door middel van adversariële training.
   • Mechanisme: DPD voert fine-tuning uit op een mengeling van schone instanties en een vooraf gegenereerde adversariële pool.
   • Hardness-Aware Preference Selection: Tijdens de training genereert de methode, voor elke gesamplede instantie en voorkeur $\lambda$, een set lokaal geaugmenteerde voorkeuren $\{\lambda'_i\}$ door kleine willekeurige perturbaties toe te passen. Het evalueert de Tchebycheff-waarden van oplossingen die zijn gegenereerd onder deze geaugmenteerde voorkeuren (met de modelparameters vastgezet) en selecteert de voorkeur $\lambda'_{adv}$ die de slechtste oplossingkwaliteit oplevert (hoogste Tchebycheff-waarde).
   • Training: De solver wordt vervolgens bijgewerkt om de gescalariseerde loss specifiek voor deze "hardste" geaugmenteerde voorkeur binnen de mini-batch te minimaliseren. Deze strategie heeft als doel overfitting naar beperkte voorkeursregio's te voorkomen en dwingt het model om robuuste representaties te leren over de voorkeursruimte.

Belangrijkste Bijdragen

• PAA Methode: Introductie van een methode om systematisch harde instanties voor MOCOPs te genereren door specifieke voorkeuren te targeten, waarmee wordt aangetoond dat neurale solvers aanzienlijk kunnen worden beïnvloed door distributieverschuivingen die zijn afgestemd op hun subprobleem-zwakheden.
• DPD Methode: Voorstel van een defensiestrategie die hardness-aware voorkeursselectie integreert in adversariële training. Deze aanpak mitigeert overfitting en verbetert de out-of-distribution prestaties zonder wijzigingen te vereisen in de onderliggende modelarchitectuur.
• Uitgebreide Evaluatie: Het framework wordt gevalideerd over drie klassieke MOCOPs: Multi-Objective Traveling Salesman Problem (MOTSP), Multi-Objective Capacitated Vehicle Routing Problem (MOCVRP) en Multi-Objective Knapsack Problem (MOKP).

Experimentele Resultaten

• Effectiviteit van de Aanval: De PAA-methode slaagde erin instanties te genereren die de Hypervolume (HV) van oplossingen geproduceerd door competitieve neurale solvers (EMNH, PMOCO, CNH) aanzienlijk verminderden in vergelijking met schone instanties en andere distributieve perturbaties (log-normaal, bèta, gamma). In verschillende gevallen presteerde PAA beter dan bestaande learning-based aanvalsmethoden zoals ROCO-RL.
• Defensieprestaties: Modellen getraind met DPD (bijv. PMOCO-DPD, CNH-DPD, EMNH-DPD) vertoonden consistente verbeteringen in robuustheid.
  • Op Gaussian OOD-instanties bereikten DPD-verbeterde solvers lagere optimaliteitsgaps vergeleken met hun niet-verdedigde tegenhangers.
  • Opvallend genoeg, op Bi-CVRP100, verbeterde het WE-CA-DPD model de HV met 2,23% ten opzichte van de WS-LKH baseline, de grootste winst die werd waargenomen.
  • DPD-modellen behielden sterke prestaties op grotere schaal instanties (tot 200 knopen) en diverse benchmark-instanties (kroAB100, etc.), waarbij ze vaak de prestaties van exacte solvers benaderden terwijl ze aanzienlijk lagere inferentietijden behielden (seconden versus uren voor exacte methoden).
• Efficiëntie: De defensiemethode voegt minimale computationele overhead toe tijdens training en inferentie, waarbij DPD-getrainde modellen orden van grootte sneller draaien dan niet-leerbare exacte solvers (bijv. WS-DP).

Betekenis en Claims
Het artikel claimt dat het voorgestelde framework een kritieke kloof in de literatuur aanpakt met betrekking tot de robuustheid van neurale MOCOP-solvers. Door expliciet de kwetsbaarheden van de solver bloot te leggen via PAA en deze systematisch aan te pakken via DPD, tonen de auteurs aan dat neurale solvers aanzienlijk robuuster kunnen worden gemaakt tegen distributieverschuivingen en variaties in voorkeuren. De resultaten suggereren dat adversariële training met hardness-aware voorkeursselectie een effectieve strategie is voor het verbeteren van de generaliseerbaarheid van DRL-gebaseerde combinatorische optimalisatie, wat deze solvers levensvatbaarder maakt voor real-world toepassingen waar probleemdistributies dynamisch en complex zijn. De auteurs concluderen dat hun werk de basis legt voor toekomstige uitbreidingen naar dynamische real-world MOCOPs en online omgevingen.