[Essay] Deep learning으로 조합 문제를 풀 수 있을까? - Neural Combinatorial Optimization

소개글

축구 리그 시즌에 감독은 로테이션을 돌려서 선수들을 경기에 내보내야 합니다. 많은 후보 선수들 중에서 어떤 선수를 내보낼지 결정하는 것은 그 선수가 가진 능력뿐만 아니라 상대팀에 대한 분석, 경기 일정 등 다양한 조건들이 추가됩니다. 예를 들어, 이틀 연속으로 경기가 있다면 한 선수를 90분 풀타임, 2경기 모두 출전시키는 것은 좋지 않은 선택이겠죠. 이러한 선택의 순간은 일상에서도 다양하게 존재하며 사람들은 최대한 괜찮은 선택을 하고자 합니다.

 

축구 경기보다 조금더 일상적인 문제로 접근해보겠습니다.

 

서울역에서 출발해서, [여수, 부산, 울산, 속초, 강릉, 대구, 대전]을 한 번씩 들리고 다시 서울로 돌아오는 경로를 짜고자 한다면, 어떻게 짜는 게 가장 최단거리일까요?

 

이 문제를 풀기 위해서 두 가지 접근법을 생각할 수 있습니다.

 

1. 서울에서 일단 가까운 곳을 방문하고, 다시 가까운 곳을 방문한다. (서울→대전 → 가까운곳)
2. 모든 경우의 길이를 다 센다. (서울-부산-울산-속초-강릉-대구-대전-여수-서울, 서울-울산-...)

 

이러한 Optimization 문제는 기존에 고전적인 방법들로 정확한 해를 찾을 수 있습니다. 그러나 변수와 조건이 늘어날수록 시간이 오래 걸리며, Meta-Heuristic 을 이용하면 시간을 단축시키나 성능이 떨어집니다. 저는  신경망에 이처럼 경우의 수에 대한 정보를 저장해둘 수 있는지의 여부가 궁금했습니다.

 

Traveling Salesman Problem

 

Traveling Salesman Problem (TSP) and  Prize Collecting TSP(PCTSP)

 

TSP문제는 Graph에서 모든 점을 방문하면서 최단거리로 이동하는 경로를 찾는 문제입니다. Prize Collecting TSP는 모든 점을 방문할 필요는 없습니다. 대신 각 위치에 대해서 보상(Prize)가 있고 만일 노드를 방문하지 않는다면 패널티(Penalty)가 존재합니다. 투어 길이 + 패널티를 최소화하면서 전체 Prize를 최대화하는 문제입니다. 앞으로 소개할 논문들에서 이 문제들을 신경망으로 풀었습니다. 

 

Neural Combinatorial Optimization

최근 발달된 딥러닝과 AI의 발달로 새롭게 부상하고 있는 영역입니다. Optimzation에 대한 계산을 신경망으로 대체하는 방법입니다. 1985년 Hopfield-network를 활용해서 Optimization문제를 접근한 것을 기반으로, 2015년에는 Pointer Network를 이용해서 노드에 대한 순차적인 선택을 하였습니다. 이 논문에서는 점들에 대한 위치와 정답 레이블에 대한 데이터 Pair를 줌으로써 학습시켰습니다. 따라서 Supervised Learning으로 학습시켰습니다.

 

 

 

 

이와 다르게 2016년에 Neural Combinatorial Optimization with RL에서는 동일한 모델로 정답레이블을 주는 대신 강화학습으로 Loss를 설정함으로써 걸리는 시간을 줄이는 방향으로 학습했습니다.

 

개인적인 생각으로, 학습의 안정성 측면에서는 Supervised Learning이 낫지만, 어려운 문제라면 해를 구하는 것조차 어렵기 때문에 장기적으로는 RL 방식을 선호하게 될 것 같습니다.

 

 

이후 2018년의 Attention, Learn to Solve Routing Problems에서는 추가적으로 Decoder에서 이미 선택한 노드에 대해서는 Masking을 하는 방식으로, TSP 문제를 풀었습니다.

 

 

그래서..

문제에 대해서 최적의 해를 찾는 것은 중요합니다. 그러나 빠른 판단을 내려야 하는 순간에 중요한 것은 짧은 시간에 괜찮은 수준의 해를 찾는 것 입니다. 컴퓨터는 해를 찾기 위해서 일일이 코딩을 해야 하지만, 사람은 대충 찍어서라도 비슷한 해를 찾을 순 있습니다. 비록 정답와 오차가 존재하지만요. Neural Combinatorial Optimization (NCO)는 이러한 특징을 잘 가지고 있는 분야인 것 같습니다. 아직 많은 연구가 활발히 진행되지는 않지만, 해를 찾는게 주요 목적인 많은 곳에서 학습된 모델로 빠르게 적절한 해를 찾을 수 있다면 많은 곳에서 쓰일 수 있을 것 같습니다.

 

References

[1] Pointer Networks, Vinyals, et al.,
    (https://arxiv.org/abs/1506.03134)

[2] Attention, Learn to Solve Routing Problems!, Kool et al.,
    (https://arxiv.org/abs/1803.08475)

[3] Neural Combinatorial Optimization with Reinforcement Learning, Bello et al.,
    (https://arxiv.org/abs/1611.09940)