Adapting the GA Approach to Solve Traveling Salesman Problems on CUDA Architecture

Ugur Cekmez, Mustafa Ozsiginan, Ozgur Koray Sahingoz
Computer Engineering Department, Yildiz Technical University, Istanbul, Turkey
14th IEEE International Symposium on Computational Intelligence and Informatics, 2013


   title={Adapting the GA Approach to Solve Traveling Salesman Problems on CUDA Architecture},

   author={Cekmez, Ugur and Ozsiginan, Mustafa and Sahingoz, Ozgur Koray},



Download Download (PDF)   View View   Source Source   



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.
Rating: 2.5. From 1 vote.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: