Attention, Learn to Solve Routing Problems! 리뷰

Updated on Apr 18th, 2025.


Traveling Salesman Problem(TSP) 혹은 Vehicle Routing Problem(VRP)와 같은 조합 최적화를 위한 딥러닝(흔히 Neural Combinatorial Optimization, NCO 라고 합니다.)을 공부한다면 무조건 알아야 하는 논문 1순위. 후속 논문들이 진짜 이 논문에서 소개하는 구조의 변형인 경우가 너~무 많음. 그렇기 때문에 이 논문만큼은 깔끔하게 알아야 한다고 생각합니다. 이러한 이유로 COSOM Blog 첫 논문 리뷰는 본 논문으로 시작하겠습니다.

주의! : 아래 키워드, 논문, 지식은 있다는 가정 하에 작성되었습니다. 이들은 본 포스팅을 이해하기 위한 필수 요소입니다.

Prerequisite


Intruduction

본 논문에서 목표로 삼은 것은 조합 최적화, 특히 Vehicle Routing Problem(VRP)에서 효율적으로 최적에 가까운 근사해를 찾는 것입니다. Vehicle Routing Problem을 직역하면 차량 경로 문제인데, 종류가 굉장히 많다만 공통적으로 추구하는 것은 모든 곳을 방문하는 최단 길이 사이클을 찾는 것입니다. 본 논문에서는 다양한 종류의 VRP를 풀지만 편의상 VRP의 가장 간단한 버전인 Traveling Salesman Problem(TSP)을 기준으로 설명하겠습니다. TSP는 $n$개의 점이 있으면 이 $n$개의 점을 모두 한바퀴 돌아오는 경로를 찾는 문제입니다. 이 문제는 최적해를 찾기 위해 모든 경우의 수를 다 하나하나 확인해야 한다는 점에서 매우 어렵습니다. $n$개의 조합 경우의 수를 모두 고려해야 하기 때문에 하나하나 경우의 수를 따져 보면 $n!$의 경우의 수가 있습니다.

이러한 복잡도 때문에 이 문제를 해결하는 전통적인 접근법은 크게 두 가지가 있습니다.

  1. 정확한 해를 얻는 대신 시간이 매우 오래 걸린다.
  2. 빠르게 해를 찾는 대신 최적해로부터 멀다.

1.의 경우, Linear Programming을 이용한 OR솔버를 이용하고, 2.의 경우 휴리스틱 알고리즘을 사용합니다. 자, 그렇다면 본 논문의 기여점은 무엇일까요?

본 논문은 뉴럴 네트워크를 통해 1과 2의 중간쯤 되는 모델을 만듭니다. 적당히 빠른 속도 내에 적당한 해를 찾는 성과를 보였습니다. 사실 이전에도 관련 연구가 몇가지 있었습니다. LSTM이나 Pointer Network(Attention Mechanism이라 간주해도 괜찮을듯.)등으로 지도학습 강화학습 등을 시도했는데 생각보다 성과가 좋진 않았습니다. 제 생각에 이 논문은 어느정도 성능이 나오는 조합 최적화 뉴럴 네트워크 모델을 학습했다는 점에서 의의가 있어 보여요!


Attention Model

이 챕터는 본 논문에서 제시하는 뉴럴 네트워크 구조를 설명합니다. 이름을 Attention Model이라 지었는데, 여기서 말하는 Attention은 Self Attention, Multi-head Attention을 의미하고 사실상 Transformer 구조라 생각하면 될 것 같습니다.

모델을 디자인하기 전에, 입출력 구조부터 알아보겠습니다. TSP는 방문 순서를 찾아내는 문제입니다. 문제 상황(즉, 방문할 장소의 위치)이 입력되면 최종적으로 방문할 장소들의 순서를 출력해야겠죠. 그러나, 이는 다소 복잡합니다. 그렇기에 문제를 단순화하기 위해 아래처럼 재구성합니다.

\[p_{\theta}(\pi|s) = \prod_{t=1}^{n} p_{\theta}(\pi_t\mid s, \pi_{1:t-1})\]

문제 상황을 $s$라고 가정합니다. 논문에서는 그래프로 설명하는데 저는 $s \in R^{n \times 2}$ 의 위치 벡터, 혹은 노드라 생각합니다. 이때, 방문 순서 $\pi$ 는 각 시퀀스의 원소 하나씩 따로 계산될 수 있다고 가정합니다. 그러면 $p_{\theta}(\pi_t\mid s, \pi_{1:t-1})$ 수식이 $t$ 번째 방문 순서는 $1:t-1$ 번째 방문 순서와 문제 상황 $s$ 의 조건부 확률이 될 수 있는거죠. 이때, $p_\theta$ 가 정책 확률식을 뉴럴 네트워크로 근사한 확률이 되겠습니다. 결국, 뉴럴 네트워크 모델은 문제 상황과 직전까지의 경로가 주어지면 그 다음 경로를 예측하는 다중 분류 모델이네요 ! 이를 반복적으로 적용하여 시퀀스를 예측합니다.

Encoder

모델의 입출력을 알아보았고, 이제 Encoder를 디자인해보겠습니다. Encoder의 목적은 방문할 노드들의 특성을 담은 벡터를 출력하는 것입니다. 그렇기에 일단은 노드의 위치 벡터만 입력으로 쓰면 되겠네요. 첫 레이어는 그냥 선형층을 사용하여 임베딩을 해줍니다.

\[h_{i}^{(0)} = W^{x}x_{i} + b^{x}\]

이때, $x^{i}$는 각 노드의 위치 벡터이고, $W^{x}$와 $b^{x}$는 단순한 선형층 레이어입니다. 이후 임베딩된 새 벡터 $h_{i}^{(0)}$ 은 Transformer Encoder 레이어에 그대로 입력됩니다. 언어 이런게 아니므로 Position Encoding과 같은 처리는 사용하지 않습니다.

\[\hat{h}_{i} = \text{BN}^{\ell} \Big( h_{i}^{(\ell-1)} + \text{MHA}_{i}^{\ell} \big( h_{1}^{(\ell-1)}, \dots, h_{n}^{(\ell-1)} \big) \Big)\] \[\mathbf{h}_{i}^{(\ell)} = \text{BN}^{\ell} \left( \hat{\mathbf{h}}_{i} + \text{FF}^{\ell} (\hat{\mathbf{h}}_{i}) \right).\]

정말 Transformer와 똑같이 BN(Batch Normalization), MHA(Multi-head Attention), FF(Feed Forward)를 사용합니다. 이렇게 위치의 특성을 나타내는 벡터를 얻었습니다.

참고로, 논문에서 사용한 파라미터는 노드 임베딩 128차원, Attention-head 8개, Feed Forward 512차원입니다.

Decoder

이제 Decoder에서는 본격적으로 시퀀스를 예측합니다. 시퀀스가 주어지면 다음 시퀀스의 확률을 예측합니다. 이 Decoder는 논문에서 Attention Decoder라고 소개를 하긴 하는데.. 저는 Attention보다는 유사도 측정과 비슷한 방식으로 느껴졌습니다. 제가 이렇게 느낀 이유는 본 논문의 Decoder는 Self-Attention이 아닐 뿐더러, Attention Score까지만 사용되기 때문입니다. 편한대로 이해하면 좋을 것 같고 어쨌거나 Decoder 구조를 알아보도록 하겠습니다.

시퀀스를 예측하기 위해 먼저 query를 형성합니다. 예측을 하기 위한 현재 진행상황을 나타내는 값이라 생각하면 좋을 것 같습니다.

\[h_{(c)}^{(N)}= \begin{cases} \left[ \bar{h}^{(N)}, h_{\pi-1}^{(N)}, h_{1}^{(N)}\right] & t > 1 \\ \left[ \bar{h}^{(N)}, v^{1}, v^{f}\right] & \text{otherwise.} \end{cases}\]

query는 $h_{(c)}^{(N)}$ 3차원의 벡터를 기반으로 만들어집니다. 이 벡터는 세가지의 정보를 담고 있습니다.

  1. $\bar{h}^{(N)}$ : 모든 임베딩 벡터들의 평균값.
  2. $h_{\pi-1}^{(N)}, v^{1}$ : 가장 마지막으로 방문한 노드, 즉 현재 시퀀스의 마지막. 첫 시퀀스인 경우 임의로 설정한 첫 노드.
  3. $h_{1}^{(N)}, v^{f}$ : 가장 처음에 방문한 노드, 되돌아와야 하는 노드. 첫 시퀀스인 경우 임의로 설정한 마지막 노드(TSP의 경우 $v^{1} = v^{f}$.).

1.은 전체 노드 정보를 담기 위해, 2.는 다음 노드와 가까운 노드를 예측하기 위해, 3.은 최적해를 찾기 위해 설정한 값인 것 같습니다. 어쨌거나 이렇게 저 벡터들을 쭉 붙여 $3 \times d_{h}$ 크기의 벡터를 하나 완성했습니다. 이제 query로 사용할 벡터도 만들었겠다, 바로 확률을 예측해보겠습니다.

\[q_{(c)} = W^{Q} h_{(c)}^{(N)} \quad k_{i} = W^{K} h_{i}^{(N)}, \quad v_{i} = W^{V} h_{i}^{(N)}\]

이렇게 검색을 위한 $q_{(c)}$, 그리고 검색 대상인 $k_{i}$를 형성하였습니다. $k_{i}$를 계산할때 쓰는 $h_{i}^{(N)}$는 아까 Encoder에서 출력된 임베딩 벡터입니다.

이때, 확률값은 아래처럼 나타낼 수 있습니다.

\[u_{(c)j} = \begin{cases} C \cdot \tanh\left( \frac{q_{(c)}^T k_j}{\sqrt{d_k}} \right) & \text{if } j \neq \pi_{t'} \quad \forall t' < t \\ -\infty & \text{otherwise.} \end{cases}\]

이전에 이미 지난 시퀀스는 $-\infty$로 처리하면서 조합 시퀀스를 찾아야 한다는 constraint를 만족시켜줍니다. 계산식은 Attention Score 측정 방식인 Scaled Dot-Producted Attention 이네요. 저는 단순히 $q_{(c)}, k_{i}$의 유사도를 비교한다! 라고 생각합니다.

\[p_i = p_{\theta}(\pi_t = i | s, \pi_{1:t-1}) = \frac{e^{u(c)i}}{\sum_j e^{u(c)j}}.\]

마지막으로 이 score 값에 softmax 함수를 씌워주면서 다음 방문 노드의 확률값을 예측할 수 있습니다.


REINFORCE with Greedy Rollout Baseline

REINFORCE 알고리즘을 적용하기 위해 보상의 누적 합을 근사해야 합니다. 본 논문에서는 DQN이나 Actor-Critic같이 보상의 누적 합을 예측하는 방법을 사용하지 않으면서 보상의 누적 합을 근사하는 아이디어를 제시합니다. 아이디어는 간단합니다. 바로 정책을 Sampling하여 근사합니다. 핵심 아이디어는 분산을 줄이기 위한 baseline function 설정에 있는데요, 단순히 정책을 Greedy로 시행한 보상을 사용합니다. 이게 왜 잘 작동하는지는 명확히 설명하긴 어렵다만, 추측건대 상태함수를 정의하는게 어렵지 않았나 생각합니다. 또한 명확한 최적해가 알 수는 없지만 이미 정해져있는 와중에 가치를 예측하는 의미가 적지않나? 싶기도 해요.

어쨌거나, 정책의 반복 시행을 통한 samling한 보상을 정책 1번 시행한 값과의 차이만큼 Gradient를 가하면서 학습을 한다는게 키 포인트가 됩니다!


Experiments

실험은 아래와 같은 조건으로 진행되었습니다.

Parameter Value
train data 1280000
test data 10000
batch 2500
batch size 512
Encoder Layer 3
Optimizer Adam
learning rate 1e-4

이렇게 했더니 아래와 같은 실험 결과를 얻었다고 합니다.

Method Type TSP20 TSP50 TSP100
Concorde Exact Solver 3.84 (1m) 5.70 (2m) 7.76 (3m)
LKH3 Heuristic 3.84 (18s) 5.70 (5m) 7.76 (21m)
Random Insertion Heuristic 4.00 (0s) 6.13 (1s) 8.52 (3s)
AM greedy (ours) RL 3.85 (0s) 5.80 (2s) 8.12 (6s)
AM sampling (ours) RL 3.84 (5m) 5.73 (24m) 7.94 (1h)

AM greedy을 보면 빠르면서도 최적해에 많이 가까운 결과를 얻은걸 알 수 있습니다.


Comment

조합 최적화를 위한 강화학습의 근간이 되는 논문. 위에서도 언급했다만 후속 연구들의 대부분이 이 논문을 기반으로 하기 떄문에 구현할 때 있어서 많이 참조하게 됩니다. 세 자리수의 TSP는 모두 이 모델을 기반으로 한다해도 과언이 아닙니다. 최근 연구는 large-scale TSP에 집중되어 있어 본 논문의 중요도가 약간은 줄어들었으나, 그래도 기초가 된다는건 변하지 않습니다. 아이디어 외에 설명이나 논문 구조 등 다른 요소들을 봐도 정말 잘 쓰여진 논문이기 때문에 깊게 읽어보시는걸 적극 추천드려요 !