ORTools, Heuristic, DQN, REINFORCE, REINFORCE with Baseline으로 TSP 문제를 풀어본 결과를 비교해 보겠습니다.
1.
가장 좋은 품질의 결과를 도출한 것은 ORTools와 DQN입니다. 총 4229의 거리의 TSP 결과를 생성합니다.
2.
Heuristic은 4422의 거리로 가장 좋은 품질의 결과는 아니지만 가장 빠른 시간에 결과를 도출하였습니다.
3.
Policy 기반의 REINFORCE와 REINFORCE with Baseline은 가장 나쁜 결과를 도출하였습니다.
하지만 DQN, REINFORCE, REINFORCE with Baseline은 하이퍼파라미터 값의 설정에 따라
TSP 품질의 변화폭이 컸습니다. 위 테스트 결과에서도 하이퍼파라미터 튜닝 결과에 따라서 품질의 순위는 충분하게 바뀔 수 있습니다.
# DQN 하이퍼파라미터
NUM_CITIES = 20
BATCH_SIZE = 64
GAMMA = 0.99
EPS_START = 1.0
EPS_END = 0.01
EPS_DECAY = 0.9999
MEMORY_SIZE = 10000
LEARNING_RATE = 0.0008
NUM_EPISODES = 30000
MAX_STEPS = NUM_CITIES*2
UPDATE_TARGET_EVERY = 100
INVALID_ACTION_PENALTY = -2000
Python
복사
TSP 결과를 시각화 하면 아래와 같이 확인 할 수 있습니다.
Reference:
[1]
