Neural Combinatorial Optimization with RL" target="_blank" title="Neural Combinatorial Optimization with RL" rel="noopener" data-mce-href="http://Neural Combinatorial Optimization with RL">http://Neural Combinatorial Optimization with RL
Neural Combinatorial Optimization with Reinforcement Learning
This paper presents a framework to tackle combinatorial optimization problems using neural networks and reinforcement learning. We focus on the traveling salesman problem (TSP) and train a recurrent network that, given a set of city coordinates, predicts a
arxiv.org
Abstract
이 논문은 TSP 문제와 같은 조합 최적화 문제를 해결하기 위해 강화학습과 신경망을 결합한 새로운 접근 방식을 제시한다. 도시 좌표의 집합이 주어진 상황에서 순환 신경망을 사용하여 도시 순열에 대한 예측을 생성하고, 이를 최적화하기 위해 정책 경사 방법을 사용한다. 정책 경사 방법이랑 정책함수 $\pi$를 경사하강법을 이용해 학습하는 방법을 말한다. 이 방법은 복잡한 엔지니어링이나 휴리스틱 설계 없이도 효과적으로 최적에 가까운 결과를 달성하는 것으로 나타났다.
1. Introduction
이 논문은 강화 학습과 신경망을 사용하여 조합 최적화 문제를 해결하는 프레임워크인 Neural Combinatorial Optimization을 제안한다. 접근 방식으로는 정책 그라디언트를 기반으로 한 두 가지 접근 방식을 고려한다.
- RL Pretraining: Train Set을 사용하여 확률 정책을 매개변수화하는 순환 신경망(RNN)을 최적화하며, 목적함수로는 보상을 사용. 테스트 시에는 정책이 고정되며, 탐욕적 디코딩이나 샘플링을 통해 추론을 수행한다.
- Active Search: 임의의 랜덤한 정책에서 시작하여 단일 테스트 인스턴스에서 RNN 매개변수를 반복적으로 최적화하며, 이 과정에서 보상 목표를 다시 사용하고 검색 중에 샘플링된 최상의 솔루션을 추적한다.
2D 유클리드 그래프에서 100~200개의 노드를 가진 경우, Neural Combinatorial Optimization는 TSP에 대한 지도 학습 접근법을 크게 능가하며, 더 많은 계산 시간을 허용할 때 거의 최적의 결과를 얻는다. 이러한 결과는 신경망이 조합 최적화 문제를 해결하기 위한 일반적인 도구로서 어떻게 사용될 수 있는지에 대한 통찰을 제공하고, TSP 문제의 학습이 가능함을 보였던 Pointer Network가 지닌 지도학습의 한계점을 강화학습을 통해 개선하려는 것이 주요한 아이디어라 할 수 있다.
2. Neural Network Architecture for TSP
이 논문에서는 Pointer Network의 기본구조를 이용하는 것으로 보인다. Pointer Network는 임의 개수의 노드에 대해서도 동작할 수 있는 것이 특징이다. 즉, 상대적으로 적은 노드의 TSP를 학습한 후 더 많은 노드의 TSP에 대해서도 학습 가능한 구조이다. Pointer Network에 관한 논문은 이전 글에서 다룬 바 있다.
Pointer Network" title="Pointer Network" rel="noopener" data-mce-href="http://Pointer Network">http://Pointer Network
[논문 리뷰] Pointer Networks
Pointer Networks " target="_blank" title="Pointer Networks" rel="noopener" data-mce-href="http:// Pointer Networks ">http:// Pointer Networks Pointer Networks We introduce a new neural architecture to learn the conditional probability of an output sequence
taekyounglee1224.tistory.com
Pointer Network의 경우, Convex Hull, Delaunay Triangulation, TSP 등 다양한 조합 최적화 문제에 대해 유연하게 잘 동작한다는 점에서 이 논문에서 기본 구조로 채택한 듯 하다.
2.1. Architecture Details
이 논문에서는 2D Euclidean TSP 상황에 집중한다. Input Graph는 총 $n$개의 도시를 2D 평면 $s$에 나타내는 것으로 표현된다. 이 때, $s = \left\{x_{i} \right\}_{i=1}^{n}$ 으로, 각각의 $x_{i} \in \mathbb{R}^2$에 대해, 각 도시를 한 번씩 방문하고 총 길이가 최소인 점들의 순열 $\pi$를 찾는 데 중점을 둔다. 순열 $\pi$로 정의된 TSP 경로의 길이를 다음과 같이 정의한다.
$$L(\pi|s) = \left\|x_{\pi_{(n)}} - x_{\pi_{(1)}} \right\|_{2} + \sum_{i=1}^{n-1}\left\|x_{\pi_{(i)}} - x_{\pi_{(i+1)}} \right\|_{2}$$
목표는 입력 점 집합 $s$가 주어졌을 때, 짧은 투어에 높은 확률을 할당하고 긴 투어에 낮은 확률을 할당하는 확률적 정책 $p(\pi|s)$의 매개변수를 학습하는 것이다. 이 연구에서 사용된 신경망 구조는
$$p(\pi|s) = \prod_{i=1}^{n}p(\pi(i)|\pi(<i), s)$$
를 개별적인 softmax를 통해 위 식의 우변을 나타낸다. 또한, $p(\pi|s)$를 매개변수화 하기 위해 Pointer Network 알고리즘을 적용한다.
2.2. Policy Gradient
Policy는 강화학습에서 Agent의 행동 방식을 정의하고, 이는 특정 상태(State)에서 Agent가 취하는 행동(Action)으로의 매핑 함수로써 표현될 수 있다. Policy Gradient Method는 주어진 Policy 함수를 반복적으로 업데이트하여 보상을 최대화하는 학습법이다.
본 논문은 이동거리의 총합은 모든 방문노드의 이전 방문노드와의 거리 총합과 마지막 방문노드와 시작 노드 거리의 합으로 정의한다. 이 식이 바로 위에서 정의한 $L(\pi|s)$이다. 그리고 총 이동거리에 대한 기댓값을 목적함수 $J$로 정의하고 이를 최소화하는 방향으로 문제를 해결한다.
$$J(\theta|s) = \mathbb{E}_{\pi\sim p_{\theta}(\cdot|s)}L(\pi|s)$$
Monte Carlo 샘플링 형태로 근사화 시키면
$$\nabla_{\theta}J(\theta) \approx \frac{1}{B} \sum_{j=1}^{B} \left( L(\pi_j|s_j) - b(s_j) \right) \nabla_{\theta} \log p(\pi_j | s_j)$$
여기서 $b(s)$는 총 여행거리의 기댓값을 예측하는 베이스라인 함수이다. 이 함수는 $\pi$와는 독립적이다.
$$b(s) = \frac{1}{N}\sum_{i=1}^{N}L(\pi_{i}|s)$$
이 식을 위의 그라디언트 함수 식에 대입해 보면 실제길이와 평균의 차이, 즉 편차를 최소화하려는 형태임을 알 수 있다. 이를 각 상태마다 반복적으로 해 주는 것이다.
3. Experiments
본 논문에서는 위처럼 4가지 형태의 실험을 제안하는데, 각 실험에 대한 설명은 다음과 같다.
- RL-Pretraining-Greedy: Train Data에 대해서는 임의로 생성한 TSP문제로 RL 에이전트를 학습시키며,Test에 대해서는 단순히 Agent가 가장 성능을 좋게 평가한 Action을 선택
- Active Search(AS): Train Data에서의 학습 없이 테스트 데이터에서 얻은 여러 샘플 경로들에 대해 더 작은 Loss를 갖게끔 Policy를 개선
- RL-Pretraining-Sampling: Train data에서 RL 에이전트를 학습시키며, Test Data에서 Stochastic Policy를 이용해 다양한 샘플 경로를 획득하고 그 중 가장 좋은 경로를 선정한다. 이 때, 사용된 샘플 경로의 수는 1,280,000개이고, TSP20, TSP50, TSP100 의 상황에 대해 각각 최적의 결과를 도출한다.
- RL-Pretraining-Active Search: Train Data에서 사전에 RL 에이전트를 학습시킨 후, 각 Test Sample에 대해, 사전 훈련된 RL 모델에서 모델 매개변수를 초기화하고 배치 크기가 128인 상태로 최대 10,000 훈련 단계까지 Active Search를 실행하여 총 1,280,000개의 후보 솔루션을 샘플링한다.
실험 결과는 다음과 같다.
Q. 보상 함수 설계: 강화 학습 모델의 효과는 보상 함수의 설계에 크게 의존한다. 시간, 비용, 고객 만족도와 같은 다양한 요소가 균형을 이루어야 하는 복잡한 실제 문제에 대한 보상 함수를 설계할 때 어떤 고려 사항을 고려해야 할까?
Q. 제약 조건 처리: 많은 실제 최적화 문제에는 만족해야 하는 엄격한 제약 조건이 포함된다. 특히 모델 아키텍처에 직접 인코딩하기 어려운 복잡한 제약 조건을 다룰 때, 모든 생성된 솔루션이 실현 가능하도록 모델을 어떻게 적응시킬 수 있을까?
Q. 우리가 풀려는 문제는 시작점과 끝점이 동일할 필요는 없을 것 같은데, 같은 알고리즘을 사용해서 학습 가능한지, 아니면 오히려 더 수식이 단순해져서 풀기 쉬워지는 지?
참고 문헌
Monte Carlo" target="_blank" title="Monte Carlo" rel="noopener" data-mce-href="http://Monte Carlo">http://Monte Carlo