Skip to main content
SpringerLink
Log in

Gravitational search algorithm using CUDA: a case study in high-performance metaheuristics

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

Many scientific and technical problems with massive computation requirements could benefit from the graphics processing units (GPUs) using compute unified device architecture (CUDA). Gravitational search algorithm (GSA) is a population-based metaheuristic which can be effectively implemented on GPU to reduce the execution time. Nonetheless, the performance improvement depends strongly on the process used to adapt the algorithm into CUDA environment. In this paper, we discuss possible approaches to parallelize GSA on graphics hardware using CUDA. An in-depth study of the computation efficiency of parallel algorithms and capability to effectively exploit the architecture of GPU is performed. Additionally, a comparative study of parallel and sequential GSA was carried out on a set of standard benchmark optimization functions. The results show a significant speedup while maintaining results quality which re-emphasizes the utility of CUDA-based implementation for complex and computationally intensive parallel applications.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15

Similar content being viewed by others

References

  1. Alba E, Luque G (2006) Evaluation of parallel metaheuristics. Lect Notes Comput Sci 4193:9–14

    Google Scholar 

  2. Calazan RM, Nedjah N, de Macedo Mourelle L (2012) Swarm grid: a proposal for high performance of parallel particle swarm optimization using GPGPU. In: Computational science and its applications-ICCSA 2012. Springer, Berlin, pp 148–160

  3. Calazan RM, Nedjah N, de Macedo Mourelle L (2013) Parallel GPU-based implementation of high dimension particle swarm optimizations. In: IEEE Fourth Latin American Symposium on Circuits and systems (LASCAS), 2013, pp 1–4

  4. Cárdenas-Montes M, Vega-Rodríguez MA, Rodríguez-Vázquez JJ, Gómez-Iglesias A (2012) A GPU-based evaluation to accelerate particle swarm algorithm. In: Computer aided systems theory-EUROCAST 2011. Springer, Berlin, pp 272–279

  5. Charles JS, Potok TE, Patton R, Cui X (2008) Flocking-based document clustering on the graphics processing unit. Springer, Berlin

    Book  Google Scholar 

  6. Chen Z, Yuan X, Tian H, Ji B (2014) Improved gravitational search algorithm for parameter identification of water turbine regulation system. Energy Convers Manag 78:306–315

    Article  Google Scholar 

  7. de P Veronese L, Krohling RA (2009) Swarm’s flight: accelerating the particles using C-CUDA. In: IEEE Congress on Evolutionary computation, 2009, pp 3264–3270

  8. Formato RA (2008) Central force optimization: a new nature inspired computational framework for multidimensional search and optimization. In: Nature Inspired Cooperative Strategies for Optimization (NICSO 2007). Springer, Berlin, pp 221–238

  9. Gao S, Chai H, Chen B, Yang G (2013) Hybrid gravitational search and clonal selection algorithm for global optimization. In: Advances in swarm intelligence. Springer, Berlin, pp 1–10

  10. Glodberg DE (1989) Genetic algorithms in search, optimization, and machine learning. Addion wesley, USA

    Google Scholar 

  11. Gotshall S, Rylander B (2008) Optimal population size and the genetic algorithm. Population 100(400):900

    Google Scholar 

  12. Green II RC, Wang L, Alam M, Formato RA (2012) Central force optimization on a GPU: a case study in high performance metaheuristics. J Supercomput 62(1):378–398

    Article  Google Scholar 

  13. Harris M (2007) Optimizing parallel reduction in CUDA. NVIDIA Developer Technology

  14. Kennedy J, Eberhart R (1995) Particle swarm optimization. In: IEEE International Conference on Neural Networks, vol 4, pp 1942–1948

  15. Kumar J, Singh L, Paul S (2013) GPU based parallel cooperative particle swarm optimization using C-CUDA: a case study. In: IEEE International Conference on Fuzzy Systems (FUZZ), 2013, pp 1–8

  16. Li J-M, Wang X-J, He R-S, Chi Z-X (2007) An efficient fine-grained parallel genetic algorithm based on GPU-accelerated. In: Proceedings of the 2007 IFIP International Conference on Network and Parallel Computing Workshops, pp 855–862

  17. Li J, Wan D, Chi Z (2007) An efficient fine-grained parallel particle swarm optimization method based on GPU-acceleration. Int J Innov Comput Inform Control 3(6):1707–1714

    Google Scholar 

  18. Li-Ping Z, Huan-Jun Y, Shang-Xu H (2005) Optimal choice of parameters for particle swarm optimization. J Zhejiang Univ Sci A 6(6):528–534

    Google Scholar 

  19. Mallick S, Ghoshal SP, Acharjee P, Thakur SS (2013) Optimal static state estimation using improved particle swarm optimization and gravitational search algorithm. Int J Electr Power Energy Syst 52:254–265

    Article  Google Scholar 

  20. Mussi L, Daolio F, Cagnoni S (2011) Evaluation of parallel particle swarm optimization algorithms within the CUDA architecture. Inform Sci 181(20):4642–4657

    Article  Google Scholar 

  21. Mussi L, Nashed YSG, Cagnoni S (2011) GPU-based asynchronous particle swarm optimization. In: Proceedings of the 13th annual conference on Genetic and evolutionary computation, pp 1555–1562. ACM

  22. CUDA Nvidia (2013) C programming guide 5.5. NVIDIA Corporation, USA

    Google Scholar 

  23. Pedersen Magnus EH (2010) Good parameters for particle swarm optimization. Hvass Lab., Copenhagen, Denmark, Tech. Rep. HL1001

  24. Rashedi E, Nezamabadi-Pour H, Saryazdi S (2009) GSA: a gravitational search algorithm. Inform Sci 179(13):2232–2248

    Article  MATH  Google Scholar 

  25. Rashedi E, Nezamabadi-Pour H, Saryazdi S (2011) Filter modeling using gravitational search algorithm. Eng Appl Artif Intell 24(1):117–122

    Article  Google Scholar 

  26. Rong G, Liu G, Zheng M, Sun A, Tian Y, Wang H (2013) Parallel gravitation field algorithm based on the CUDA platform. J Inform Comput Sci 10:3635–3644

    Article  Google Scholar 

  27. CUDA Toolkit (2013) Curand guide 5.5. NVIDIA Corporation, USA

    Google Scholar 

  28. Wong M-L, Wong T-T, Fok K-L (2005) Parallel evolutionary algorithms on graphics processing unit. In: The IEEE Congress on Evolutionary Computation, 2005, vol 3, pp 2286–2293

  29. Zarrabi A, Samsudin K (2014) Task scheduling on computational grids using gravitational search algorithm. Cluster Comput 17(3):1001–1011

  30. Zhou Y, Tan Y (2009) Gpu-based parallel particle swarm optimization. In: IEEE Congress on Evolutionary Computation, 2009. CEC’09, pp 1493–1500

  31. Zhou Y, Tan Y (2010) Particle swarm optimization with triggered mutation and its implementation based on GPU. In: Proceedings of the 12th annual conference on Genetic and evolutionary computation, pp 1–8. ACM

Download references

Author information

Authors and Affiliations

  1. Department of Computer and Communication Systems Engineering, Faculty of Engineering, University Putra Malaysia (UPM), 43400, Serdang, Selangor, Malaysia

    Amirreza Zarrabi & Khairulmizam Samsudin

  2. MIMOS Berhad, Technology Park Malaysia, 5700, Kuala Lumpur, Malaysia

    Amirreza Zarrabi & Ettikan K. Karuppiah

Authors
  1. Amirreza Zarrabi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Khairulmizam Samsudin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ettikan K. Karuppiah
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Amirreza Zarrabi.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zarrabi, A., Samsudin, K. & Karuppiah, E.K. Gravitational search algorithm using CUDA: a case study in high-performance metaheuristics. J Supercomput 71, 1277–1296 (2015). https://doi.org/10.1007/s11227-014-1360-1

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-014-1360-1

Keywords

Search

Navigation