Kazuta Kobashi, Akihiro Fujii, Teruo Tanaka, and Kazunori Miyoshi
Ant Colony Optimization, Multithreaded processor, operational analysis, queuing network
Ant Colony Optimization(ACO) is a meta-heuristic and probabilistic technique for solving NP-hard problems. The most widely studied problem using ACO algorithms is the Traveling Salesman Problem (TSP). Although ACO offers a good quality of solution, it still needs considerable computational time and resources. Moreover, since the structure of the algorithm is well suited for parallelization, in this paper we propose an implementation of ACO on a Graphic Processing Unit (GPU), which has a massively parallel architecture. To fully utilize the GPU architecture in the implementation, we use a data-based algorithm consisting of parallel reduction and a parallel binary search for solution construction, instead of the traditional population-based one. Then, a nearest neighbor search is applied to the TSP to reduce the amount of memory usage. Our experiments show that the proposed method has outstanding performance and efficiency compared to the serial CPU and population-based GPU implementations for large scale problems.
Important Links:
Go Back
