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

Year 2018, Volume: 1 Issue: 1, 67 - 83, 30.09.2018

Javier Luis Mroginski , Hugo Guillermo Castro

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

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