Adapting the GA approach to solve Traveling Salesman Problems on CUDA architecture

摘要

The vehicle routing problem (VRP) is one of the most challenging combinatorial optimization problems, which has been studied for several decades. The number of solutions for VRP increases exponentially while the number of points, which must be visited increases. There are 3.0×10⁁64 different solutions for 50 visiting points in a direct solution, and it is practically impossible to try out all these permutations. Some approaches like evolutionary algorithms allow finding feasible solutions in an acceptable time. However, if the number of visiting points increases, these algorithms require high performance computing, and they remain insufficient for finding a feasible solution quickly. Graphics Processing Units (GPUs) have tremendous computational power by allowing parallel processing over lots of computing grids, and they can lead to significant performance gains compared with typical CPU implementations. In this paper, it is aimed to present efficient implementation of Genetic Algorithm, which is an evolutionary algorithm that is inspired by processes observed in the biological evolution of living organisms to find approximate solutions for optimization problems such as Traveling Salesman Problem, on GPU. A 1-Thread in 1-Position (1T1P) approach is developed to improve the performance through maximizing efficiency, which then yielded a significant acceleration by using GPUs. Performance of implemented system is measured with the different parameters and the corresponding CPU implementation.