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

Résumé Technique : Génération d'Instances Adversaires et Entraînement Robuste pour l'Optimisation Combinatoire Neuronale à Objectifs Multiples

Énoncé du Problème
L'apprentissage par renforcement profond (DRL) est apparu comme une approche prometteuse pour résoudre les problèmes d'optimisation combinatoire multi-objectifs (MOCOP), offrant une efficacité supérieure par rapport aux algorithmes heuristiques et exacts traditionnels. Cependant, la robustesse de ces solveurs DRL reste peu explorée, particulièrement en ce qui concerne leur performance à travers des distributions de problèmes diverses et complexes. Les études existantes sur les problèmes à objectif unique suggèrent que les modèles DRL peuvent souffrir d'un « apprentissage par raccourci » (shortcut learning), s'ajustant excessivement à des indices distributionnels spécifiques et échouant lors de tests sur des instances hors distribution (OOD). Dans le contexte des MOCOP, où l'objectif est d'approximer un front de Pareto équilibrant plusieurs objectifs conflictuels, la vulnérabilité des solveurs neuronaux aux changements de distribution et l'absence d'évaluation systématique de la robustesse posent des défis importants pour leur déploiement pratique.

Méthodologie
Les auteurs proposent un cadre unifié comprenant deux composantes centrales : une Attaque Adversaire basée sur les Préférences (PAA) pour exposer les faiblesses du solveur et une Défense Dynamique augmentée par les Préférences (DPD) pour renforcer la robustesse.

1. Attaque Adversaire basée sur les Préférences (PAA) :

   • Objectif : Générer des instances « difficiles » qui dégradent spécifiquement les performances des solveurs DRL sous des conditions de préférences spécifiques.
   • Mécanisme : La méthode traite l'entrée du problème (par exemple, les coordonnées des nœuds dans le TSP) comme une variable apprenable. Elle met à jour de manière itérative l'entrée $x$ via l'ascension de gradient pour maximiser la perte de renforcement $\ell(x; \theta)$ d'un solveur cible.
   • Fonction de Perte : La perte est définie comme la perte du sous-problème normalisée $L(\pi|x)$ divisée par une référence (baseline), multipliée par la probabilité logarithmique de la solution. En maximisant cela, l'attaque force le solveur à produire des solutions ayant une faible qualité de front de Pareto (mesurée par l'Hypervolume, HV) pour des vecteurs de préférence $\lambda$ spécifiques.
   • Résultat : Le processus génère un réservoir d'instances adversaires adaptées à différentes préférences, abaissant efficacement la qualité des fronts de Pareto résultants.

2. Défense Dynamique augmentée par les Préférences (DPD) :

   • Objectif : Améliorer la généralisabilité et la robustesse des solveurs neuronaux grâce à l'entraînement adversarial.
   • Mécanisme : La DPD effectue un ajustement fin (fine-tuning) sur un mélange d'instances propres et d'un réservoir d'instances adversaires pré-générées.
   • Sélection de Préférence Sensible à la Difficulté : Pendant l'entraînement, pour chaque instance échantillonnée et préférence $\lambda$, la méthode génère un ensemble de préférences augmentées localement $\{\lambda'_i\}$ en appliant de petites perturbations aléatoires. Elle évalue les valeurs de Tchebycheff des solutions générées sous ces préférences augmentées (avec les paramètres du modèle fixes) et sélectionne la préférence $\lambda'_{adv}$ qui produit la pire qualité de solution (valeur de Tchebycheff la plus élevée).
   • Entraînement : Le solveur est ensuite mis à jour pour minimiser la perte scalarisée spécifiquement pour cette préférence augmentée la plus « difficile » au sein du mini-lot (mini-batch). Cette stratégie vise à prévenir le surapprentissage sur des régions de préférences restreintes et force le modèle à apprendre des représentations robustes à travers l'espace des préférences.

Principales Contributions

• Méthode PAA : Introduction d'une méthode pour générer systématiquement des instances difficiles pour les MOCOP en ciblant des préférences spécifiques, démontrant que les solveurs neuronaux peuvent être significativement affaiblis par des changements de distribution adaptés à leurs faiblesses de sous-problèmes.
• Méthode DPD : Proposition d'une stratégie de défense intégrant la sélection de préférence sensible à la difficulté dans l'entraînement adversarial. Cette approche atténue le surapprentissage et améliore la performance hors distribution sans nécessiter de modifications de l'architecture du modèle sous-jacent.
• Évaluation Complète : Le cadre est validé à travers trois MOCOP classiques : le Problème du Voyageur de Commerce Multi-Objectif (MOTSP), le Problème de Tournées de Véhicules à Capacité Limitée Multi-Objectif (MOCVRP) et le Problème du Sac à Dos Multi-Objectif (MOKP).

Résultats Expérimentaux

• Efficacité de l'Attaque : La méthode PAA a réussi à générer des instances qui ont réduit de manière significative l'Hypervolume (HV) des solutions produites par des solveurs neuronaux compétitifs (EMNH, PMOCO, CNH) par rapport aux instances propres et à d'autres perturbations de distribution (log-normale, bêta, gamma). Dans plusieurs cas, la PAA a surpassé les méthodes d'attaque basées sur l'apprentissage existantes comme ROCO-RL.
• Performance de la Défense : Les modèles entraînés avec la DPD (par exemple, PMOCO-DPD, CNH-DPD, EMNH-DPD) ont démontré des améliorations constantes de la robustesse.
  • Sur les instances OOD gaussiennes, les solveurs améliorés par la DPD ont obtenu des écarts d'optimalité plus faibles que leurs homologues non défendus.
  • Notamment, sur Bi-CVRP100, le modèle WE-CA-DPD a amélioré l'HV de 2,23 % par rapport à la ligne de base WS-LKH, le gain le plus important observé.
  • Les modèles DPD ont maintenu une performance solide sur des instances de plus grande échelle (jusqu'à 200 nœuds) et des instances de référence diverses (kroAB100, etc.), approchant souvent la performance des solveurs exacts tout en maintenant des temps d'inférence nettement inférieurs (secondes contre des heures pour les méthodes exactes).
• Efficacité : La méthode de défense ajoute un surcoût computationnel minimal pendant l'entraînement et l'inférence, les modèles entraînés par DPD s'exécutant avec des ordres de grandeur de vitesse supérieurs aux solveurs exacts non apprenables (ex: WS-DP).

Signification et Revendications
L'article affirme que le cadre proposé comble une lacune critique dans la littérature concernant la robustesse des solveurs MOCOP neuronaux. En exposant explicitement les vulnérabilités des solveurs via la PAA et en les traitant systématiquement via la DPD, les auteurs démontrent que les solveurs neuronaux peuvent devenir nettement plus robustes aux changements de distribution et aux variations de préférences. Les résultats suggèrent que l'entraînement adversarial avec sélection de préférence sensible à la difficulté est une stratégie efficace pour améliorer la généralisabilité de l'optimisation combinatoire basée sur le DRL, rendant ces solveurs plus viables pour des applications réelles où les distributions de problèmes sont dynamiques et complexes. Les auteurs concluent que leur travail jette les bases de futures extensions vers des MOCOP réels dynamiques et des environnements en ligne.