(Department of Informatics, Universitas Maritim Raja Ali Haji, Indonesia)(2) * Reza Pulungan
(Computer Science and Electronics Department, Universitas Gadjah Mada, Indonesia)*corresponding author
AbstractGenetic algorithms are frequently used to solve optimization problems. However, the problems become increasingly complex and time consuming. One solution to speed up the genetic algorithm processing is to use parallelization. The proposed parallelization method is coarse-grained and employs two levels of parallelization: message passing with MPI and Single Instruction Multiple Threads with GPU. Experimental results show that the accuracy of the proposed approach is similar to the sequential genetic algorithm. Parallelization with coarse-grained method, however, can improve the processing and convergence speed of genetic algorithms.
KeywordsGenetic algorithms; Parallelization; Coarse-grained; MPI; GPU
|
DOIhttps://doi.org/10.26555/ijain.v4i1.137 |
Article metricsAbstract views : 4202 | PDF views : 575 |
Cite |
Full Text Download
|
References
[1] P. S. Oliveto and C. Witt, “Improved time complexity analysis of the simple genetic algorithm,” Theoretical Comput. Sci., vol. 605, pp. 21-41, 2015, doi: https://doi.org/ 10.1016/j.tcs.2015.01.002.
[2] Y. Y. Liu and S. Wang, “A scalable parallel genetic algorithm for the generalized assignment problem,” Parallel Computing, vol. 46, pp. 98–119, 2015, doi: https://doi.org/10.1016/j.parco.2014.04.008.
[3] 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, doi: http://dx.doi.org/10.1007/978-3-642-04843-2_4.
[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, doi: http://doi.acm.org/10.1145/1068009.1068219.
[5] 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, doi: https://doi.org/10.1109/ICNC.2012.6234584.
[6] 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, doi: https://doi.org/10.1109/RACSS.2012.6212694.
[7] 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, doi: http://dx.doi.org/10.1007/ 978-3-642-35326-0_30.
[8] 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, doi: http://dx.doi.org/10.1016/j.amc.2014.06.033.
[9] F. Lu, Y. Ge, and L. Gao, “A novel genetic algorithm with multiple sub-population parallel search mechanism,” in Natural Computation (ICNC), 2010 Sixth International Conference on, vol. 5, 2010, pp. 2249–2253, doi: https://doi.org/10.1109/ICNC.2010.5584437.
[10] 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, doi: https://doi.org/10.1109/ICNC.2011.6022186.
[11] OpenMP, “The OpenMP API specification for parallel programming,” 2017, available at: http://openmp.org/.
[12 M. Wahib, A. Munawar, M. Munetomo, and K. Akama, “Optimization of parallel genetic algorithms for nVidia GPUs,” in Evolutionary Computation (CEC), 2011 IEEE Congress on, 2011, pp. 803–811, doi: https://doi.org/10.1109/CEC.2011.5949701.
[13] 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, doi: https://doi.org/10.1109/ICCSCE.2013.6719971.
[14] NVidia, “CUDA parallel computing platform,” 2017, available at: https://developer.nvidia.com/cuda-zone.
[15] 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, available at: https://dialnet.unirioja.es/descarga/articulo/6081873.pdf.
[16] 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, doi: https://doi.org/10.1109/ACCESS.2017.2776295.
[17] 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, doi: https://doi.org/10.1177/1687814017707413.
[18] B. Barney, Introduction to Parallel Computing. Lawrence Livermore National Laboratory, 2017, available at: https://computing.llnl.gov/tutorials/parallel_comp/.
[19] M. R. Rathomi, “Peningkatan kecepatan pemrosesan algoritma genetika dengan paralelisasi menggunakan metode coarse-grained,” Master’s thesis, Universitas Gadjah Mada, Indonesia, 2015, available at: https://goo.gl/Bsi7s5.
[20] 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, doi: https://doi.org/10.1016/j.asoc.2011.01.046.
[21] D. C. Mattfeld and R. J. Vaessens, “OR-library: a set of 82 JSP test instances,” 2017, available at: http://people.brunel.ac.uk/~mastjjb/jeb/info.html.
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 UAD and ASCEE Computer Society
Published by Universitas Ahmad Dahlan
W: http://ijain.org
E: info@ijain.org (paper handling issues)
andri.pranolo.id@ieee.org (publication issues)
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0