| Summary: | 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.
|
|---|