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

기술 요약: 다중 목적 신경 조합 최적화를 위한 적대적 인스턴스 생성 및 강건한 학습

문제 정의
심층 강화 학습(DRL)은 전통적인 정밀 알고리즘 및 휴리스틱 알고리즘에 비해 우수한 효율성을 제공하며, 다중 목적 조합 최적화 문제(MOCOPs)를 해결하기 위한 유망한 접근 방식으로 부상했습니다. 그러나 이러한 DRL 솔버의 강건성(robustness)은 여전히 충분히 탐구되지 않았으며, 특히 다양하고 복잡한 문제 분포에 대한 성능 측면에서 그러합니다. 단일 목적 문제에 대한 기존 연구들은 DRL 모델이 특정 분포적 단서에 과적합되는 "지름길 학습(shortcut learning)"을 겪을 수 있으며, 분포 외(out-of-distribution, OOD) 인스턴스에서 실패할 수 있음을 시사합니다. 상충하는 여러 목적 사이의 균형을 맞추는 파레토 프런트(Pareto front)를 근사하는 것을 목표로 하는 MOCOP의 맥락에서, 신경 솔버의 분포 변화에 대한 취약성과 체계적인 강건성 평가의 부재는 실질적인 배포에 있어 중요한 도전 과제가 됩니다.

방법론
저자들은 두 가지 핵심 구성 요소인 **선호도 기반 적대적 공격(Preference-based Adversarial Attack, PAA)**과 **동적 선호도 증강 방어(Dynamic Preference-augmented Defense, DPD)**로 구성된 통합 프레임워크를 제안합니다.

1. 선호도 기반 적대적 공격 (PAA):

   • 목적: 특정 선호 조건 하에서 DRL 솔버의 성능을 구체적으로 저하시키는 "어려운(hard)" 인스턴스를 생성합니다.
   • 메커니즘: 이 방법은 문제 입력(예: TSP의 노드 좌표)을 학습 가능한 변수로 취급합니다. 대상 솔버의 강화 손실 $\ell(x; \theta)$를 최대화하기 위해 그래디언트 상승법(gradient ascent)을 통해 입력 $x$를 반복적으로 업데이트합니다.
   • 손실 함수: 손실은 기준값으로 나눈 정규화된 서브문제 손실 $L(\pi|x)$를 솔루션의 로그 확률에 곱한 것으로 정의됩니다. 이를 최대화함으로써, 공격은 솔버가 특정 선호 벡터 $\lambda$에 대해 낮은 파레토 프런트 품질(Hypervolume, HV로 측정)을 가진 솔루션을 생성하도록 강제합니다.
   • 결과: 이 과정은 다양한 선호도에 맞춤화된 적대적 인스턴스 풀을 생성하며, 결과적으로 생성된 파레토 프런트의 품질을 효과적으로 낮춥니다.

2. 동적 선호도 증강 방어 (DPD):

   • 목적: 적대적 학습을 통해 신경 솔버의 일반화 능력과 강건성을 향상시킵니다.
   • 메커니즘: DPD는 깨끗한(clean) 인스턴스와 사전 생성된 적대적 풀의 혼합체에 대해 미세 조정(fine-tuning)을 수행합니다.
   • 난이도 인식 선호도 선택 (Hardness-Aware Preference Selection): 학습 중에 각 샘플링된 인스턴스와 선호도 $\lambda$에 대해, 작은 무작위 섭동을 적용하여 국소적으로 증강된 선호도 집합 $\{\lambda'_i\}$를 생성합니다. 모델 파라미터를 고정한 상태에서 증강된 선호도 하에서 생성된 솔루션의 체비셰프(Tchebycheff) 값을 평가하고, 가장 최악의 솔루션 품질(가장 높은 체비셰프 값)을 산출하는 선호도 $\lambda'_{adv}$를 선택합니다.
   • 학습: 솔버는 미니 배치 내의 이 "가장 어려운" 증강된 선호도에 대해 스칼라화된 손실(scalarized loss)을 최소화하도록 업데이트됩니다. 이 전략은 제한된 선호 영역에 대한 과적합을 방지하고, 모델이 선호 공간 전반에 걸쳐 강건한 표현을 학습하도록 강제하는 것을 목표로 합니다.

주요 기여

• PAA 방법: 특정 선호도를 타겟팅하여 MOCOP을 위한 어려운 인스턴스를 체계적으로 생성하는 방법을 도입하였으며, 이를 통해 신경 솔버가 서브문제의 약점에 맞춰진 분포 변화에 의해 크게 저하될 수 있음을 입증했습니다.
• DPD 방법: 난이도 인식 선호도 선택을 적대적 학습에 통합하는 방어 전략을 제안했습니다. 이 접근 방식은 기본 모델 아키텍처의 변경 없이도 과적합을 완화하고 분포 외(OOD) 성능을 개선합니다.
• 포괄적 평가: 이 프레임워크는 세 가지 고전적인 MOCOP인 다중 목적 순회 외판원 문제(MOTSP), 다중 목적 용량 제한 차량 경로 문제(MOCVRP), 다중 목적 배낭 문제(MOKP)에 대해 검증되었습니다.

실험 결과

• 공격 효능: PAA 방법은 깨끗한 인스턴스 및 기타 분포 섭동(log-normal, beta, gamma)과 비교했을 때, 경쟁력 있는 신경 솔버(EMNH, PMOCO, CNH)가 생성한 솔루션의 하이퍼볼륨(HV)을 유의미하게 감소시키는 어려운 인스턴스를 성공적으로 생성했습니다. 여러 경우에서 PAA는 ROCO-RL과 같은 기존의 학습 기반 공격 방법보다 뛰어난 성능을 보였습니다.
• 방어 성능: DPD로 학습된 모델(예: PMOCO-DPD, CNH-DPD, EMNH-DPD)은 강건성 측면에서 일관된 개선을 보여주었습니다.
  • 가우시안(Gaussian) OOD 인스턴스에서, DPD가 강화된 솔버는 방어되지 않은 대응 모델에 비해 더 낮은 최적성 격차(optimality gaps)를 달しまいました.
  • 특히, Bi-CVRP100에서 WE-CA-DPD 모델은 WS-LKH 베이스라인 대비 HV를 2.23% 개선하였으며, 이는 관찰된 가장 큰 향상 폭입니다.
  • DPD 모델은 더 큰 규모의 인스턴스(최대 200개 노드)와 다양한 벤치마크 인스턴스(kroAB100 등)에서도 강력한 성능을 유지하였으며, 종종 정밀 솔버(exact solvers)의 성능에 근접하면서도 훨씬 짧은 추론 시간(정밀 방법의 경우 몇 시간 vs. 몇 초)을 유지했습니다.
• 효율성: 방어 방법은 학습 및 추론 과정에서 최소한의 계산 오버헤드만을 추가하며, DPD로 학습된 모델은 비학습형 정밀 솔버(예: WS-DP)보다 수십 배 더 빠르게 실행됩니다.

의의 및 주장
본 논문은 제안된 프레임워크가 신경 MOCOP 솔버의 강건성에 관한 문헌의 결정적인 공백을 메운다고 주장합니다. PAA를 통해 솔버의 취약성을 명시적으로 드러내고 DPD를 통해 이를 체계적으로 해결함으로써, 저자들은 신경 솔버가 분포 변화 및 선호도 변화에 대해 훨씬 더 강건해질 수 있음을 입증했습니다. 결과는 난이도 인식 선호도 선택을 포함한 적대적 학습이 DRL 기반 조합 최적화의 일반화 능력을 향상시키는 효과적인 전략임을 시사하며, 이는 문제 분포가 동적이고 복잡한 실제 응용 분야에서 이러한 솔버들을 더욱 실용적으로 만듭니다. 저자들은 본 연구가 향-동적인 실제 환경의 MOCOP으로의 확장을 위한 토대를 마련했다고 결론짓습니다.