[GNN] A graph neural network assisted monte carlo tree search approach to traveling salesman problem(2020)

 

[GNN] A grap neural network assisted monted carlo tree search approach to traveling salesman problem(2020)

 

요약 : GNN을 이용하여 tsp graph의 사전확률을 구하고 이를 monte carlo tree search에 적용한 결과 다른 learning-based algorithm보다 좋은 성능을 내었다.

 

1. Introduction

Deep convolutional neural netowrks(CNN)과 Monte Carlo Tree Search(MCTS)의 조합은 그 유명한 AlphaGo를 탄생시킨 알고리즘이다. 그러나 바둑에 적용된 알고리즘을 TSP에 그대로 적용하는 것은 부적절하다. 그 이유는 다음과 같다.

 

첫째, 바둑은 2D이미지로 쉽게 표현가능 하지만 TSP를 grid상에 표현하는 것은 어렵다.

 

둘째, TSP는 NP-hard이기에 이를 효율적이고 정확하게 풀어내는 heuristic은 없다.

 

셋째, AlphaGo는 branch를 따라가며 average winning rate를 높이면 되지만 TSP는 '최단거리'라는 exact path가 필요하다.

 

비록 알파고 알고리즘을 TSP에 바로 적용하기엔 무리가 있지만 AlphaGo의 영향으로 많은 연구자들이 combinational optimization problem 문제를 풀기 위해 classical heuristic search algorithm에 neural network를 이용하는 방법론을 연구하고 있다. 본 논문 역시 이러한 연구의 일환으로 Graph Neural Network(GNN)를 mote-carlo tree search에 활용하고자한다.

 

2. Background - Monte Carlo Tree Search

대표사진 삭제

사진 설명을 입력하세요.

Monte Carlo Tree Search(MCTS) algorithm의 4step은 다음과 같다.

 

1. Selection

: leaf node를 찾아가는 selection step이다. 이때 새로운 경로를 찾는 exploration과 이전 경로탐색에서 이득을 보았던 경로를 다시 방분하는 exploitation 간에 balance가 유지되어야한다. 만일 exploration에 가중치를 둔다면 탐색에 비효율성이 발생할 수 있고 exploitation에 가중치를 둔다면 local optimum에 빠질 가능성이 높다.

 

2. Expansion

: selection을 통해 leaf node에 도달하면 해당 상태는 GNN에 의해 평가되어 leaf node의 children nodes의 사전확률 p를 구한다.

 

3. Simulation

시뮬레이션을 통하여 해당 새로 생긴 leaf node의 state 업데이트

 

4. Backpropagation

Paraent의 node의 방문횟수를 1씩 update하고 simulation을 기반으로 업데이트된 node의 state에 따라 paraent nodedml state를 업데이트한다.

 

3. Algorithm

대표사진 삭제

사진 설명을 입력하세요.

MCTS with GNN

 

1. Selection Strategy

exploration과 exploitation의 balance를 맞추기위하여 PUCT함수 사용

 

대표사진 삭제

N(s,a) 노드 s에 방문한 횟수, P(s,a) edge s를 선택할 확률, Cpuct : 상수

대표사진 삭제

action value와 U(s,a)가 최대가 되게하는 a값

2. Expansion Strategy

leaf node에 도달했을때 GNN을 이용하여 leaf node의 children node의 사전확률 p를 구한다.

 

3. Simulation Strategy

leaf node까지의 length of tour를 이용하여 얻은 value fuction h(s)를 이용하여 simulation 결과 도출

 

4. Back-Propagation Strategy

t < l 인 모든 step에 대하여 edge statistic이 backward process에 의해 업데이트 된다.

Visit count : N = N+1

Action Value : Q = max(Q,Vl)

실험결과	1. Optimality gap   GNN-MCTS model을 TSP100으로 training 후 tsp200, 300, 500문제에 적용시 다른 algorithm보다 optimality gap이 낮음, TSP500으로 training시 TSP1000의 해를 찾아냄. 2. Running time   Proposed model의 경우 TSP 500이하에서는 다른 algorithm에 비하여 running time이 느리지만, TSP1000에서 feasible solution을 도출해냄.