## 6 Experimentation  
Experimentation was performed to compare the execution time when solving four TSP problems from the TSPLIB library [37]. A sequential implementation and a manycore GPU parallel implementation based on CUDA (9.2 version) were compared. The system used for performing the experiments was equipped with a Pentium i7 3.2 GHz and an NVIDIA GeForce 1060p graphics accelerator, 6 GB GPU RAM, and 32 GB DDR4 RAM. Different scopes were devised for each of the problems by varying the population sizes (64 and 128 individuals) and the number of iterations performed (1000, 5000, and 10,000 iterations). The cities from TSPLIB that were considered for the experiments were Berlin52, Att48, Eil76, and Ch130, with 52, 48, 76, and 130 urban nodes, respectively. They represent real scenarios taken from cities in Europe, USA, and China. Figures 7-14 depict the results with respect to the CPU and GPU mean time in milliseconds (ms) of 10 blocks of 1000 runs, each with a PC clean reset. Results show that the DTLBO GPU parallel version improves performance up to 6\(\times\) when dealing with a high number of individuals and iterations. DTLBO reached the optimal path in Att48 (distance = 33,523); in the case of Berlin52, the difference obtained with regard to the optimal was only 2 (7544 versus 7542); in the case of the problems with a higher number of urban nodes, DTLBO obtained 6336 in Ch130 (optimal = 6110), and 552.63 in Eil76 (optimal = 538). The paths obtained for these four real urban scenarios are shown in Figures 15-18. Figure 6: Subpopulation organization and memory accesses. Figure 7: CPU and graphics processing unit (GPU) times (in ms) from Berlin130 with respect to different populations (64 and 128) and iterations (1000, 5000, and 10,000). Figure 8: Speedup when comparing CPU and GPU times from Berlin130 with respect to different populations (64 and 128) and iterations (1000, 5000, and 10,000). Figure 10: Speedup when comparing CPU and GPU times for Att48 with respect to different populations (64 and 128) and iterations (1000, 5000, and 10,000). Figure 9: CPU and GPU times (in ms) for Att48 with respect to different populations (64 and 128) and iterations (1000, 5000, and 10,000). Figure 11: CPU and GPU times for Eil76 (in ms) with respect to different populations (64 and 128) and iterations (1000, 5000, and 10,000). Figure 12: Speedup when comparing CPU and GPU times for Eil76 with respect to different populations (64 and 128) and iterations (1000, 5000, and 10,000). Figure 13: CPU and GPU times (in ms) for Ch130 with respect to different populations (64 and 128) and iterations (1000, 5000, and 10,000). Figure 16: DTLBO solution for Att48. Figure 14: Speedup when comparing CPU and GPU times for Ch130 with respect to different populations (64 and 128) and iterations (1000, 5000, and 10,000). Figure 7:0 DTLBO solution for Berlin52. The GPU's features allow it to process a high number of threads per block. As a consequence, it was noted that the increase in the population does not have as much time penalty as the CPU, so the GPU times are only affected by the number of iterations. Moreover, the GPU block architecture is highly suitable for subpopulation algorithms, due to the fact that they can be placed in different blocks of the GPU and consequently run in parallel if the number of subpopulations allows it. It is possible for different problems to be executed on the same GPU, achieving a maximal utilization of the GPU resources and a minimal response time. All of the optimal solutions were obtained with populations of 128 individuals. With populations of 64 individuals, it was only possible to generate one of the optimal solutions (the one of the smallest problem). It was established that population sizes of 64 and 128 are capable of computing all scenarios without memory problems: in the case of 64 individuals, to have a population size close to the number of variables of some problems; and in the case of 128 individuals, to have a population size above almost all of the problems.