Parallel Maxmin Ant System Based on Heterogeneous Platform

Abstract:

Maxmin Ant System is a kind of heuristic algorithm with excellent performance, which is commonly used to solve combinatorial optimization problems. But it costs a long time when scale of the target problem is large as well as iterations are a lot. The experiment took the open source packet ACOTSP as a reference, used the advantage of multithreaded GPU, and implemented ACO algorithm on CPUGPU platform by parallel ants strategy. While the parallel algorithm is running on GPU, we also analyzed the impact factors carefully, such as data transmission, memory hierarchy, library calls et al, and made useful optimization. Eventually, the experiment made 13 times speedup, proving the parallel strategy is highly efficient and applicable.