Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Accelerating continuous GRASP with a GPU

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

Abstract

This work proposes a GPU-based parallelization for the Continuous GRASP (C-GRASP), a local search metaheuristic for finding cost-efficient solutions to continuous global optimization problems subject to box constraints. C-GRASP has demonstrated competitive performance on several well-known multimodal test functions as well as on difficult real-world problems, hence a GPU parallelization might increase even further the applicability of this metaheuristic. Although GPU parallelizations have been proposed for many metaheuristics, little has been done for C-GRASP. We conduct an extensive set of experiments and compare our proposal with state-of-the-art GPU parallelizations of other metaheuristics, such as Scatter Search and Differential Evolution. We also compare our GPU approach with two other C-GRASP implementations: a sequential version and a multi-core version. Experimental results show our GPU C-GRASP outperforms other GPU-based metaheuristics and the multi-core C-GRASP. Besides, we observed speedups of up to \(154{\times }\) over the sequential version.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. The source code of our implementation can be downloaded at https://sites.google.com/site/nogueirabruno/software.

  2. Functions in which the sequential C-GRASP finds an optimal solution in less than 1 ms were omitted from this table.

References

  1. Resende MG, Ribeiro CC (2016) Optimization by GRASP. Springer, Berlin

    Book  Google Scholar 

  2. Hirsch MJ, Meneses C, Pardalos PM, Resende MG (2007) Global optimization by continuous GRASP. Optim Lett 1(2):201–212

    Article  MathSciNet  Google Scholar 

  3. Hirsch MJ, Pardalos PM, Resende MG (2010) Speeding up continuous GRASP. Eur J Oper Res 205(3):507–521

    Article  Google Scholar 

  4. Hirsch MJ, Pardalos PM, Resende MG (2006) Sensor registration in a sensor network by continuous GRASP. In: Military Communications Conference, 2006, MILCOM 2006, IEEE. IEEE, pp 1–6

  5. Hirsch MJ, Pardalos PM, Resende MG (2009) Solving systems of nonlinear equations with continuous GRASP. Nonlinear Anal Real World Appl 10(4):2000–2006

    Article  MathSciNet  Google Scholar 

  6. Hirsch MJ, Meneses CN, Pardalos PM, Ragle M, Resende MG (2007) A continuous grasp to determine the relationship between drugs and adverse reactions. In: AIP Conference Proceedings, Vol. 953, AIP, pp 106–121

  7. Macharet DG, Neto AA, da Camara Neto VF, Campos MF (2011) Nonholonomic path planning optimization for dubins’ vehicles. In: 2011 IEEE International Conference on Robotics and Automation (ICRA). IEEE, pp 4208–4213

  8. Neto JXV, Reynoso-Meza G, Ruppel TH, Mariani VC, dos Santos Coelho L (2017) Solving non-smooth economic dispatch by a new combination of continuous grasp algorithm and differential evolution. Int J Electr Power Energy Syst 84:13–24

    Article  Google Scholar 

  9. Queiroga E, Subramanian A, Lucídio dos Anjos FC (2018) Continuous greedy randomized adaptive search procedure for data clustering. Appl Soft Comput 72:43–55

    Article  Google Scholar 

  10. Nogueira B, Pinheiro RG (2018) A CPU–GPU local search heuristic for the maximum weight clique problem on massive graphs. Comput Oper Res 90:232–248

    Article  MathSciNet  Google Scholar 

  11. Nogueira B, Pinheiro RG (2019) A GPU based local search algorithm for the unweighted and weighted maximum s-plex problems. Ann Oper Res. https://doi.org/10.1007/s10479-019-03159-5

    Article  Google Scholar 

  12. Alekseeva E, Mezmaz M, Tuyttens D, Melab N (2017) Parallel multi-core hyper-heuristic GRASP to solve permutation flow-shop problem. Concurr Comput Pract Exp 29(9):e3835

    Article  Google Scholar 

  13. Coelho I, Munhoz P, Ochi L, Souza M, Bentes C, Farias R (2016) An integrated CPU–GPU heuristic inspired on variable neighbourhood search for the single vehicle routing problem with deliveries and selective pickups. Int J Prod Res 54(4):945–962

    Article  Google Scholar 

  14. Melab N, Luong T, Boufaras K, Talbi E.-G (2011) Towards paradisEO-MO-GPU: a framework for GPU-based local search metaheuristics. In: International Work-Conference on Artificial Neural Networks. Springer, pp 401–408

  15. Nashed YS, Ugolotti R, Mesejo P, Cagnoni S (2012) libcudaoptimize: an open source library of GPU-based metaheuristics. In: Proceedings of the 14th Annual Conference Companion on Genetic and Evolutionary Computation. ACM, pp 117–124

  16. Andrade L, Xavier R, Cabral L, Formiga A, Parallel construction for continuous grasp optimization on GPUs. In: Anais do XLVI Simpósio Brasileiro de Pesquisa Operacional, pp 2393–2404

  17. Harris M (2007) Optimizing parallel reduction in CUDA. NVIDIA Dev Technol 2(4):70

    Google Scholar 

  18. Jamil M, Yang X-S (2013) A literature survey of benchmark functions for global optimisation problems. Int J Math Model Numer Optim 4(2):150–194

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Universidade Federal de Alagoas, Maceió, Brazil

    Bruno Nogueira

  2. Universidade Federal de Pernambuco, Recife, Brazil

    Eduardo Tavares

  3. Universidade Federal Rural de Pernambuco, Recife, Brazil

    Jean Araujo & Gustavo Callou

Authors
  1. Bruno Nogueira
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Eduardo Tavares
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jean Araujo
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Gustavo Callou
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bruno Nogueira.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Nogueira, B., Tavares, E., Araujo, J. et al. Accelerating continuous GRASP with a GPU. J Supercomput 75, 5741–5759 (2019). https://doi.org/10.1007/s11227-019-02833-6

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-019-02833-6

Keywords

Search

Navigation