Binjubier, Mohammed and Mohd Arfian, Ismail and Tusher, Ekramul Haque and Aljanabi, Mohammad (2024) A GPU accelerated parallel genetic algorithm for the traveling salesman problem. Journal of Soft Computing and Data Mining, 5 (2). pp. 137-150. ISSN 2716-621X. (Published)
|
Pdf
A GPU accelerated parallel genetic algorithm for the traveling salesman problem.pdf Available under License Creative Commons Attribution Non-commercial Share Alike. Download (815kB) | Preview |
Abstract
The Traveling Salesman Problem (TSP) is a widely studied challenge in combinatorial optimization. Given a set of cities and their pairwise distance, the problem seeks to find the minimum-distance tour that the salesman can make such that he visits every city once and goes back to the origin. The problem was classified as NP-Hard. Several different algorithms were developed to solve the problem; among them, the Genetic Algorithm was used to deal with it. However, runtime may turn out to be of crucial concern when dealing with complex TSPs. Such limitations could be alleviated by recommending an implementation of a parallelized genetic algorithm, further analyzing the impact of block size configuration for efficient runtime on the GPU. This recommendation takes advantage of the computational presence afforded by the GPU to increase the speed of processing without compromising solution quality. Moreover, parallelism can be considerably included in the framework structure of the GA while tackling the TSP. In this work, authors propose 'Coarse-Grained' parallel scheme-population is divided into a number of subpopulations, without any individual migration between them. Each from the subpopulations is concurrently processed by several threads of the GPU. That makes execution of the same tasks on different data in parallel possible. Such Coarse-Grained design significantly speeds up enhanced GA. The results of the experiments reveal significant improvements in the processing times. In fact, parallel GA results for the gr120 dataset, with a population size of 2048, reach an average processing time of 0.7 seconds compared to the sequential one.
| Item Type: | Article |
|---|---|
| Additional Information: | Indexed by Scopus |
| Uncontrolled Keywords: | CUDA; Genetic algorithm; Parallel computing; Traveling salesman problem |
| Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science Q Science > QA Mathematics > QA76 Computer software T Technology > T Technology (General) T Technology > TA Engineering (General). Civil engineering (General) |
| Faculty/Division: | Institute of Postgraduate Studies Centre of Excellence for Artificial Intelligence & Data Science Faculty of Computing |
| Depositing User: | Mr Muhamad Firdaus Janih@Jaini |
| Date Deposited: | 25 Feb 2025 08:21 |
| Last Modified: | 25 Feb 2025 08:21 |
| URI: | http://umpir.ump.edu.my/id/eprint/43901 |
| Download Statistic: | View Download Statistics |
Actions (login required)
 |
View Item |