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

Resumo Técnico: Geração de Instâncias Adversárias e Treinamento Robusto para Otimização Combinatória Neural com Múltiplos Objetivos

Definição do Problema
O Aprendizado por Reforço Profundo (DRL) emergiu como uma abordagem promissora para resolver Problemas de Otimização Combinatória de Múltiplos Objetivos (MOCOPs), oferecendo uma eficiência superior em comparação com algoritmos heurísticos e exatos tradicionais. No entanto, a robustez desses resolvedores de DRL permanece pouco explorada, particularmente em relação ao seu desempenho através de distribuições de problemas diversas e complexas. Estudos existentes sobre problemas de objetivo único sugerem que os modelos de DRL podem sofrer de "aprendizado de atalhos" (shortcut learning), sobreajustando-se a pistas distributivas específicas e falhando ao serem testados em instâncias fora da distribuição (OOD). No contexto de MOCOPs, onde o objetivo é aproximar uma fronteira de Pareto equilibrando múltiplos objetivos conflitantes, a vulnerabilidade dos resolvedores neurais a mudanças de distribuição e a falta de uma avaliação sistemática de robustez impõem desafios significativos ao seu implantação prática.

Metodologia
Os autores propõem um framework unificado composto por dois componentes principais: um Ataque Adversário Baseado em Preferência (PAA) para expor as fraquezas do resolvedor e uma Defesa Dinâmica Aumentada por Preferência (DPD) para aumentar a robustez.

1. Ataque Adversário Baseado em Preferência (PAA):

   • Objetivo: Gerar instâncias "difíceis" que degradem especificamente o desempenho de resolvedores de DRL sob condições de preferência específicas.
   • Mecanismo: O método trata a entrada do problema (ex: coordenadas de nós no TSP) como uma variável aprendível. Ele atualiza iterativamente a entrada $x$ via ascensão de gradiente para maximizar a perda de reforço $\ell(x; \theta)$ de um resolvedor alvo.
   • Função de Perda: A perda é definida como a perda do subproblema normalizada $L(\pi|x)$ dividida por uma linha de base (baseline), multiplicada pela log-probabilidade da solução. Ao maximizar isso, o ataque força o resolvedor a produzir soluções com baixa qualidade de fronteira de Pareto (medida por Hipervolume, HV) para vetores de preferência $\lambda$ específicos.
   • Resultado: O processo gera um pool de instâncias adversárias adaptadas a diferentes preferências, reduzindo efetivamente a qualidade das fronteiras de Pareto resultantes.

2. Defesa Dinâmica Aumentada por Preferência (DPD):

   • Objetivo: Melhorar a generalizabilidade e a robustez de resolvedores neurais através de treinamento adversário.
   • Mecanismo: O DPD realiza o ajuste fino (fine-tuning) em uma mistura de instâncias limpas e um pool adversário pré-gerado.
   • Seleção de Preferência Consciente de Dificuldade (Hardness-Aware): Durante o treinamento, para cada instância amostrada e preferência $\lambda$, o método gera um conjunto de preferências localmente aumentadas $\{\lambda'_i\}$ aplicando pequenas perturbações aleatórias. Ele avalia os valores de Tchebycheff das soluções geradas sob essas preferências aumentadas (com os parâmetros do modelo fixos) e seleciona a preferência $\lambda'_{adv}$ que produz a pior qualidade de solução (maior valor de Tchebycheff).
   • Treinamento: O resolvedor é então atualizado para minimizar a perda escalonada especificamente para esta preferência aumentada "mais difícil" dentro do mini-lote (mini-batch). Esta estratégia visa prevenir o sobreajuste a regiões de preferência restritas e força o modelo a aprender representações robustas através do espaço de preferência.

Principais Contribuições

• Método PAA: Introdução de um método para gerar sistematicamente instâncias difíceis para MOCOPs visando preferências específicas, demonstrando que resolvedores neurais podem ser significativamente prejudicados por mudanças de distribuição adaptadas às suas fraquezas de subproblemas.
• Método DPD: Proposta de uma estratégia de defesa que integra a seleção de preferência consciente de dificuldade no treinamento adversário. Esta abordagem mitiga o sobreajuste e melhora o desempenho fora da distribuição sem exigir mudanças na arquitetura do modelo subjacente.
• Avaliação Abrangente: O framework é validado através de três MOCOPs clássicos: Problema do Caixeiro Viajante de Múltiplos Objetivos (MOTSP), Problema de Roteamento de Veículos Capacitado de Múltiplos Objetivos (MOCVRP) e Problema da Mochila de Múltiplos Objetivos (MOKP).

Resultados Experimentais

• Eficácia do Ataque: O método PAA gerou com sucesso instâncias que reduziram significativamente o Hipervolume (HV) das soluções produzidas por resolvedores neurais competitivos (EMNH, PMOCO, CNH) em comparação com instâncias limpas e outras perturbações de distribuição (log-normal, beta, gamma). Em vários casos, o PAA superou métodos de ataque baseados em aprendizado existentes, como o ROCO-RL.
• Desempenho da Defesa: Modelos treinados com DPD (ex: PMOCO-DPD, CNH-DPD, EMNH-DPD) demonstraram melhorias consistentes na robustez.
  • Em instâncias OOD gaussianas, os resolvedores aprimorados com DPD alcançaram lacunas de otimalidade menores em comparação com seus equivalentes não defendidos.
  • Notavelmente, no Bi-CVRP100, o modelo WE-CA-DPD melhorou o HV em 2,23% sobre a linha de base WS-LKH, o maior ganho observado.
  • Modelos DPD mantiveram um forte desempenho em instâncias de maior escala (até 200 nós) e benchmarks diversos (kroAB100, etc.), frequentemente aproximando-se do desempenho de resolvedores exatos enquanto mantêm tempos de inferência significativamente menores (segundos vs. horas para métodos exatos).
• Eficiência: O método de defesa adiciona um overhead computacional mínimo durante o treinamento e a inferência, com modelos treinados com DPD rodando ordens de magnitude mais rápido que resolvedores exatos não aprendíveis (ex: WS-DP).

Significância e Alegações
O artigo afirma que o framework proposto aborda uma lacuna crítica na literatura em relação à robustez de resolvedores neurais de MOCOP. Ao expor explicitamente as vulnerabilidades do resolvedor através do PAA e endereá-las sistematicamente via DPD, os autores demonstram que os resolvedores neurais podem se tornar significativamente mais robustos a mudanças de distribuição e variações de preferência. Os resultados sugerem que o treinamento adversário com seleção de preferência consciente de dificuldade é uma estratégia eficaz para aumentar a generalizabilidade de DRL para otimização combinatória, tornando esses resolvedores mais viáveis para aplicações do mundo real onde as distribuições de problemas são dinâmicas e complexas. Os autores concluem que seu trabalho estabelece as bases para extensões futuras para MOCOPs dinâmicos do mundo real e ambientes online.