Travel Salesman Problem is the most popular combinatorial optimization problem. Although numerous heuristics and machine learning approaches were proposed, training a value function for TSP remains a challenging task. In this research, the main focus is shifted from finding a capable model to the wise choice of instances to label using active learning. Two selection criteria based on one-step look-ahead and novelty for choosing the best instance to label are proposed. In addition, a metric to evaluate performance in active learning settings is introduced. The experimental results demonstrate that applying active learning gives a significant advantage over passive learning.
외판원 순회 문제는 가장 유명한 조합 최적화 문제이다. 수많은 휴리스틱 및 기계학습 접근법이 제안되었지만, 외판원 순회에 대한 가치 함수를 훈련하는 것은 여전히 어려운 과제이다. 본 연구에서는 유능한 모델을 찾는 것에서 벗어나 능동 학습을 이용해서 레이블을 붙일 인스턴스를 선택하는데 주요 초점을 맞추었다. 라벨링 할 최적의 인스턴스를 선택하기 위해 한 단계 전방 알고리즘 및 신규성에 기반한 두 가지 선택 기준을 제안하였다. 더하여, 능동 학습 설정에서 성능을 평가하는 지표를 도입하였다. 실험 결과 능동 학습을 적용하는 것이 수동 학습에 비해 중요한 이점을 제공함을 보여주었다.
