https://arxiv.org/abs/1611.09940

요약

  • TSP 문제는 Node가 많아질 경우 Optimal Solution을 구하기 어려워 지도학습에 활용할 데이터셋을 구하기 어려움
  • 이를 해결하기 위해 TSP문제를 강화학습으로 해결하는 모델 제안

배경지식

다음의 내용을 알고 있으면 글을 이해하기 편합니다.

  • 조합 최적화 (Combinatorial Optimization)
  • TSP
  • 강화학습 (Reinforcement Learning)
  • Pointer Network

배경

조합 최적화 문제란 이산적(Discrete)이거나 이산적으로 환원(Reduction) 가능한 탐색 공간에서 최적의 해를 찾는 문제입니다. 대표적인 문제로는 Traveling Salesman Problem (TSP), Knapsack Problem, Jop Ship scehduling 등이 있습니다. Neural Combinatorial Optimization with RL 논문은 이 중에서 TSP를 집중적으로 해결했으며 그 외에도 Knapsack 문제에도 확장하여 적용할 수 있는 방법을 제안한 논문입니다.

Traveling Salesman Problem (TSP)

TSP는 n개의 노드에 대해서 이동거리를 최소화하도록 하는 노드 방문 순서를 결정하는 문제입니다. 아래 그림처럼 어떤 순서로 도시를 방문했는지에 따라 이동거리의 총합은 크게 차이가 나게 됩니다[1].

서로 다른 경로의 여행거리

TSP의 문제의 계산복잡도는 $O(N^22^N)$으로 알려져 있습니다. 따라서 많은 개수의 노드에 대해서는 정확한 값을 찾기 어렵습니다. 기존에는 탐색 공간을 줄여서 효율성을 높이는 여러 휴리스틱을 사용하였습니다. 하지만 문제에 따라 적절한 휴리스틱을 사용해야 합니다.
이에 따라 별도의 휴리스틱을 사용하지 않고도 2D Euclidean Graph로 표현된 TSP 문제를 Neural Network로 해결하는 방안들이 제안되었습니다. 그 중하나가 이전 포스팅에 소개한 Pointer Network입니다. Pointer Network는 20개의 노드에 대한 TSP 문제를 지도학습으로 해결하여 노드 50개에 대한 TSP까지 준수한 성능을 내는 모델을 제안했습니다.
하지만 더 많은 수의 node에 TSP 문제에 적용하기 위해서는 그에 해당하는 optimal solution을 사용해 학습해야 하는데 optimal solution을 계산하기 어렵습니다. (실제로 여러 TSP 논문에서 노드 100개까지의 optimal solution을 사용하고 그 이상은 기존의 휴리스틱 방법론들과 이동거리를 비교합니다.)

Neural Combinatorial Optimization with RL 논문은 이러한 지도학습의 한계점을 극복하기 위해 강화학습을 사용하는 것을 제안했습니다.
Pointer Network 모델을 그대로 사용하면서 REINFORCE 라는 강화학습 알고리즘을 사용하여 훈련하였습니다.
논문에서는 knapsack에서도 좋은 성능을 보여줬다고 말하지만 본 글에서는 TSP 문제만을 다루겠습니다.

강화학습

REINFORCE

강화학습은 환경과 Agent가 상호작용하면서 얻은 피드백을 통해 학습하는 방법입니다. Agent는 환경에서 관측한 상태 (State)로부터 어떤 행동 (Action)을 할지 결정하는 State-Action 함수를 학습하게 됩니다. 이러한 State-Action 함수를 policy라고 하고, 강화학습의 목표는 피드백에 해당하는 목적함수를 최대화 혹은 최소화 하는 policy를 찾는 것입니다. 이때 policy를 직접적으로 업데이트하는 방식을 Policy Gradient라고 하며, REINFORCE 알고리즘은 이러한 Policy Gradient 의 한 종류입니다. REINFORCE 알고리즘은 Monte-Carlo Method를 통해 샘플링하여 policy에 따른 목적함수를 추정하고 이를 통해 Policy를 업데이트 하는 방법입니다. 좀 더 자세한 설명은 Lilian Weng의 블로그를 참고해주세요.

TSP 문제에서는 총 여행거리 $L$ 을 최소화해야 합니다. 따라서 TSP는 총 여행거리의 기대값을 목적함수 J로 정의하고 이를 최소화시키는 것으로 정의할 수 있습니다 이는 다음과 같은 식으로 표현할 수 있습니다.

  • 여행거리 : $ L(\pi | s) = || x_{\pi (n)} - x_{\pi (1)} || + \sum_{i=1}^{n-1} ||x_{\pi (i)} - x_{\pi (i+1)}|| $
  • Policy : $ p(\pi | s) = \Pi_{i=1}^{n}(p(\pi (i) | \pi (<i), s) $
  • 목적함수 : $ J(\theta | s) = E_{\pi \sim p_{\theta} (.|s)} L(\pi | s) $

Search Strategy

Agent가 여행순서를 결정하는 시간 (Inference Time)은 오래걸리지 않습니다. 따라서 여러 결과를 출력 후 그 중에서 가장 좋은 방법을 선택하는 2가지 방법을 추가로 제안했습니다.

  • Active Search: 하나의 test input에 대해서 여러 번 결과를 출력하고 이에 대한 결과를 사용해 Agent를 학습합니다.
  • Sampling : Poliy는 stochastic하므로 Agent는 하나의 TSP 문제에 대해서 여러 여행경로를 출력할 수 있습니다. 이러한 복수개의 여행경로로부터 가장 좋은 여행 경로를 선택하는 방법입니다.

Different learning configuration

추가로 강화학습의 탐험을 유도하기 위해 softmax temparture와 logic clipping이라는 트릭이 사용되었지만, 본 글에서는 이에 대한 설명은 생략하겠습니다.

실험 결과

저자는 제안하는 모델과 더불어 supervised learning, 기타 휴리스틱 방법론들, 그리고 optimal solution을 비교했습니다.

  • Active Search (AS): 학습없이 Active search 방식으로 결과
  • RL pretraining-Greedy: 학습을 위해 생성한 학습 데이터에서 RL Agent를 학습시킨 후 테스트에서는 RL Agent가 가장 좋은 Action을 선택하여 출력한 결과
  • RL pretraining-Greedy@16: 16개의 RL Agent가 가장 생성한 결과 중 가장 좋은 결과
  • RL pretraining-Sampling: 학습을 위해 생성한 학습 데이터에서 RL Agent를 학습시킨 후 테스트에서는 Sampling 방식으로 결과
  • RL pretraining-Active Search: 학습 후 Active search 방식으로 결과
  • Supervised Learning: Pointer Network로 학습한 결과
  • Optimal
  • 기타 heuristic 방법론들

실험 결과는 다음과 같습니다.

아래 표에서 나온 것처럼 강화학습을 사용한 모델은 기존 지도학습과 휴리스틱 방법론보다 더 좋은 결과를 보였고, Optimal Solution에 근접한 결과를 보였습니다.

또한 수행시간을 보면 강화학습이 기존 휴리스틱 및 Optimal solution 대비 더 빠르게 결과를 보였습니다.

TSP 결과와 수행시간

아래표는 Pretraining-Sampling 방법, Pretraining-Active Search과 Or-Tools에서 제공하는 세가지 방법론들과의 결과를 비교한 것입니다.
표를 보면 속도측면에서는 Pretrainig-sampling이 성능 측면에서는 Prtraining-Active Search가 우세하다는 것을 볼 수 있습니다.
다만 Guided Local Search에 비해서는 둘 모두 낮은 성능을 보입니다. 또한 Solution 수가 적을수록 Or-tools에서 제공하는 방법들이 더 빠른 수행시간을 보입니다.

Performance of RL pretraining-sampling and RL pretraining-Active Search
Performance of OR-Tools

결론

논문에서는 label을 얻기 어려운 TSP문제에서도 학습이 가능한 강화학습 모델을 제안하였고, 성능을 비교했습니다.
또한 시간을 일정수준 포기하고 성능을 높일 수 있는 방법들에 대해서도 제안을 했습니다.
개인적으로는 지도학습과 같은 모델을 썼음에도 불구하고 더 좋은 성능을 보였다는 점이 신기했습니다.

하지만 Pointer Network와는 달리 Generalization에 대한 결과가 없다는 점이 아쉬웠습니다.
또한 Guided Local search에 비해 아직 속도나 성능 측면에서 큰 우위가 없어 실적용하기에는 아직 어려움이 있을 것 같다고 생각이 들었습니다.

Reference

저작자표시

티스토리툴바