A Study on the Traveling Salesman Problem by Combination of Greedy and Genetic Algorithms
Chang‐Young Lee · 한국전자통신학회 학술대회지 · 2014
이 논문에서 우리는 탐욕 일고리듬과 유전자 알고리듬을 조합하여 외판원문제(Traveling Salesman Problem, TSP)를 해결하는 방법에 대해 연구한다. 탐욕 알고리듬은 즉각적인 해를 제공하지만 그 해는 최적화 경로에서 벗어나는 것이 보통이다. 한편, 유전자 알고리듬은 이보다 더 나은 해를 낳지만 매우 큰 계산적 비용을 요구한다. 본 연구에서 제시하는 방법은 그 둘을 조합하는 것이다. 실험 결과, 매우 빠른 수렴속도로 유전자 알고리듬에 가까운 준 최적화 경로를 검색할 수 있음이 확인되었다.