A Parallel Ant Colony Optimization Algorithm Based On Fine-grained Model With GPU-Acceleration

Ant Colony Optimization algorithm (ACO) is an evolutionary computation technique inspired by social behavior or ant colony. It has proven to be a powerful global optimization method and shows great potential in practice. However, it still needs plenty of computing time when it processes much data and when large-scale complicated work is involved in which math modeling and optimization are highly demanded, whereas parallel ACO comes into being and becomes a hit because it can reduce working-out time dramatically. Parallel ACO algorithm is mostly run on parallel machine and simulated by multi-thread technology, however, exists the following drawbacks: The consumption on communication between processes confines the population of ant colony; Most researchers don't have the parallel machine equipments, therefore couldn't make use of parallel ACO algorithm to solve problems; Multi-thread technology couldn't raise running performance because it runs on common pc which serial-parallel simulation.The highly processing power, parallelism and programmability available nowadays on the contemporary GPU provide an ideal platform on which the general-purpose computation could be made.Aiming at those problems in parallel ACO algorithm, we raised a fine-grained ACO algorithm based on GPU acceleration, which converts the process of working-out into the execution of kernels based CUDA using a thread block to simulate an ant, speeds up its running and provides ordinary user with feasible ACO algorithm. The excutive model of GPU using CUDA is parallel threads. Thread is the smallest unit of CUDA. Many threads compose a thread block. The threads in the same block can access shared memory and can synchronize rapidly.In this paper, as an example, we mainly discuss MMAS and ACS's parallelization and describe the algorithm's design and programming. Furthermor, we present a lot of results of applying to symmetric traveling salesman problems, and give comparisions with the relevant sequential version when running under the same computing environment, and analysis the properties of parallel ACO algorithm. The simulation results show that our algorithm achieves a good optimization effect and it also increases the ant population in the fine-grained parallelism while speeding up its running.