획기적인 발견! 신경망 기반 TSP 솔버의 일반화 문제 해결의 실마리, '순도 법칙'

중국 연구팀이 여행 세일즈맨 문제(TSP)의 일반화 문제를 해결할 새로운 원리인 '순도 법칙(PuLa)'과 이를 기반으로 한 훈련 패러다임 'PUPO'를 발표했습니다. PuLa는 최적 솔루션의 구조적 원리를 규명하고, PUPO는 기존 신경망 솔버의 일반화 성능을 크게 향상시킵니다.

여행 세일즈맨 문제(TSP)는 여러 도시를 방문하여 최단 경로를 찾는 문제로, 인공지능 분야에서 난공불락의 과제 중 하나였습니다. 특히, 다양한 규모와 분포의 문제 인스턴스에 걸쳐 일반화된 해결책을 제시하는 것은 신경망 기반 접근 방식의 큰 어려움이었습니다. 왜냐하면 신경망은 종종 보편적인 패턴을 식별하고 다양한 인스턴스에서 최적의 해를 도출하는 강력한 원리를 학습하는 데 실패하기 때문입니다.

하지만 최근, Wenzhao Liu 등 중국 연구팀은 이러한 어려움을 극복할 획기적인 발견을 발표했습니다. 바로 '순도 법칙(Purity Law, PuLa)' 입니다. PuLa는 최적의 TSP 솔루션에 대한 기본적인 구조적 원리를 밝혀낸 것으로, **'엣지의 출현 빈도가 주변 정점의 희소성에 따라 기하급수적으로 증가한다'**는 것을 규명했습니다. 다양한 인스턴스에 걸쳐 통계적으로 검증된 PuLa는 최적해에서 지역적 희소성에 대한 일관된 편향을 보여줍니다.

이러한 통찰력을 바탕으로 연구팀은 '순도 정책 최적화(Purity Policy Optimization, PUPO)' 라는 새로운 훈련 패러다임을 제시했습니다. PUPO는 신경망 솔루션의 특징을 PuLa와 명시적으로 정렬하여 해결책을 구성하는 과정에서 일반화 성능을 향상시키는 방법입니다. 광범위한 실험 결과, PUPO는 기존의 인기 있는 신경망 솔버와 원활하게 통합될 수 있으며, 추론 중에 추가적인 계산 오버헤드 없이 일반화 성능을 크게 향상시키는 것으로 나타났습니다.

이번 연구는 TSP 문제 해결에 있어 획기적인 전기를 마련했습니다. PuLa와 PUPO는 단순히 TSP 문제에만 국한되지 않고, 다른 최적화 문제에도 적용 가능한 잠재력을 가지고 있습니다. 앞으로 PuLa와 PUPO를 기반으로 한 다양한 연구가 진행될 것으로 예상되며, 이는 인공지능의 발전에 크게 기여할 것으로 기대됩니다. 특히, 추가적인 연산 부담 없이 일반화 성능을 향상시킨 점은 실제 응용 분야에서 큰 장점으로 작용할 것입니다.

연구팀: Wenzhao Liu, Haoran Li, Congying Han, Zicheng Zhang, Anqi Li, Tiande Guo