Paper) Neural Combinatorial Optimization with Reinforcement Learning - Not Finished...

목차

Abstract

goal

• TSP 문제를 품
• 우리는 순회 판매원 문제(TSP)에 초점을 맞추고 일련의 도시 좌표가 주어진다면 다른 도시 순열에 대한 분포를 예측하는 반복 신경망을 훈련시킨다.
• negative tour length를 보상 신호로 사용하여 정책 기울기 방법을 사용하여 현재 신경망의 매개 변수를 최적화한다.
• 우리는 일련의 훈련에서 네트워크 매개 변수를 학습하는 것과 개별 시험 그래프에서 학습하는 것을 비교한다. 계산 비용에도 불구하고, 많은 엔지니어링 및 휴리스틱 설계 없이, 신경 조합 최적화는 최대 100개의 노드가 있는 2D 유클리드 그래프에서 최적의 결과에 가까운 결과를 달성한다. 또 다른 NP-난이도 문제인 KnapSack에 적용하면, 동일한 방법이 최대 200개의 항목이 있는 인스턴스에 대해 최적의 솔루션을 얻는다

 

result & discussion

• optimal에 유사한 결과까지 얻었다고 주장한다.

Introduction

조합 최적화 중에서 예로는 순회 판매원 문제(TSP)가 있는데, 그래프가 주어지면 최소 총 가장자리 가중치(투어 길이)로 최적의 노드 시퀀스를 찾기 위해 순열 공간을 검색해야 한다.

2차원 유클리드에서도 최적의 TSP 솔루션을 찾는 것은 NP-hard이다.

사례(Papadimitriou, 1977)는 노드가 2D 점이고 모서리 가중치가 점 쌍 사이의 유클리드 거리인 경우이다. 실제로 TSP solver는 경쟁적인 투어를 효율적으로 찾기 위해 검색 절차를 안내하는 수작업 휴리스틱에 의존합니다.

이러한 휴리스틱이 TSP에서 잘 작동하더라도, 일단 문제 진술이 약간 바뀌면, 그것들은 수정될 필요가 있다. 이와는 대조적으로, 기계 학습 방법은 훈련 데이터를 기반으로 자체 휴리스틱을 자동으로 발견하여 많은 최적화 작업에 적용할 수 있으므로 한 가지 작업에만 최적화된 해결사보다 수공학을 덜 필요로 한다.

대부분의 성공적인 기계 학습 기술은 훈련 입력에서 출력으로의 매핑을 학습하는 감독 학습 계열에 속하지만, 최적의 라벨을 줄 수 없기 때문에 지도 학습은 대부분의 조합 최적화 문제에 적용되지 않는다.

검증기를 사용하여 솔루션 세트의 품질을 비교하고 학습 알고리즘에 대한 보상 피드백을 제공할 수 있기 때문에 지도 학습보다는 강화학습 패러다임을 사용한다.

우리는 지도 방식의 맵핑을 최적화하기 위해 라벨링된 데이터와 같은 최적 솔루션을 사용하는 경우에도 다른 투어를 탐색하고 그에 상응하는 보상을 관찰하는 RL 에이전트에 비해 일반화가 다소 미흡하다는 것을 경험적으로 입증한다.

저자는 강화학습과 신경망을 사용하여 조합최적화 문제를 해결하기 위한 프레임워크인 neural combinatorial optimization을 제안한다.

policy gradients 기반으로 2가지 접근 방식을 고려한다.

첫번째 접근 방식은 강화학습 사전 학습으로 예상 보상을 목표로 하여 솔루션보다 확률적 정책을 매개 변수화하는 반복 신경망(RNN)을 최적화하기 위한 훈련 세트를 사용한다. 테스트시 정책이 고정되고 디코딩또는 샘플링으로 추론을 한다.

두 번째 접근 방식은 active search로 사전 훈련을 포함하지 않습니다. 임의 정책에서 시작하여 검색 중에 샘플링된 최상의 솔루션을 추적하면서 예상 보상 목표를 사용하여 단일 테스트 인스턴스에서 RNN 매개 변수를 반복적으로 최적화한다. 우리는 RL 사전 훈련과 능동 검색을 결합하는 것이 실무에서 가장 효과적이라는 것을 발견했다.

저자들은 최대 100개의 노드가 있는 2D 유클리드 그래프에서 신경 조합 최적화는 TSP에 대한 지도 학습 접근방식을 크게 능가하며(Vinyals et al., 2015b) 더 많은 계산 시간이 허용되면 최적의 결과에 가까운 결과를 얻는다. KnapSack 문제에 대해 동일한 방법을 테스트하여 유연성을 설명하며, 최대 200개의 항목이 있는 인스턴스에 대해 최적의 결과를 얻는다. 이러한 결과는 신경망을 조합 최적화 문제, 특히 휴리스틱을 설계하기 어려운 문제를 해결하기 위한 일반적인 도구로 사용할 수 있는 방법에 대한 통찰력을 제공한다.

부가적으로 NP-HARD 예시로는 다음과 같다고 한다.

NP-hard는 다항시간내에 풀 수 없는 문제를 말한다. 다항 방정식 대신에 지수 방정식으로 풀 수 있는 문제를 말한다. 즉 결정석 다항식으로 구성할 수 없다는 것이다. NP-hard라고 해서 다항식이 아니라는 것은 아니다. 다만 다항식으로 표현될 수 있을 지의 여부가 아직 알려지지 않았다라는 것이다.

즉, NP-Hard란 TSP문제와 같이 모든 경우의 수를 일일히 확인해보는 방법이외에는 다항식 처럼 답을 풀이 할 수 없는 문제들을 말한다. NP-hard의 예로 외판원 문제가 있다.

 

 

TODO