A metaheuristic optimization algorithm for multimodal benchmark function in a GPU architecture

Javier Luis Mroginski; Hugo Guillermo Castro

doi:10.33434/cams.459423

EN

A metaheuristic optimization algorithm for multimodal benchmark function in a GPU architecture

Abstract

It is well known that the numerical solution of evolutionary systems and problems based on topological design requires a high computational power. In the last years, many parallel algorithms have been developed in order to improve its performance. Among them, genetic algorithms (GAs) are one of the most popular metaheuristic algorithms inspired by Darwin's evolution theory. From the High Performance Computing (HPC) point of view, the CUDA environment is probably the parallel computing platform and programming model that more heyday has had in recent years, mainly due to the low acquisition cost of graphics processing units (GPUs) compared to a cluster with similar functional characteristics. Consequently, the number of GPU-CUDAs present in the top 500 fastest supercomputers in the world is constantly growing. In this paper, a numerical algorithm developed in the NVIDIA CUDA platform capable of solving classical optimization functions usually employed as benchmarks is presented. The obtained results demonstrate that GPUs are a valuable tool for acceleration of GAs and may enable its use in much complex problems. Also, a sensitivity analysis is carried out in order to show the relative weight of each GA operator in the whole computational cost of the algorithm.

Keywords

CUDA environment,Genetic algorithm,Mathematical function optimization,GPU architecture,GPU architecture

References

[1] A. Aalaei, V. Kayvanfar, and H. Davoudpour. A multi-objective optimization for preemptive identical parallel machines scheduling problem. Computational and Applied Mathematics, pages doi:10.1007/s40314-015-0298-0, 2015.
[2] M. Abouali, J. Timmermans, J. E. Castillo, and B. Z. Su. A high performance GPU implementation of surface energy balance system (SEBS) based on CUDA-C. Environmental Modelling and Software, 41:134-138, 2013.
[3] D. H. Ackley. An empirical study of bit vector function optimization. In Lawrence Davis, editor, Genetic Algorithms and Simulated Annealing, Pitman, London, 1987, pages 170-204. 1987.
[4] E. Alba, G. Luque, C.A.C. Coello, and E.H. Luna. Comparative study of serial and parallel heuristics used to design combinational logic circuits. Optimization Methods and Software, 22:485-509, 2007.
[5] A. Belegundu and T. Chandrupatla. Optimization Concepts and Applications in Engineering. Prentice Hall,1999.
[6] A. Cano, A. Zafra, and S. Ventura. Speeding up the evaluation phase of GP classification algorithms on GPUs. Soft Computing, 16(2):187-202, 2012.
[7] S. D. Costarelli, M. A. Storti, R. R. Paz, L. D. Dalcin, and S. R. Idelsohn. GPGPU implementation of the BFECC algorithm for pure advection equations. Cluster Computing, 17(2):243-254, 2014.
[8] A. Danowitz, K. Kelley, J. Mao, J. P. Stevenson, and M. Horowitz. CPU DB: recording microprocessor history. Acm Queue, 10(4):10-27, 2012.
[9] D.P.S. dos Santos and J.K. Silva Formiga. Application of a genetic algorithm in orbital maneuvers. Computational and Applied Mathematics, 34:437-450, 2015.
[10] Anthony Gregerson. Implementing fast MRI gridding on GPUs via CUDA. Nvidia Tech. Report on Medical Imaging using CUDA, 2008.

[11] M. J. Harris. Real-time cloud simulation and rendering. University of North Carolina. Technical Report TR03-040, 2003.
[12] C. Lederman, R. Martin, and J. Cambier. Time-parallel solutions to differential equations via functional optimization. Computational and Applied Mathematics, pages doi:10.1007/s40314-016-0319-7, 2016.
[13] Daniel Lustig and Margaret Martonosi. Reducing GPU offload latency via fine-grained CPU-GPU synchronization. In Proceedings of the 2013 IEEE 19th International Symposium on High Performance Computer Architecture (HPCA), pages 354-365, Washington, DC, USA, 2013. IEEE Computer Society.
[14] J. L. Mroginski, P. A. Beneyto, G. Gutierrez, and H. A. Di Rado. A selective genetic algorithm for multiobjective optimization of cross sections in 3D trussed structures based on a spatial sensitivity analysis. Multidiscipline Modeling in Materials and Structures, 12:423-435, 2016.
[15] H. M¨uhlenbein, M. Schomisch, and J. Born. The parallel genetic algorithm as function optimizer. Parallel Computing, 17(6-7):619-632, 1991.
[16] J. Nickolls, I. Buck, M. Garland, and K. Skadron. Scalable parallel programming with CUDA. Queue, 6(2):40-53, 2008.
[17] NVIDIA Corporation. Cuda c programming guide, September 2015.
[18] NVIDIA Corporation. Cuda toolkit documentation v7.5, September 2015.
[19] R. R. Paz, M. A. Storti, H. G. Castro, and L. D. Dalcin. Using hybrid parallel programming techniques for the computation, assembly and solution stages in finite element codes. Latin American Applied Research, 41:365-377, 2011.
[20] R. R. Paz, M. A. Storti, L. D. Dalcin, H. G. Castro, and P. A. Kler. Fastmat: A C++ library for multi-index array computations. Advances in Engineering Software, 54:38-48, 2012.
[21] D. Robilliard, V. Marion-Poty, and C. Fonlupt. Genetic programming on graphics processing units. Genetic Programming and Evolvable Machines, 10(4):447-471, 2009.
[22] G. Sharma, A. Agarwala, and B. Bhattacharya. A fast parallel Gauss Jordan algorithm for matrix inversion using CUDA. Computers and Structures, 128:31-37, 2013.
[23] S. Siva Sathya and M.V. Radhika. Convergence of nomadic genetic algorithm on benchmark mathematical functions. Applied Soft Computing, 13(5):2759-2766, 2013.
[24] T. Tomczak, K. Zadarnowska, Z. Koza, M. Matyka, and L. Miroslaw. Acceleration of iterative Navier-Stokes solvers on graphics processing units. International Journal of Computational Fluid Dynamics, 27:201-209,2013.
[25] M. Ujald´on and J. Saltz. Exploiting parallelism on irregular applications using the GPU. In G.R. Joubert, W.E. Nagel, F.J. Peters, O. Plata, P. Tirado, and E. Zapata, editors, Parallel Computing: Current & Future Issues of High-End Computing, John von Neumann Institute for Computing, J¨ulich, (Germany), volume 33, pages 639-646, 2006.
[26] Y. Yang. A globally and quadratically convergent algorithm with efficient implementation for unconstrained optimization. Computational and Applied Mathematics, 34:1219-1236, 2015.
[27] Liu Yong, Kang Lishan, and D.J. Evans. The annealing evolution algorithm as function optimizer. Parallel Computing, 21(3):389-400, 1995.
[28] H. Zhang and M. Ishikawa. The performance verification of an evolutionary canonical particle swarm optimizer. Neural Networks, 23(4):510-516, 2010.
[29] K. Zhang, S. Yang, L. Li, and M. Qiu. Parallel genetic algorithm with opencl for traveling salesman problem. Communications in Computer and Information Science, 472:585-590, 2014.
[30] Y. Zhang, M. Sakamoto, and H. Furutani. Effects of population size and mutation rate on results of genetic algorithm. In 4th International Conference on Natural Computation (ICNC), volume 1, pages 70-75, 2008

Details

Primary Language

English

Subjects

Mathematical Sciences

Journal Section

Research Article

Authors

Javier Luis Mroginski ^*
0000-0001-7495-7735
Argentina

Hugo Guillermo Castro This is me
0000-0003-1715-1238
Argentina

Publication Date

September 30, 2018

Submission Date

September 12, 2018

Acceptance Date

September 19, 2018

Published in Issue

Year 2018 Volume: 1 Number: 1

DOI

https://doi.org/10.33434/cams.459423

IZ

https://izlik.org/JA74EG86ZJ

APA

Mroginski, J. L., & Castro, H. G. (2018). A metaheuristic optimization algorithm for multimodal benchmark function in a GPU architecture. Communications in Advanced Mathematical Sciences, 1(1), 67-83. https://doi.org/10.33434/cams.459423

AMA

1.Mroginski JL, Castro HG. A metaheuristic optimization algorithm for multimodal benchmark function in a GPU architecture. Communications in Advanced Mathematical Sciences. 2018;1(1):67-83. doi:10.33434/cams.459423

Chicago

Mroginski, Javier Luis, and Hugo Guillermo Castro. 2018. “A Metaheuristic Optimization Algorithm for Multimodal Benchmark Function in a GPU Architecture”. Communications in Advanced Mathematical Sciences 1 (1): 67-83. https://doi.org/10.33434/cams.459423.

EndNote

Mroginski JL, Castro HG (September 1, 2018) A metaheuristic optimization algorithm for multimodal benchmark function in a GPU architecture. Communications in Advanced Mathematical Sciences 1 1 67–83.

IEEE

[1]J. L. Mroginski and H. G. Castro, “A metaheuristic optimization algorithm for multimodal benchmark function in a GPU architecture”, Communications in Advanced Mathematical Sciences, vol. 1, no. 1, pp. 67–83, Sept. 2018, doi: 10.33434/cams.459423.

ISNAD

Mroginski, Javier Luis - Castro, Hugo Guillermo. “A Metaheuristic Optimization Algorithm for Multimodal Benchmark Function in a GPU Architecture”. Communications in Advanced Mathematical Sciences 1/1 (September 1, 2018): 67-83. https://doi.org/10.33434/cams.459423.

JAMA

1.Mroginski JL, Castro HG. A metaheuristic optimization algorithm for multimodal benchmark function in a GPU architecture. Communications in Advanced Mathematical Sciences. 2018;1:67–83.

MLA

Mroginski, Javier Luis, and Hugo Guillermo Castro. “A Metaheuristic Optimization Algorithm for Multimodal Benchmark Function in a GPU Architecture”. Communications in Advanced Mathematical Sciences, vol. 1, no. 1, Sept. 2018, pp. 67-83, doi:10.33434/cams.459423.

Vancouver

1.Javier Luis Mroginski, Hugo Guillermo Castro. A metaheuristic optimization algorithm for multimodal benchmark function in a GPU architecture. Communications in Advanced Mathematical Sciences. 2018 Sep. 1;1(1):67-83. doi:10.33434/cams.459423

The published articles in CAMS are licensed under a Creative Commons Attribution-NonCommercial 4.0 International License..

Abstract

A metaheuristic optimization algorithm for multimodal benchmark function in a GPU architecture

Abstract

Keywords

References

Details

Primary Language

Subjects

Journal Section

Authors

Publication Date

Submission Date

Acceptance Date

Published in Issue

DOI

IZ

Cite