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

Resumen Técnico: Generación de Instancias Adversarias y Entrenamiento Robusto para la Optimización Combinatoria Neuronal con Múltiples Objetivos

Planteamiento del Problema
El Aprendizaje por Refuerzo Profundo (DRL) ha emergido como un enfoque prometedor para resolver Problemas de Optimización Combinatoria Multiobjetivo (MOCOPs), ofreciendo una eficiencia superior en comparación con los algoritmos heurísticos y exactos tradicionales. Sin embargo, la robustez de estos resolvedores de DRL sigue siendo poco explorada, particularmente en lo que respecta a su rendimiento ante distribuciones de problemas diversas y complejas. Los estudios existentes sobre problemas de un solo objetivo sugieren que los modelos de DRL pueden sufrir de "aprendizaje de atajos" (shortcut learning), sobreajustándose a claves distributivas específicas y fallando cuando se prueban en instancias fuera de la distribución (OOD). En el contexto de los MOCOPs, donde el objetivo es aproximar un frente de Pareto que equilibre múltiples objetivos en conflicto, la vulnerabilidad de los resolvedores neuronales ante cambios de distribución y la falta de una evaluación sistemática de la robustez plantean desafíos significativos para su despliegue práctico.

Metodología
Los autores proponen un marco unificado que consta de dos componentes principales: un Ataque Adversario Basado en Preferencias (PAA) para exponer las debilidades del resolvedor y una Defensa Dinámica Aumentada por Preferencias (DPD) para mejorar la robustez.

1. Ataque Adversario Basado en Preferencias (PAA):

   • Objetivo: Generar instancias "difíciles" que degraden específicamente el rendimiento de los resolvedores de DRL bajo condiciones de preferencia específicas.
   • Mecanismo: El método trata la entrada del problema (por ejemplo, las coordenadas de los nodos en el TSP) como una variable aprendible. Actualiza iterativamente la entrada $x$ mediante el ascenso de gradiente para maximizar la pérdida de refuerzo $\ell(x; \theta)$ de un resolvedor objetivo.
   • Función de Pérdida: La pérdida se define como la pérdida del subproblema normalizada $L(\pi|x)$ dividida por una línea base, multiplicada por la log-probabilidad de la solución. Al maximizar esto, el ataque obliga al resolvedor a producir soluciones con una calidad de frente de Pareto deficiente (medida por el Hipervolumen, HV) para vectores de preferencia $\lambda$ específicos.
   • Resultado: El proceso genera un conjunto de instancias adversarias adaptadas a diferentes preferencias, reduciendo efectivamente la calidad de los frentes de Pareto resultantes.

2. Defensa Dinámica Aumentada por Preferencias (DPD):

   • Objetivo: Mejorar la generalizabilidad y la robustez de los resolvedores neuronales mediante el entrenamiento adversario.
   • Mecanismo: DPD realiza un ajuste fino (fine-tuning) sobre una mezcla de instancias limpias y un conjunto de instancias adversarias pregeneradas.
   • Selección de Preferencia Consciente de la Dificultad: Durante el entrenamiento, para cada instancia muestreada y preferencia $\lambda$, el método genera un conjunto de preferencias aumentadas localmente $\{\lambda'_i\}$ aplicando pequeñas perturbaciones aleatorias. Evalúa los valores de Tchebycheff de las soluciones generadas bajo estas preferencias aumentadas (con los parámetros del modelo fijos) y selecciona la preferencia $\lambda'_{adv}$ que produzca la peor calidad de solución (el valor de Tchebycheff más alto).
   • Entrenamiento: El resolvedor se actualiza entonces para minimizar la pérdida escalarizada específicamente para esta preferencia aumentada "más difícil" dentro del mini-lote (mini-batch). Esta estrategia tiene como objetivo evitar el sobreajuste a regiones de preferencia restringidas y obliga al modelo a aprender representaciones robustas a través del espacio de preferencias.

Contribuciones Clave

• Método PAA: Introducción de un método para generar sistemáticamente instancias difíciles para MOCOPs al apuntar a preferencias específicas, demostrando que los resolvedores neuronales pueden verse significativamente afectados por cambios de distribución adaptados a sus debilidades de subproblemas.
• Método DPD: Propuesta de una estrategia de defensa que integra la selección de preferencia consciente de la dificultad en el entrenamiento adversario. Este enfoque mitiga el sobreajuste y mejora el rendimiento fuera de la distribución sin requerir cambios en la arquitectura del modelo subyacente.
• Evaluación Exhaustiva: El marco es validado a través de tres MOCOPs clásicos: el Problema del Viajante Multiobjetivo (MOTSP), el Problema de Rutas de Vehículos con Capacidad Multiobjetivo (MOCVRP) y el Problema de la Mochila Multiobjetivo (MOKP).

Resultados Experimentales

• Eficacia del Ataque: El método PAA generó con éxito instancias que redujeron significativamente el Hipervolumen (HV) de las soluciones producidas por resolvedores neuronales competitivos (EMNH, PMOCO, CNH) en comparación con instancias limpias y otras perturbaciones de distribución (log-normal, beta, gamma). En varios casos, PAA superó a los métodos de ataque basados en aprendizaje existentes como ROCO-RL.
• Desempeño de la Defensa: Los modelos entrenados con DPD (por ejemplo, PMOCO-DPD, CNH-DPD, EMNH-DPD) demostraron mejoras consistentes en la robustez.
  • En instancias OOD gaussianas, los resolvedores mejorados con DPD lograron brechas de optimalidad más bajas en comparación con sus contrapartes no defendidas.
  • Notablemente, en Bi-CVRP100, el modelo WE-CA-DPD mejoró el HV en un 2.23% sobre la línea base WS-LKH, la mayor ganancia observada.
  • Los modelos DPD mantuvieron un fuerte rendimiento en instancias de mayor escala (hasta 200 nodos) e instancias de referencia diversas (kroAB100, etc.), a menudo acercándose al rendimiento de los resolvedores exactos mientras mantienen tiempos de inferencia significativamente menores (segundos vs. horas para métodos exactos).
• Eficiencia: El método de defensa añade un overhead computacional mínimo durante el entrenamiento y la inferencia, con modelos entrenados con DPD que se ejecutan órdenes de magnitud más rápido que los resolvedores exactos no aprendibles (por ejemplo, WS-DP).

Significancia y Reivindicaciones
El artículo afirma que el marco propuesto aborda una brecha crítica en la literatura con respecto a la robustez de los resolvedores de MOCOP neuronales. Al exponer explícitamente las vulnerabilidades del resolvedor mediante PAA y abordarlas sistemáticamente mediante DPD, los autores demuestran que los resolvedores neuronales pueden hacerse significativamente más robustos a los cambios de distribución y variaciones de preferencia. Los resultados sugieren que el entrenamiento adversario con selección de preferencia consciente de la dificultad es una estrategia efectiva para mejorar la generalizabilidad de la optimización combinatoria basada en DRL, haciendo que estos resolvedores sean más viables para aplicaciones del mundo real donde las distribuciones de problemas son dinámicas y complejas. Los autores concluyen que su trabajo sienta las bases para futuras extensiones a MOCOPs del mundo real dinámicos y entornos en línea.