Paper Link: https://arxiv.org/abs/1803.08475
Source Code (Official): https://github.com/wouterkool/attention-learn-to-route

Abstract

1. 조합최적화 문제를 풀 때 기존의 optimal solution을 구하는 과정이 아닌, heuristic을 사용하여 sub-optimal 하지만 computational cost 측면에서 이점을 가지는 solution을 찾고자 하는 아이디어가 제시됨.
2. 본 논문에서는 Pointer Network에서 사용된 attention 개념을 토대로 조합 최적화 문제를 풀기 위한 모델을 제시하고 REINFORCE 알고리즘을 사용해 학습 시키는 방법을 제시.
3. Travelling Salesman Problem (TSP), Vehicle Routing Problem (VRP), Orienteering Problem (OP), Prize Collecting TSP (PCTSP) 등 여러 routing 문제를 하나의 hyperparameter로 풀어서 제시한 모델의 generalizability를 강조.

What is Combinatorial Optimization (조합최적화)?

Definition: Process of searching for maxima (or minima) of an objective function F whose domain is discrete but large configuration space (as opposed to an N-dimensional continuous space)

쉽게 말하면 objective function을 최대화 하거나 loss function을 최소화하는 조합을 찾아내는 게 목적인 연구분야.

대표적으로 TSP가 있는데, traveling distance나 traveling time을 최소화 하면서 주어진 node들을 한번씩만 방문하고 출발지점으로 돌아오는 문제이다.

조합최적화에 접근하는 방법은 크게 두가지가 있는데, exact solution, 즉 optimal한 solution을 찾기 위한 방법이 있고, heuristic을 사용하여 sub-optimal하지만 computational cost 측면에서 이점을 가지는 solution을 찾기 위한 방법이 있다. 이 논문에서 제시한 방법론은 후자에 속하는 접근 방법으로, RL을 사용하였다.

저자는 조합최적화 문제로 분류되는 여러 routing 문제들을 풀기 위해 이 모델을 제시했는데, 이 모델을 설명하기 위해 TSP problem setting을 이용한다고 한다. 모델이 TSP 문제만을 풀 수 있는건 아니며, 문제 세팅마다 약간의 모델 수정이나 환경 세팅을 해줌으로써 다양한 routing 문제를 풀 수 있다고 한다.

Problem Setting

• Problem instance s as a fully-connected graph with n nodes, which are fully connected (including self-connections)
• Each node is represented by feature x_i which is coordinate of node i
• Solution is defined as a permutation of nodes π = (π₁,…,π_n) where π_t ≠ π_t’
• Stochastic policy for choosing next node p_θ(πㅣs) = ∏_t=1 p_θ(π_tㅣs,π_1:t-1)

Attention Model

• 이 논문에서는 예시로 TSP 문제를 위한 Attention Model을 정의한다. 다른 문제 세팅의 경우, Model은 같으나 input, mask, decoder context만 변형하여 사용하면 된다.
• Encoder produces embeddings of all input nodes.
• Decoder produces the sequence π of input nodes, one node at a time. Also, the decoder observes a mask to know which nodes have been visited.

Attention은 seq-to-seq 모델에 많이 쓰이는데, 한 문장을 다른 언어로 번역하는 예가 대표적이다. 즉 특정 단어를 output으로 내기 위해 어떤 input 단어들에 “집중” 할 것인지 결정하는 게 attention mechanism이라고 생각하면 될 것 같다.

Encoder

• Input은 각 노드의 좌표 (2-dimensional)
• Output은 여러 Multi-Head-Attention layer를 거친 embedding vector
• N개의 attention layer를 거치며 각 attention layer는 2개의 sub-layer로 이루어져 있다.
• 각 노드의 embedding과 더불어 노드들의 평균을 낸 aggregated embedding도 output으로 내줌. -> Context input to the decoder

각 Attention layer는 아래와 같이 구성

1. 일단 Raw Input이 MLP를 거치고 나면 128-dimensional Embedding이 만들어짐. (첫번째 초록색 화살표)
2. Embedding에 Weight matrix를 곱해서 (query, key, value) set을 만듬. Multi-Head Attention이라고 불리우는 이유는 좀 더 다양한 feature들을 고려하기 위해 (query, key, value) set을 생성할 때 dimension을 쪼개기 때문이다. 예를 들면 Single Head Attention으로 128x128 weight matrix를 사용해 128-dimensional vector로 project 해주는 대신에 8개의 16x128 weight matrix를 사용해서 16-dimensional vector 8개를 만들어 나중에 합친다. 여기서 W_Q와 W_K는 d_k x d_h의 크기를 가지고, W_V는 d_v x d_h의 크기를 가진다.

1. 기준이 되는 node의 query와 나머지 주변 node들의 key끼리 dot-product를 해줘서 compatibility를 계산. 예를 들면, 1번 노드에게 나머지 노드들이 얼마나 의미를 가지는가 하는 점수를 계산해주는 과정. 너무 멀리 떨어져 있는 node의 경우 아래와 같이 처리. 분모의 d_k 같은 경우 normalization 효과가 있다.

1. 계산된 compatibility에 softmax function을 씌워서 normalize 시켜준 값을 attention score로 씀.

1. 각 attention score는 각 노드의 value vector와 곱해져서 전부 더해짐.

1. Multi-Head Attention인 경우 위의 h’_i vector는 16x1의 크기를 가진다. 앞에서 말했듯이 이 같은 8개의 vector에 128x16 weight matrix를 곱해주어 모두 더해서 최종적으로 128x1 Embedding vector를 만들어 낸다.

위 과정이 하나의 Attention layer에서 일어나는 일이다.

Attention Layer를 통과하고 난 다음의 Feed-Forward Layer는 단순하게 ReLU와 Batch Normalization으로 이루어짐.

Decoder

• Inputs: Encoder Embeddings, Problem Specific Mask, Context (Embeddings for first and last node)
• The order and coordinates of other nodes already visited are irrelevant
• Decoder는 timestep 마다 encoder의 embedding과 해당 timestep 전에 방문한 모든 node들을 참고하여 다음 node인 π_t을 return 한다.
• Decoder는 context node (c)를 그래프 embedding과 같이 사용한다.
• Computational cost를 줄이기 context node에서의 message만 고려한다.
• Context node에는 graph embedding, 첫번째 노드 embedding, 마지막 노드 embedding을 포함한다.

• t = 1인 경우 첫번째 노드와 마지막 노드 대신에 학습된 v¹, v^f 사용.
• [.,.,.] operation은 horizontal concatenation으로 최종 context node는 3 x d_h dimension을 가짐.
• Decoder에서도 똑같이 context node를 query로 생각하고, 나머지 node embedding들을 key와 value로 생각해서 Multi-head Attention을 진행함.
• 다만 maximal efficiency를 위해 skip-connections, batch normalization, feed-forward layer는 사용하지 않음.

그래서 p_θ(π_tㅣs,π_1:t-1)는 어떻게 구할건데?

• Decoder에서 나온 결과에 마지막 single attention head layer를 추가. 여기서 C = 10.

• 여기서 가장 높은 p 값을 가진 node가 다음 노드가 되고, masking된다.

REINFORCE with Greedy Rollout Baseline

• b(s) is the cost of a solution from a deterministic greedy rollout of the policy defined by the best model so far.
• Baseline의 목적은 instance s의 difficulty를 측정하는 데에 있음.
• Harder the instance, higher the cost.
• When performing the rollout, the solution is obtained with a greedy policy with maximum probability.
• Freeze greedy rollout policy for every epoch (similar to freezing of the target Q-network)
• The rollout policy is replaced with the current training policy if the improvement is significant according to a paired t-test (alpha = 5%).
• The t-test is done on 10000 separate evalauation instance