A coarse-grained parallelization of genetic algorithms

(1) Muhamad Radzi Rathomi Mail (Department of Informatics, Universitas Maritim Raja Ali Haji, Indonesia)
(2) * Reza Pulungan Mail (Computer Science and Electronics Department, Universitas Gadjah Mada, Indonesia)
*corresponding author


Abstract


Genetic algorithms are frequently used to solve optimization problems. Nowadays, the problems to be solved by genetic algo-rithms become increasingly complex and require large computa-tion times. One solution to speed up genetic algorithm processing is to use parallelization. In this paper, a new method to increase the speed of genetic algorithms in finding the optimal solutions by parallelizing the processing of subpopulations is proposed. The proposed parallelization method is coarse-grained and em-ploys two levels of parallelization: message passing with MPI and Single Instruction Multiple Threads with GPU. Experimental results show that the accuracy of the proposed parallel genetic algorithm is similar to the sequential genetic algorithm. Parallel-ization with coarse-grained method, however, can improve the processing speed of genetic algorithms. Convergence speed of the parallel genetic algorithm is also much better than the se-quential genetic algorithm.

Keywords


Genetic algorithms; parallelization; coarse-grained; MPI ;GPU

   

DOI

https://doi.org/10.26555/ijain.v4i1.137
   

Article metrics

Abstract views : 177

   

Cite

   

References


P. S. Oliveto and C. Witt, “Improved time complexity analysis of the simple genetic algorithm,” Theoretical Computer Science, vol. 605, pp. 21-41, 2015. [Online]. Available: https://doi.org/ 10.1016/j.tcs.2015.01.002

Y. Y. Liu and S. Wang, “A scalable parallel genetic algorithm for the generalized assignment problem,” Parallel Computing, vol. 46, pp. 98–119, 2015. [Online]. Available: http://www.sciencedirect.com/ science/article/pii/S0167819114000519

S. Zhang and Z. He, “Implementation of parallel genetic algorithm based on CUDA,” in Advances in Computation and Intelligence (ISICA 2009). Springer Berlin Heidelberg, 2009, pp. 24–30. [Online]. Available: http://dx.doi.org/10.1007/978-3-642-04843-2_4

Z. Skolicki and K. De Jong, “The influence of migration sizes and intervals on island models,” in Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation (GECCO’05). ACM, 2005, pp. 1295–1302. [Online]. Available: http://doi.acm.org/10.1145/1068009.1068219

W. Li and Y. Huang, “A distributed parallel genetic algorithm oriented adaptive migration strategy,” in Natural Computation (ICNC), 8th International Conference on, 2012, pp. 592–595.

L. Falahiazar, M. Teshnehlab, and A. Falahiazar, “Parallel genetic algorithm based on a new migration strategy,” in Recent Advances in Computing and Software Systems (RACSS), International Conference on, 2012, pp. 37–41.

A.-R. Hedar, A. Abdelsamee, A. Fouad, and S. T. Amin, “Advanced parallel genetic algorithm with gene matrix for global optimization,” Advanced Machine Learning Technologies and Applications (AMLTA 2012), Springer Berlin Heidelberg, 2012, pp. 295–303. [Online]. Available: http://dx.doi.org/10.1007/ 978-3-642-35326-0_30

A. J. Umbarkar, M. S. Joshi, and W.-C. Hong, “Multithreaded parallel dual population genetic algorithm (MPDPGA) for unconstrained function optimizations on multi-core system,” Appl. Math. Comput., vol. 243, pp. 936–949, 2014. [Online]. Available: http://dx.doi.org/10.1016/j.amc.2014.06.033

F. Lu, Y. Ge, and L. Gao, “A novel genetic algorithm with multiple sub-population parallel search mechanism,” in 6th International Conference on Natural Computation, vol. 5, 2010, pp. 2249–2253.

Z. R. Wang, T. Ju, D. W. Cui, and X. H. Hei, “A study of hybrid parallel genetic algorithm model,” in Natural Computation (ICNC), 7th International Conference on, vol. 2, 2011, pp. 1038–1042.

“The OpenMP API specification for parallel programming,” 2017. [Online]. Available: http://openmp.org/wp/

M. Wahib, A. Munawar, M. Munetomo, and K. Akama, “Optimization of parallel genetic algorithms for nVidia GPUs,” in 2011 IEEE Congress of Evolutionary Computation (CEC), 2011, pp. 803–811.

F. M. Johar, F. A. Azmin, M. K. Suaidi, A. S. Shibghatullah, B. H. Ahmad, S. N. Salleh, M. Z. A. A. Aziz, and M. M. Shukor, “A review of genetic algorithms and parallel genetic algorithms on graphics processing unit (GPU),” in Control System, Computing and Engineering (ICCSCE), 2013 IEEE International Conference on, 2013, pp. 264–269.

“CUDA parallel computing platform,” 2017. [Online]. Available: http://www.nvidia.com/object/ cuda_home_new.html

J. O. C. Millan, V. H. A. Calvo, R. M. P. Chaves, “Quadratic assignment problem (QAP) on GPU through a master-slave PGA,” Vision Electronica, 2016, vol. 10, issue 2, pp. 220-231, 2016. [Online]. Available: https://dialnet.unirioja.es/descarga/articulo/6081873.pdf

N. Hou, F. He, Y. Zhou, Y. Chen, X. Yan, “A parallel genetic algorithm with dispersion correction for HW/SW partitioning on multi-core CPU and many-core GPU”, IEEE Access, vol. 6, pp. 883-898, 2018. [Online]. Available: https//doi.org/10.1109/ACCESS.2017.2776295

C. Li, C. Lin, J. Liu, “Parallel genetic algorithm on the graphics processing units using island model and simulated annealing”, Advances in Mechanical Engineering, 2017, vol. 9, issue 7, 2017. [Online]. Available: https//doi.org/10.1177/1687814017707413

B. Barney, Introduction to Parallel Computing. Lawrence Livermore National Laboratory, 2017. [Online]. Available: https://computing.llnl.gov/tutorials/parallel_comp/

R. Yusof, M. Khalid, G. T. Hui, S. M. Yusof, and M. F. Othman, “Solving job shop scheduling problem using a hybrid parallel micro genetic algorithm,” Applied Soft Computing, vol. 11, no. 8, pp. 5782–5792, 2011. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S1568494611000901

D. C. Mattfeld and R. J. Vaessens, “OR-library: a set of 82 JSP test instances,” 2017. [Online]. Available: http://people.brunel.ac.uk/∼mastjjb/jeb/orlib/files/jobshop1.txt




Copyright (c) 2018

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

___________________________________________________________
International Journal of Advances in Intelligent Informatics
ISSN 2442-6571  (print) | 2548-3161 (online)
Organized by Informatics Department - Universitas Ahmad Dahlan , and UTM Big Data Centre - Universiti Teknologi Malaysia
Published by Universitas Ahmad Dahlan
W : http://ijain.org
E : info@ijain.org, andri.pranolo@tif.uad.ac.id (paper handling issues)
     ijain@uad.ac.id, andri.pranolo.id@ieee.org (publication issues)

View IJAIN Stats

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0