방문판매원 문제에 적용한 개선된 개미 군락 시스템
Improved Ant Colony System for the Traveling Salesman Problem
0
조회
0
다운로드
6
인용
0
참고문헌
키워드
초록
개미 군락 시스템 (Ant Colony System, ACS)은 조합 최적화 문제 중의 하나인 방문 판매원 문제에(Traveling Salesman Problem, TSP) 간단하게 응용할 수 있고 좋은 결과를 보여주었다. 그러나 ACS는 작은 TSP에서는 최적해를 구하였지만, 큰 TSP에 대해서는 최적해를 구하지 못하였다. 본 연구에서는 큰 TSP에 대한 최적해를 찾기 위하여 개미들에게 좀 더 많은 정보를 주는 기법의 하나로 한 도시에서 다음 도시로의 탐색 경로를 결정할 때, 인접한 도시들에(adjacent neighbor) 대한 거리로만 결정하지 않고 길이가 w인 부경로(subpath)에 대한 정보를 미리 수집한 후, 이 정보를 이용하여 경로를 생성하였다. 실험 결과 본 연구에서 제안한 기법이 기존의 ACS 기법보다 큰 그래프에서 최적해(Known Optimal)에 가까운 경로를 찾는 것을 볼 수 있다. 그래프에 따라서는 기존의 ACS 기법보다 최대 70% 이상의 성능이 개선되었으며 평균적으로 30%내외의 개선된 결과를 보여준다.
Abstract
Ant Colony System (ACS) applied to the traveling salesman problem (TSP) has demonstrated a good performance on the small TSP. However, in case of the large TSP, ACS does not yield the optimum solution. In order to overcome the drawback of the ACS for the large TSP, the present study employs the idea of subpath to give more information to ants by computing the distance of subpath with length w. In dealing with the large TSP, the experimental results indicate that the proposed algorithm gives the solution much closer to the optimal solution than does the original ACS. In comparison with the original ACS, the present algorithm has substantially improved the performance. By utilizing the proposed algorithm, the solution performance has been enhanced up to 70% for some graphs and around at 30% for averaging over all graphs.
참고문헌 (10)
- "The Ant System: Optimization by a colony of cooperating agents", 26(1), pp.1~13 (1996)
- "Ant Colonies for the Travelling Salesman Problem", 43, pp.73~81 (1997)
- "Ant Colony System에서 효율적 경로 탐색을 위한 지역갱신과 전역갱신에서의 추가 강화에 관한 연구", 10-B, pp.237~242 (2003)
- "Ant Algorithms for Discrete Optimization", 5(3), pp.137~172 (1999)
- "Reasons of ACO’s Success in TSP", 3172, pp.226~237 (2004)
- "Solving symmetric and asymmetric TSPs by ant colonies", pp.622~627 (1996)
- "Ant Colony Optimization" (2003), MIT Press
- "Swarm Intelligence: From Natural to Artificial Systems" (1999), Oxford University Press
- "Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem", 1(1) (1997)
- "Local search the probabilistic salesman problem: correction to the 2-p-opt and 1-shift algorithms" (2003)