본 포스팅에서는 강화학습을 공부하기 위해서 여러가지 강화학습 알고리즘으로 TSP 문제를 풀어본 경험을 정리하려고 합니다.
테스트해본 강화학습 알고리즘은 1. Deep Q-Network (DQN), 2. REINFORCE, 3.REINFORCE with Baseline의 세 가지입니다.
더불어 각 강화학습의 결과를 평가하기 위해서 Google OR Tools와 Heuristic 으로 풀어본 결과도 함께 비교해 보도록 하겠습니다.
Google OR Tools
Google OR Tools ortools.constraint_solver를 사용하면 쉽게 TSP 문제를 풀어 볼 수 있습니다.
본 포스팅에서는 각 강화학습의 품질을 평가하기 위해서 OR Tools을 기본 baseline으로 계산합니다.
Heuristic
TSP를 위한 휴리스틱중 가장 간단한 방법인 Nearest Neighbor 방법을 사용하여 TSP문제를 풀어보고 결과를 강화학습 알고리즘의 결과를 비교해 보겠습니다.
참고로 Nearest Neighbor는 아래와 같은 순서로 알고리즘이 작동합니다.
1.
시작 도시를 하나 선택합니다.
2.
현재 도시에서 아직 방문하지 않은 도시들 중 가장 가까운 도시를 찾습니다.
3.
그 도시로 이동합니다. 이동한 도시는 이제 방문한 도시로 표시됩니다.
4.
모든 도시를 방문할 때까지 2-3단계를 반복합니다.
5.
마지막으로 방문한 도시에서 시작 도시로 돌아와 경로를 완성합니다.
Deep Q-Network (DQN)
DQN은 상태-행동 가치 함수인 Q-function을 심층 신경망으로 근사하여 최적의 행동을 학습하는 알고리즘입니다.
이산적인 행동 공간을 갖는 문제에 효과적이기 때문에 다음 노드로 이동하는 행동공간을 선택해야 하는 TSP 문제와도 잘 맞을 것으로 판단했습니다
REINFORCE
REINFORCE는 정책 경사(Policy Gradient) 알고리즘의 대표적인 방법으로,
에이전트가 수행한 행동에 따른 보상을 기반으로 정책 자체를 직접적으로 최적화합니다.
에피소드 단위로 학습이 진행되며, 전체 경로에 대한 보상을 사용하여 정책을 한번에 업데이트합니다.
REINFORCE with Baseline
REINFORCE은 보상의 변동성이 클 경우 학습이 불안정해지는 경향이 있습니다.
REINFORCE with Baseline은 이러한 높은 분산 문제를 완화하기 위해 기준값(baseline) 함수를 도입하여 해결 합니다.
보상의 기댓값을 추정하여 실제 보상과의 차이(advantage)를 계산하고, 이 advantage를 사용하여 정책을 업데이트함으로써 학습의 안정성과 효율성을 향상시킵니다.
TSP 알고리즘 수행결과
Reference:
