Neural Combinatorial Optimization With Reinforcement Learning

0. Abstract

이 논문은 Deep RL로 CO문제를 푸는 framework를 제안한다.

1. Introduction

CO는 CS의 근본적인 문제로 이들은 다양한 분야에서 적용된다.

TSP 해 찾기는 NP-hard이다.

Heuristic work등이 있지만, condition의 변화에 적용이 불가능해진다.

반대로 ML은 heuristic을 training data에서 자동으로 찾기 때문에 다양한 condition에 적용될 수 있다.

지도학습의 label에 대한 요구로 인해 대부분의 CO에 적용되기 어렵다.

우리는 SL보다 RL이 generalization이 더 좋음을 실험적으로 보인다.

1. Policy gradient approach
   • Policy is parameterized by RNN
   • At test time, inference by greedy sampling
2. Active search
   • Search 동안의 좋은 solution들을 유지하면서 최적화??
3. 혼합

NCO는 pointer network의 지도학습 방법보다 더 낫다.

2. Previous work

TSP를 근사적으로 푸는 heuristic들이 있었다.

이보다 더 일반적인 문제인 Google’s vehicle routing problem도 있다.

No Free Lunch theorem : 다양한 search 알고리즘들은 모든 문제를 고려하게 될 경우 거기서 거기다.

결국 사전 지식에 기반해서 문제 상황에 적절한 것을 골라야 한다.

---

최근 Pointer Network가 뉴럴넷 기반으로 이 문제를 다뤘다.

3. Neural Network Architecture For TSP

• $n$ : number of cities
• $s={\left\{{\mathbf{x}}_i\right\}}_{i=1}^n$ where ${\mathbf{x}}_i\in {\mathbb{R}}^2$
• $\pi \in \pi (s)$ : permutation of $s$
• $L(\pi \mid s)={|{\mathbf{x}}_{\pi (n)}-{\mathbf{x}}_{\pi (1)}|}_2+\sum _{i=1}^{n-1}{|{\mathbf{x}}_{\pi (i)}-{\mathbf{x}}_{\pi (i+1)}|}_2$
• $p(\pi \mid s)=\prod _{i=1}^{n}p(\pi (i)\mid \pi (<i),s)$

Vanilla sequence to sequence 문제는 output dictionary size가 고정되어 있다.

다양한 $n$에 적용하기 위해, pointer network approach를 적용하였다.

3.1 Architecture details

4. Optimization with Policy Gradient

Let $\theta$ be the parameters of PtrNet.

$$\begin{array}{rl}J(\mathit{\theta }\mid s)& ={\mathbb{E}}_{\pi \sim p_{\theta }(.\mid s)}L(\pi \mid s)\\ J(\mathit{\theta })& ={\mathbb{E}}_{s\sim \mathcal{S}}J(\mathit{\theta }\mid s)\\ {\mathrm{\nabla }}_{\theta }J(\theta \mid s)& ={\mathbb{E}}_{\pi \sim p_{\theta }(\cdot \mid s)}[(L(\pi \mid s)-b(s)){\mathrm{\nabla }}_{\theta }\log p_{\theta }(\pi \mid s)]\\ {\mathrm{\nabla }}_{\theta }J(\theta )& \approx \frac{1}{B}\sum _{i=1}^B(L({\pi }_i\mid s_i)-b\left(s_i\right)){\mathrm{\nabla }}_{\theta }\log p_{\theta }({\pi }_i\mid s_i)\end{array}$$

where $b(s)$ is a baseline function.

Let ${\theta }_v$ be the parameter of critic network.

$$\mathcal{L}\left({\theta }_v\right)=\frac{1}{B}\sum _{i=1}^B{\Vert b_{{\theta }_v}\left(s_i\right)-L({\pi }_i\mid s_i)\Vert }_2^2$$

4.1 Search Strategies

• Sampling
  1. $s\sim S_{train}$
  2. $\{{\pi }_i\}\sim p_{\theta }(\cdot \mid s)$ for $i=1,\dots ,n_{\pi }$
  3. Evaluate $L_i=L(\pi \mid s)$
  4. ${\pi }^{\star }=max{L}_i$
  5. Policy Gradient
  6. repeat 1 until convergence
  7. Greedy in test phase
• Active Search
  1. $s\sim S_{test}$
  2. Policy Gradient
  3. repeat 2 until convergence
  4. Greedy

5. Experiments