[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Hybrid parallel multimethod hyperheuristic for mixed-integer dynamic optimization problems in computational systems biology

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

Abstract

This paper describes and assesses a parallel multimethod hyperheuristic for the solution of complex global optimization problems. In a multimethod hyperheuristic, different metaheuristics cooperate to outperform the results obtained by any of them isolated. The results obtained show that the cooperation of individual parallel searches modifies the systemic properties of the hyperheuristic, achieving significant performance improvements versus the sequential and the non-cooperative parallel solutions. Here we present and evaluate a hybrid parallel scheme of the multimethod, using both message-passing (MPI) and shared memory (OpenMP) models. The hybrid parallelization allows to achieve a better trade-off between performance and computational resources, through a compromise between diversity (number of islands) and intensity (number of threads per island). For the performance evaluation, we considered the general problem of reverse engineering nonlinear dynamic models in systems biology, which yields very large mixed-integer dynamic optimization problems. In particular, three very challenging problems from the domain of dynamic modeling of cell signaling were used as case studies. In addition, experiments have been carried out in a local cluster, a large supercomputer and a public cloud, to show the suitability of the proposed solution in different execution platforms.

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
£29.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 includes VAT (United Kingdom)

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

Similar content being viewed by others

Notes

  1. www.dreamchallenges.org.

References

  1. Alba E (2005) Parallel metaheuristics: a new class of algorithms. Wiley, Hoboken

    Book  MATH  Google Scholar 

  2. Alba E, Luque G, Nesmachnow S (2013) Parallel metaheuristics: recent advances and new trends. Int Trans Oper Res 20(1):1–48

    Article  MATH  Google Scholar 

  3. Aldridge BB, Burke JM, Lauffenburger DA, Sorger PK (2006) Physicochemical modelling of cell signalling pathways. Nat Cell Biol 8(11):1195–1203

    Article  Google Scholar 

  4. Alexopoulos LG, Saez-Rodriguez J, Cosgrove BD, Lauffenburger DA, Sorger PK (2010) Networks inferred from biochemical data reveal profound differences in toll-like receptor and inflammatory signaling between normal and transformed hepatocytes. Mol Cell Proteom 9(9):1849–1865

    Article  Google Scholar 

  5. Almeida F, Giménez D, López-Espín JJ (2011) A parameterized shared-memory scheme for parameterized metaheuristics. J Supercomput 58(3):292–301

    Article  Google Scholar 

  6. Balsa-Canto E, Banga JR (2011) AMIGO, a toolbox for advanced model identification in systems biology using global optimization. Bioinformatics 27(16):2311–2313

    Article  Google Scholar 

  7. Banga JR (2008) Optimization in computational systems biology. BMC Syst Biol 2(1):47

    Article  MathSciNet  Google Scholar 

  8. Burke EK, Gendreau M, Hyde M, Kendall G, Ochoa G, Özcan E, Qu R (2013) Hyper-heuristics: a survey of the state of the art. J Oper Res Soc 64(12):1695–1724

    Article  Google Scholar 

  9. CESGA: Centro de supercomputación de galicia. http://www.cesga.es. Accessed Apr 2019

  10. Chachuat B, Singer A, Barton P (2006) Global methods for dynamic optimization and mixed-integer dynamic optimization. Ind Eng Chem Res 45(25):8373–8392

    Article  Google Scholar 

  11. Chen X, Ong YS, Lim MH, Tan KC (2011) A multi-facet survey on memetic computation. IEEE Trans Evol Comput 15(5):591–607

    Article  Google Scholar 

  12. Crainic TG (2017) Parallel meta-heuristic and cooperative search. Technical Report, CIRRELT-2017-58, Universite du Quebec a Montreal

  13. Dean J, Ghemawat S (2004) MapReduce: simplified data processing on large clusters. In: The 6th USENIX Symposium on Operating Systems Design and Implementation

  14. Egea JA, Balsa-Canto E, García MSG, Banga JR (2009) Dynamic optimization of nonlinear processes with an enhanced scatter search method. Ind Eng Chem Res 48(9):4388–4401

    Article  Google Scholar 

  15. Evangelinos C, Hill C (2008) Cloud computing for parallel scientific HPC applications: feasibility of running coupled atmosphere-ocean climate models on amazon’s EC2. In: 1st Workshop on Cloud Computing and Its Applications (CCA’08), pp 1–6

  16. Exler O, Lehmann T, Schittkowski K (2012) A comparative study of sqp-type algorithms for nonlinear and nonconvex mixed-integer optimization. Math Program Comput 4(4):383–412

    Article  MathSciNet  MATH  Google Scholar 

  17. Exler O, Schittkowski K (2007) A trust region SQP algorithm for mixed-integer nonlinear programming. Optim Lett 1(3):269–280

    Article  MathSciNet  MATH  Google Scholar 

  18. Expósito RR, Taboada GL, Ramos S, Touriño J, Doallo R (2013) Performance analysis of HPC applications in the cloud. Future Gener Comput Syst 29(1):218–229

    Article  Google Scholar 

  19. González P, Pardo XC, Penas DR, Teijeiro D, Banga JR, Doallo R (2017) Using the cloud for parameter estimation problems: comparing spark vs MPI with a case-study. In: The 17th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing

  20. González P, Penas DR, Pardo XC, Banga JR, Doallo R (2018) Multimethod optimization for reverse engineering of complex biological networks. In: Proceedings of the 6th International Workshop on Parallelism in Bioinformatics, PBio 2018, pp 11–18

  21. González P, Penas DR, Pardo XC, Banga JR, Doallo R (2018) Multimethod optimization in the cloud: a case study in systems biology modelling. Concurr Comput Practice Exp 30(12):e4488

    Article  Google Scholar 

  22. Grobler J, Engelbrecht AP, Kendall G, Yadavalli V (2010) Alternative hyper-heuristic strategies for multi-method global optimization. In: The 2010 IEEE Congress on Evolutionary Computation (CEC). IEEE, pp 1–8

  23. Hansen N, Auger A, Finck S, Ros R (2009) Real-parameter black-box optimization benchmarking 2009: experimental setup. Technical Report RR-6828, INRIA

  24. Henriques D, Rocha M, Saez-Rodriguez J, Banga JR (2015) Reverse engineering of logic-based differential equation models using a mixed-integer dynamic optimization approach. Bioinformatics 31(18):2999–3007

    Article  Google Scholar 

  25. Hill SM, Heiser LM, Cokelaer T, Unger M, Nesser NK, Carlin DE, Zhang Y, Sokolov A, Paull EO, Wong CK et al (2016) Inferring causal molecular networks: empirical assessment through a community-based effort. Nat Methods 13(4):310–318

    Article  Google Scholar 

  26. Jin C, Vecchiola C, Buyya R (2008) MRPGA: an extension of MapReduce for parallelizing genetic algorithms. In: The 2008 IEEE Fourth International Conference on eScience. IEEE, pp 214–221

  27. Lee WP, Hsiao YT, Hwang WC (2014) Designing a parallel evolutionary algorithm for inferring gene networks on the cloud computing environment. BMC Syst Biol 8(1):5

    Article  Google Scholar 

  28. Luke S (2009) Essentials of metaheuristics, vol 113. Lulu, Raleigh

    Google Scholar 

  29. MacNamara A, Terfve C, Henriques D, Bernabé BP, Saez-Rodriguez J (2012) State-time spectrum of signal transduction logic models. Phys Biol 9(4):045003

    Article  Google Scholar 

  30. McNabb AW, Monson CK, Seppi KD (2007) Parallel PSO using MapReduce. In: The 2007 IEEE Congress on Evolutionary Computation (CEC). IEEE, pp 7–14

  31. Napper J, Bientinesi P (2009) Can cloud computing reach the top500? In: Proceedings of the Combined Workshops on UnConventional High Performance Computing Workshop Plus Memory Access Workshop. ACM, pp 17–20

  32. Olorunda O, Engelbrecht AP (2009) An analysis of heterogeneous cooperative algorithms. In: The 2009 IEEE Congress on Evolutionary Computation (CEC). IEEE, pp 1562–1569

  33. Ostermann S, Iosup A, Yigitbasi N, Prodan R, Fahringer T, Epema D (2008) An early performance analysis of cloud computing services for scientific computing. Technical Report. Delft University of Technology

  34. Penas D, Banga J, González P, Doallo R (2015) Enhanced parallel differential evolution algorithm for problems in computational systems biology. Appl Soft Comput 33:86–99

    Article  Google Scholar 

  35. Penas D, González P, Egea JA, Doallo R, Banga J (2017) Parameter estimation in large-scale systems biology models: a parallel and self-adaptive cooperative strategy. BMC Bioinform 18(1):52

    Article  Google Scholar 

  36. Penas DR, Henriques D, González P, Doallo R, Saez-Rodriguez J, Banga JR (2017) A parallel metaheuristic for large mixed-integer dynamic optimization problems, with applications in computational biology. Plos One 12(8):e0182186

    Article  Google Scholar 

  37. Peng F, Tang K, Chen G, Yao X (2010) Population-based algorithm portfolios for numerical optimization. IEEE Trans Evolut Comput 14(5):782–800

    Article  Google Scholar 

  38. Prill RJ, Saez-Rodriguez J, Alexopoulos LG, Sorger PK, Stolovitzky G (2011) Crowdsourcing network inference: the dream predictive signaling network challenge. Sci Signal 4(189):mr7

    Article  Google Scholar 

  39. Qin AK, Suganthan PN (2005) Self-adaptive differential evolution algorithm for numerical optimization. IEEE, pp 1785–1791

  40. Radenski A (2012) Distributed simulated annealing with MapReduce. Applications of evolutionary computation. Springer, Berlin, pp 466–476

    Book  Google Scholar 

  41. Saez-Rodriguez J, Alexopoulos LG, Epperlein J, Samaga R, Lauffenburger DA, Klamt S, Sorger PK (2009) Discrete logic modelling as a means to link protein signalling networks with functional analysis of mammalian signal transduction. Mol Syst Biol 5:331

    Article  Google Scholar 

  42. Saez-Rodriguez J, Costello JC, Friend SH, Kellen MR, Mangravite L, Meyer P, Norman T, Stolovitzky G (2016) Crowdsourcing biomedical research: leveraging communities as innovation engines. Nat Rev Genet 17(8):470–486

    Article  Google Scholar 

  43. Salto C, Minetti G, Alba E, Luque G (2018) Developing genetic algorithms using different mapreduce frameworks: Mpi vs. hadoop. In: Conference of the Spanish Association for Artificial Intelligence. Springer, pp 262–272

  44. Storn R, Price K (1997) Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces. J Glob Optim 11(4):341–359

    Article  MathSciNet  MATH  Google Scholar 

  45. Teijeiro D, Pardo XC, González P, Banga JR, Doallo R (2016) Implementing parallel differential evolution on Spark. Applications of evolutionary computation, vol 9598. Lecture notes in computer science. Springer, Berlin, pp 75–90

    Google Scholar 

  46. Teijeiro D, Pardo XC, González P, Banga JR, Doallo R (2016) Towards cloud-based parallel metaheuristics: a case study in computational biology with differential evolution and spark. Int J High Perform Comput Appl. https://doi.org/10.1177/1094342016679011

  47. Terfve C, Cokelaer T, Henriques D, MacNamara A, Goncalves E, Morris MK, van Iersel M, Lauffenburger DA, Saez-Rodriguez J (2012) CellNOptR: a flexible toolkit to train protein signaling networks to data using multiple logic formalisms. BMC Syst Biol 6(1):133

    Article  Google Scholar 

  48. Verma A, Llora X, Goldberg DE, Campbell RH (2009) Scaling genetic algorithms using MapReduce. In: The Ninth International Conference on Intelligent Systems Design and Applications, ISDA’09. IEEE, pp 13–18

  49. Villaverde AF, Banga JR (2014) Reverse engineering and identification in systems biology: strategies, perspectives and challenges. J R Soc Interface 11(91):20130505

    Article  Google Scholar 

  50. Vrugt JA, Robinson BA, Hyman JM (2009) Self-adaptive multimethod search for global optimization in real-parameter spaces. IEEE Trans Evolut Comput 13(2):243–259

    Article  Google Scholar 

  51. Wilcoxon F (1945) Individual comparisons by ranking methods. Biom Bull 1(6):80–83

    Article  Google Scholar 

  52. Wittmann DM, Krumsiek J, Saez-Rodriguez J, Lauffenburger DA, Klamt S, Theis FJ (2009) Transforming boolean models to continuous models: methodology and application to t-cell receptor signaling. BMC Syst Biol 3(1):98

    Article  Google Scholar 

  53. Yang P, Hwa Yang Y, B Zhou B, Y Zomaya A (2010) A review of ensemble methods in bioinformatics. Curr Bioinform 5(4):296–308

    Article  Google Scholar 

  54. Zaharia M, Chowdhury M, Das T, Dave A, Ma J, McCauley M, Franklin MJ, Shenker S, Stoica I (2012) Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing. In: The 9th USENIX Symposium on Networked Systems Design and Implementation, NSDI

  55. Zhai Y, Liu M, Zhai J, Ma X, Chen W (2011) Cloud versus in-house cluster: evaluating amazon cluster compute instances for running MPI applications. In: SC’11: State of the Practice Reports. ACM, p 11

Download references

Acknowledgements

This research received financial support from the Spanish Government through the Projects DPI2017-82896-C2-2-R and TIN2016-75845-P (AEI/FEDER, UE), and from the Galician Government under the Consolidation Program of Competitive Research Units (Network Ref. R2016/045 and Project Ref. ED431C 2017/04), all of them co-funded by FEDER funds of the EU. We also acknowledge Microsoft Research for being awarded with a sponsored Azure account, and CESGA for the access to their facilities.

Author information

Authors and Affiliations

  1. Computer Architecture Group, CITIC, University of A Coruña, A Coruña, Spain

    Patricia González, Pablo Argüeso-Alejandro, Xoan C. Pardo & Ramón Doallo

  2. MODESTYA Research Group, IMAT, University of Santiago de Compostela, Santiago de Compostela, Spain

    David R. Penas

  3. Faculty of Medicine, Institute for Computational Biomedicine, Bioquant, Heidelberg University, Heidelberg, Germany

    Julio Saez-Rodriguez

  4. BioProcess Engineering Group, IIM-CSIC, Spanish National Research Council, Madrid, Spain

    Julio R. Banga

Authors
  1. Patricia González
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Pablo Argüeso-Alejandro
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. David R. Penas
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Xoan C. Pardo
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Julio Saez-Rodriguez
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Julio R. Banga
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Ramón Doallo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Patricia González.

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

González, P., Argüeso-Alejandro, P., Penas, D.R. et al. Hybrid parallel multimethod hyperheuristic for mixed-integer dynamic optimization problems in computational systems biology. J Supercomput 75, 3471–3498 (2019). https://doi.org/10.1007/s11227-019-02871-0

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-019-02871-0

Keywords

Search

Navigation