Efficient Parallelization of a Genetic Algorithm Solution on the Traveling Salesman Problem with Multi-core and Many-core Systems

Document Type : Original Article

Authors

Department of Computer Engineering, Engineering Faculty, Bu-Ali Sina University, Hamedan, Iran

Abstract

Efficient parallelization of genetic algorithms (GAs) on state-of-the-art multi-threading or many-threading platforms is a challenge due to the difficulty of scheduling hardware resources regarding the concurrency of threads. In this paper, for resolving the problem, a novel method is proposed, which parallelizes the GA by designing three concurrent kernels, each of which are running some dependent effective operators of GA. The proposed method can be straightforwardly adapted to run on many-core and multi-core processors by using Compute Unified Device Architecture (CUDA) and Threading Building Blocks (TBB) platforms. To efficiently use the valuable resources of such computing cores in concurrent execution of the GA, threads that run any of the triple kernels are synchronized by a considerably fast switching technique. The offered method was used for parallelizing a GA-based solution of Traveling Salesman Problem (TSP) over CUDA and TBB platforms with identical settings. The results confirm the superiority of the proposed method to state-of-the-art methods in effective parallelization of GAs on Graphics Processing Units (GPUs) as well as on multi-core Central Processing Units (CPUs). Also, for GA problems with a modest initial population, though the switching time among GPU kernels is negligible, the TBB-based parallel GA exploits the resources more efficiently.

Keywords


6. REFERENCES
1. Fathollahi-Fard, A.M., Hajiaghaei-Keshteli, M., and Tavakkoli-Moghaddam, R., 'The Social Engineering Optimizer (Seo)', Engineering Applications of Artificial Intelligence, (2018), Vol. 72, 267-293. https://doi.org/10.1016/j.engappai.2018.04.009
2. Fard, A.F. and Hajiaghaei-Keshteli, M., 'Red Deer Algorithm (Rda); a New Optimization Algorithm Inspired by Red Deers’ Mating', in, International Conference on Industrial Engineering, IEEE., (2016). https://doi.org/10.1007/s00500-020-04812-z
3. Mohammadzadeh, H., Sahebjamnia, N., Fathollahi-Fard, A., and Hahiaghaei-Keshteli, M., 'New Approaches in Metaheuristics to Solve the Truck Scheduling Problem in a Cross-Docking Center', International Journal of Engineering-Transactions B: Applications, 2018, Vol. 31, No. 8, 1258-1266. https://doi.org/10.5829/ije.2018.31.08b.14
4. Fathollahi-Fard, A., Hajiaghaei-Keshteli, M., and Tavakkoli-Moghaddam, R., 'A Lagrangian Relaxation-Based Algorithm to Solve a Home Health Care Routing Problem', International Journal of Engineering Transactions A: Basics, Vol. 31, No. 10, (2018), 1734-1740. https://doi.org/10.5829/ije.2018.31.10a.16
5. Hajiaghaei-Keshteli, M., Abdallah, K., and Fathollahi-Fard, A., 'A Collaborative Stochastic Closed-Loop Supply Chain Network Design for Tire Industry', International Journal of Engineering Transactions A: Basics, Vol. 31, No. 10, (2018), 1715-1722. https://doi.org/10.5829/ije.2018.31.10a.14
6. López-González, A., Campaña, J.M., Martínez, E.H., and Contro, P.P., 'Multi Robot Distance Based Formation Using Parallel Genetic Algorithm', Applied Soft Computing, (2020), Vol. 86, p. 105929. https://doi.org/10.1016/j.asoc.2019.105929
7. Munroe, S., Sandoval, K., Martens, D.E., Sipkema, D., and Pomponi, S.A., 'Genetic Algorithm as an Optimization Tool for the Development of Sponge Cell Culture Media', In Vitro Cellular & Developmental Biology-Animal, Vol. 55, No. 3, (2019), 149-158. https://doi.org/DOI: 10.1007/s11626-018-00317-0
8. Sin, I.H. and Do Chung, B., 'Bi-Objective Optimization Approach for Energy Aware Scheduling Considering Electricity Cost and Preventive Maintenance Using Genetic Algorithm', Journal of Cleaner Production, Vol. 244, (2020), 118869. https://doi.org/10.1016/j.jclepro.2019.118869
9. Yasmin, S.: 'Linear Colour Image Processing in Hypercomplex Algebra Guided by Genetic Algorithms', University of Essex, 2019
10. Lima, A.A., de Barros, F.K., Yoshizumi, V.H., Spatti, D.H., and Dajer, M.E., 'Optimized Artificial Neural Network for Biosignals Classification Using Genetic Algorithm', Journal of Control, Automation and Electrical Systems, Vol. 30, No. 3, (2019), 371-379. https://doi.org/10.1007/s40313-019-00454-1
11. Rajagopalan, A., Modale, D.R., and Senthilkumar, R., Optimal Scheduling of Tasks in Cloud Computing Using Hybrid Firefly-Genetic Algorithm', Advances in Decision Sciences, Image Processing, Security and Computer Vision, (Springer, 2020) ISBN: 978-3-030-24318-0. https://doi.org/10.1007/978-3-030-24318-0_77
12. Rajesh, K., Visali, N., and Sreenivasulu, N., Optimal Load Scheduling of Thermal Power Plants by Genetic Algorithm', Emerging Trends in Electrical, Communications, and Information Technologies, (Springer, 2020) ISBN: 978-981-13-8942-9. https://doi.org/10.1007/978-981-13-8942-9_33
13. Arif, M.H., Li, J., Iqbal, M., and Liu, K., 'Sentiment Analysis and Spam Detection in Short Informal Text Using Learning Classifier Systems', Soft Computing, Vol. 22, No. 21, (2018), 7281-7291. https://doi.org/10.1007/s00500-017-2729-x
14. Talbi, E.-G., 'A Unified View of Parallel Multi-Objective Evolutionary Algorithms', Journal of Parallel and Distributed Computing, Vol. 133, (2019), 349-358. https://doi.org/10.1016/j.jpdc.2018.04.012
15. Nayak, S. and Panda, M., Hardware Partitioning Using Parallel Genetic Algorithm to Improve the Performance of Multi-Core Cpu', Advances in Intelligent Computing and Communication, (Springer, 2020) ISBN: 978-981-15-2774-6
16. Giap, C.N. and Ha, D.T., 'Parallel Genetic Algorithm for Minimum Dominating Set Problem', in, Computing, Management and Telecommunications (ComManTel), 2014 International Conference on, (IEEE, 2014). https//doi.org/10.1109/ComManTel.2014.6825598
17. Zhu, J. and Li, Q., 'Application of Hybrid Mpi+ Tbb Parallel Programming Model for Traveling Salesman Problem', in, Green Computing and Communications (GreenCom), 2013 IEEE and Internet of Things (iThings/CPSCom), IEEE International Conference on and IEEE Cyber, Physical and Social Computing, (IEEE, 2013). https://doi.org/10.1109/GreenCom-iThings-CPSCom.2013.408
18. Fujimoto, N. and Tsutsui, S., 'A Highly-Parallel Tsp Solver for a Gpu Computing Platform', in, International Conference on Numerical Methods and Applications, (Springer, 2010). https://doi.org/10.1007/978-3-642-18466-6_3
19. Chen, S., Davis, S., Jiang, H., and Novobilski, A., Cuda-Based Genetic Algorithm on Traveling Salesman Problem', Computer and Information Science 2011, (Springer, 2011). https://doi.org/10.1007/978-3-642-21378-6_19
20. Sánchez, L.N.G., Armenta, J.J.T., and Ramírez, V.H.D., 'Parallel Genetic Algorithms on a Gpu to Solve the Travelling Salesman Problem', Difu100ci@ Revista en Ingeniería y Tecnología, UAZ, 2015, 8, (2). https://doi.org/10.1007/978-3-662-45049-9_96
M. Abbasi and M. Rafiee / IJE TRANSACTIONS A: Basics Vol. 31, No. 7, (July 2020) 1257-1265 1265
21. Kang, S., Kim, S.-S., Won, J., and Kang, Y.-M., 'Gpu-Based Parallel Genetic Approach to Large-Scale Travelling Salesman Problem', The Journal of Supercomputing, 2016, Vol. 72, No. 11, 4399-4414. https://doi.org/10.1007/s11227-016-1748-1
22. Moumen, Y., Abdoun, O., and Daanoun, A., 'Parallel Approach for Genetic Algorithm to Solve the Asymmetric Traveling Salesman Problems', in, Proceedings of the 2nd International Conference on Computing and Wireless Communication Systems, (ACM, 2017) https://doi.org/10.1145/3167486.3167510
23. Cekmez, U., Ozsiginan, M., and Sahingoz, O.K., 'Adapting the Ga Approach to Solve Traveling Salesman Problems on Cuda Architecture', in, Computational Intelligence and Informatics (CINTI), 2013 IEEE 14th International Symposium on, (IEEE, 2013) https://doi.org/10.1109/CINTI.2013.6705234
24. Radford, D. and Calvert, D., 'A Comparative Analysis of the Performance of Scalable Parallel Patterns Applied to Genetic Algorithms and Configured for Nvidia Gpus', Procedia Computer Science, Vol. 114, (2017), 65-72. https://doi.org/10.1016/j.procs.2017.09.009
25. Li, C.-C., Lin, C.-H., and Liu, J.-C., 'Parallel Genetic Algorithms on the Graphics Processing Units Using Island Model and Simulated Annealing', Advances in Mechanical Engineering, Vol. 9, No. 7, (2017), 12-25. https://doi.org/10.1177%2F1687814017707413
26. Saxena, R., Jain, M., Sharma, D., and Jaidka, S., 'A Review on Vanet Routing Protocols and Proposing a Parallelized Genetic Algorithm Based Heuristic Modification to Mobicast Routing for Real Time Message Passing', Journal of Intelligent & Fuzzy Systems, Vol. 36, No. 3, (2019), 2387-2398. https://doi.org/10.3233/JIFS-169950
27. NVIDIA. NVIDIA CUDA (Compute Unified Device Architecture) Programming Guide, Available: http://docs.nvidia.com/cuda/pdf/CUDA_C_Programming_Guide.pdf, (Accessed July 2020).
28. Jam, S., Shahbahrami, A., and Ziyabari, S., 'Parallel Implementation of Particle Swarm Optimization Variants Using Graphics Processing Unit Platform', International Journal of Engineering Transactions A: Basics, Vol 30, No. 1, (2017), 48-56. https://doi.ir/10.5829/idosi.ije.2017.30.01a.07
29. Yip, C.M. and Asaduzzaman, A., 'A Promising Cuda-Accelerated Vehicular Area Network Simulator Using Ns-3', in, Performance Computing and Communications Conference (IPCCC), 2014 IEEE International, (IEEE, 2014) https://doi.org/10.1109/PCCC.2014.7017048
30. Kim, C.G., Kim, J.G., and Lee, D.H., 'Optimizing Image Processing on Multi-Core Cpus with Intel Parallel Programming Technologies', Multimedia Tools and Applications, Vol. 68, No. 2, (2014), 237-251. https://doi.org/10.1007/s11042-011-0906-y
31. Reinders, J. 'Intel threading building blocks: outfitting C++ for multi-core processor parallelism', O'Reilly Media. Inc, 2007.
32. Hougardy, S. and Wilde, M., 'On the Nearest Neighbor Rule for the Metric Traveling Salesman Problem', Discrete Applied Mathematics, (2014). https://doi.org/10.1016/j.dam.2014.03.012
33. Groba, C., Sartal, A., and Vázquez, X.H., 'Solving the Dynamic Traveling Salesman Problem Using a Genetic Algorithm with Trajectory Prediction: An Application to Fish Aggregating Devices', Computers & Operations Research, Vol. 56, (2015), 22-32. https://doi.org/10.1016/j.cor.2014.10.012
34. Hussain, A. and Muhammad, Y.S., 'Trade-Off between Exploration and Exploitation with Genetic Algorithm Using a Novel Selection Operator', Complex & Intelligent Systems, (2019), 1-14. https://doi.org/0.1007/s40747-019-0102-7
35. Hassanat, A., Prasath, V., Abbadi, M., Abu-Qdari, S., and Faris, H., 'An Improved Genetic Algorithm with a New Initialization Mechanism Based on Regression Techniques', Information, Vol. 9, No. 7, (2018), 167. https://doi.org/10.3390/info9070167
36. Doughabadi, M.H., Bahrami, H., and Kolahan, F., 'Evaluating the Effects of Parameters Setting on the Performance of Genetic Algorithm Using Regression Modeling and Statistical Analysis', Journal of Industrial Engineering, University of Tehran, (2011), 61-68.
37. Contreras-Bolton, C. and Parada, V., 'Automatic Combination of Operators in a Genetic Algorithm to Solve the Traveling Salesman Problem', PloS One, Vol. 10, No. 9, (2015), e0137724-e0137724. https://doi.org/10.1371/journal.pone.0137724
38. VLSI-TSP-Collection, Available: http://www.math.uwaterloo.ca/tsp/vlsi/index.html, (Accessed July 2020).