A GPU accelerated parallel genetic algorithm for the traveling salesman problem
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 pro...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Penerbit UTHM
2024
|
| Subjects: | |
| Online Access: | http://umpir.ump.edu.my/id/eprint/43901/1/A%20GPU%20accelerated%20parallel%20genetic%20algorithm%20for%20the%20traveling%20salesman%20problem.pdf |
| _version_ | 1825816146420432896 |
|---|---|
| author | Binjubier, Mohammed Mohd Arfian, Ismail Tusher, Ekramul Haque Aljanabi, Mohammad |
| author_facet | Binjubier, Mohammed Mohd Arfian, Ismail Tusher, Ekramul Haque Aljanabi, Mohammad |
| author_sort | Binjubier, Mohammed |
| collection | UMP |
| description | 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. |
| first_indexed | 2025-03-06T04:06:05Z |
| format | Article |
| id | UMPir43901 |
| institution | Universiti Malaysia Pahang |
| language | English |
| last_indexed | 2025-03-06T04:06:05Z |
| publishDate | 2024 |
| publisher | Penerbit UTHM |
| record_format | dspace |
| spelling | UMPir439012025-02-25T08:21:24Z http://umpir.ump.edu.my/id/eprint/43901/ A GPU accelerated parallel genetic algorithm for the traveling salesman problem Binjubier, Mohammed Mohd Arfian, Ismail Tusher, Ekramul Haque Aljanabi, Mohammad QA75 Electronic computers. Computer science QA76 Computer software T Technology (General) TA Engineering (General). Civil engineering (General) 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. Penerbit UTHM 2024-12-18 Article PeerReviewed pdf en cc_by_nc_sa_4 http://umpir.ump.edu.my/id/eprint/43901/1/A%20GPU%20accelerated%20parallel%20genetic%20algorithm%20for%20the%20traveling%20salesman%20problem.pdf 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) https://doi.org/10.30880/jscdm.2024.05.02.010 https://doi.org/10.30880/jscdm.2024.05.02.010 |
| spellingShingle | QA75 Electronic computers. Computer science QA76 Computer software T Technology (General) TA Engineering (General). Civil engineering (General) Binjubier, Mohammed Mohd Arfian, Ismail Tusher, Ekramul Haque Aljanabi, Mohammad A GPU accelerated parallel genetic algorithm for the traveling salesman problem |
| title | A GPU accelerated parallel genetic algorithm for the traveling salesman problem |
| title_full | A GPU accelerated parallel genetic algorithm for the traveling salesman problem |
| title_fullStr | A GPU accelerated parallel genetic algorithm for the traveling salesman problem |
| title_full_unstemmed | A GPU accelerated parallel genetic algorithm for the traveling salesman problem |
| title_short | A GPU accelerated parallel genetic algorithm for the traveling salesman problem |
| title_sort | gpu accelerated parallel genetic algorithm for the traveling salesman problem |
| topic | QA75 Electronic computers. Computer science QA76 Computer software T Technology (General) TA Engineering (General). Civil engineering (General) |
| url | http://umpir.ump.edu.my/id/eprint/43901/1/A%20GPU%20accelerated%20parallel%20genetic%20algorithm%20for%20the%20traveling%20salesman%20problem.pdf |
| work_keys_str_mv | AT binjubiermohammed agpuacceleratedparallelgeneticalgorithmforthetravelingsalesmanproblem AT mohdarfianismail agpuacceleratedparallelgeneticalgorithmforthetravelingsalesmanproblem AT tusherekramulhaque agpuacceleratedparallelgeneticalgorithmforthetravelingsalesmanproblem AT aljanabimohammad agpuacceleratedparallelgeneticalgorithmforthetravelingsalesmanproblem AT binjubiermohammed gpuacceleratedparallelgeneticalgorithmforthetravelingsalesmanproblem AT mohdarfianismail gpuacceleratedparallelgeneticalgorithmforthetravelingsalesmanproblem AT tusherekramulhaque gpuacceleratedparallelgeneticalgorithmforthetravelingsalesmanproblem AT aljanabimohammad gpuacceleratedparallelgeneticalgorithmforthetravelingsalesmanproblem |