Traveling Salesman Problem을 위한 GPU 기반 병렬 Ant Colony System
GPU-based Parallel Ant Colony System for Traveling Salesman Problem
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 논문에서는 개미 집단 시스템(ant colony system)을 통한 순회 외판원 문제(traveling salesman problem)를 효과적으로 해결하기 위해 GPU 기반 병렬 알고리즘을 설계 구현하였다. TSP에서 동시에 수백 또는 수천의 탐색 여정(tour)을 생성하는 반복 과정을 GPU의 작업 병렬성을 활용하여 처리성능을 개선하고, 페로몬 자취 데이터의 업데이트 과정은 32x32의 쓰레드 블럭을 사용하여 데이터 병렬성을 적극 활용하였다. 특히 다중 쓰레드의 메모리 동시 접근을 통해 연속 메모리공간의 병합 접근 효과와 공유 메모리의 동시 접근을 지원하였다. 본 실험은 TSPLIB에서 제공되는127개부터 1002개에 이르는 도시 데이터를 사용하였고, Intel Core i9-9900K CPU와 Nvidia Titan RTX 시스템을 사용하여 순차 알고리즘과 병렬 알고리즘의 성능을 비교하였다. GPU 병렬화에 의한 성능 향상은 약 10.13~11.37배의 성능 개선 효과를 보였다.
Abstract
In this paper, we design and implement a GPU-based parallel algorithm to effectively solve the traveling salesman problem through an ant color system. The repetition process of generating hundreds or thousands of tours simultaneously in TSP utilizes GPU's task-level parallelism, and the update process of pheromone trails data actively exploits data parallelism by 32x32 thread blocks. In particular, through simultaneous memory access of multiple threads, the coalesced accesses on continuous memory addresses and concurrent accesses on shared memory are supported. This experiment used 127 to 1002 city data provided by TSPLIB, and compared the performance of sequential and parallel algorithms by using Intel Core i9-9900K CPU and Nvidia Titan RTX system. Performance improvement by GPU parallelization shows speedup of about 10.13 to 11.37 times.
참고문헌 (16)
- T. H. Cormen, "Introduction to Algorithms" (2001), The MIT Press
- M. Dorigo, "The ant system:Optimization by a colony of cooperating agents", IEEE Transactions on Systems, Man, and Cybernetics–Part B, 26, pp.29~41 (1996)
- Junqi Yu, "A Novel Parallel Ant Colony Optimization Algorithm for Warehouse Path Planning", Journal of Control Science and Engineering, 2020, pp.1687~5249 (2020)
- J. Kanda, "Meta-learning to select the best meta-heuristic for the Traveling Salesman Problem: A comparison of meta-features", Neurocomputing, 205(C), pp.393~406 (2016)
- X. Chen, "A hybrid algorithm combining glowworm swarm optimization and complete 2-opt algorithm for spherical traveling salesman problems", Applied Soft Computing, 58, pp.104~114 (2017)
- C. Groba, "Solving the dynamic traveling salesman problem using a genetic algorithm with trajectory prediction: an application to fish aggregating devices", Computers & Operations Research, pp.22~32 (2015)
- Mavrovouniotis, M., "Ant Colony Optimization Algorithms for Dynamic Optimization:A Case Study of the Dynamic Travelling Salesperson Problem", IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE, 15(1), pp.52~63 (2020)
- M. Mavrovouniotis, "Ant colony optimization with local search for dynamic traveling salesman problems", IEEE Trans. Cybern, 47(7), pp.1743~1756 (2017)
- M. Manfrin, "Parallel Ant Colony Optimization for the Traveling Salesman Problem", Proc. of5th International Workshop on Ant Colony Optimization and Swarm Intelligence, pp.224~234 (2006), Springer-Verlag
- P. Delisle, "Parallel implementation of an ant colony optimization metaheuristic with OpenMP", Proc. of the 3rd European Workshop on OpenMP, pp.1~7 (2001)
- Breno A. de Melo Menezes, "High-Level Parallel Ant Colony Optimization with Algorithmic Skeletons", International Journal of Parallel Programming, 49, pp.776~801 (2021)
- A. Del´evacq, "Parallel Ant Colony Optimization on Graphics Processing Units", Journal of Parallel and Distributed Computing, 73(1), pp.52~61 (2013)
- Menezes, B. A., "Parallelization strategies for GPU-based ant colony optimization solving the traveling salesman problem", Proc. of IEEE Congress on Evolutionary Computation, pp.3094~3101 (2019)
- Yi Zhou, "Parallel ant colony optimization on multi-core SIMD CPUs", Future Generation Computer Systems, 79(2), pp.473~487 (2018)
- "Ant colony optimization"[URL]
- "Symmetric traveling salesman problem"[URL]