Implementing cloud-based parallel metaheuristicsan overview

  1. González, Patricia
  2. Pardo Martínez, Xoán Carlos
  3. Doallo, Ramón
  4. Banga, Julio
Journal:
Journal of Computer Science and Technology

ISSN: 1666-6038

Year of publication: 2018

Issue Title: Special Issue JCC&BD 2018; e27

Volume: 18

Issue: 3

Type: Article

DOI: 10.24215/16666038.18.E26 DIALNET GOOGLE SCHOLAR

More publications in: Journal of Computer Science and Technology

Sustainable development goals

Abstract

Metaheuristics are among the most popular methods for solving hard global optimization problems in many areas of science and engineering. Their parallel im- plementation applying HPC techniques is a common approach for efficiently using available resources to re- duce the time needed to get a good enough solution to hard-to-solve problems. Paradigms like MPI or OMP are the usual choice when executing them in clusters or supercomputers. Moreover, the pervasive presence of cloud computing and the emergence of programming models like MapReduce or Spark have given rise to an increasing interest in porting HPC workloads to the cloud, as is the case with parallel metaheuristics. In this paper we give an overview of our experience with different alternatives for porting parallel metaheuris- tics to the cloud, providing some useful insights to the interested reader that we have acquired through extensive experimentation.

Bibliographic References

  • C. A. Floudas and P. M. Pardalos, Optimization in computational chemistry and molecular biology: local and global approaches, vol. 40. Springer Science & Business Media, 2013.
  • J. R. Banga, “Optimization in computational systems biology,” BMC systems biology, vol. 2, no. 1, p. 47, 2008.
  • I. E. Grossmann, Global optimization in engineering design, vol. 9. Springer Science & Business Media, 2013.
  • I. Foster and D. B. Gannon, Cloud Computing for Science And Engineering. The MIT Press, 2017.
  • R. R. Exp´osito, G. L. Taboada, S. Ramos, J. Touri ˜no, and R. Doallo, “Performance analysis of HPC applications in the cloud,” Future Generation Computer Systems, vol. 29, no. 1, pp. 218–229, 2013.
  • I. Sadooghi, J. H. Martin, T. Li, K. Brandstatter, K. Maheshwari, T. P. P. de Lacerda Ruivo, G. Garzoglio, S. Timm, Y. Zhao, and I. Raicu, “Understanding the performance and potential of cloud computing for scientific applications,” IEEE Transactions on Cloud Computing, vol. 5, no. 2, pp. 358–371, 2017.
  • J. Dean and S. Ghemawat, “MapReduce: simplified data processing on large clusters,” in The 6th USENIX Symposium on Operating Systems Design and Implementation, 2004.
  • M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauley,M. J. Franklin, S. Shenker, and I. Stoica, “Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing,” in USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2012.
  • K. V. Price, R. M. Storn, and J. Lampinen, Differential Evolution - a practical approach to global optimization, vol. 141. 01 2005.
  • S. Das and P. Suganthan, “Differential evolution: A survey of the state-of-the-art,” IEEE Transactions on Evolutionary Computation, vol. 15, no. 1, pp. 4–31, 2011.
  • E. Alba, G. Luque, and S. Nesmachnow, “Parallel metaheuristics: recent advances and new trends,” International Transactions in Operational Research, vol. 20, no. 1, pp. 1–48, 2013.
  • D. Teijeiro, X. C. Pardo, P. Gonz´alez, J. R. Banga, and R. Doallo, Applications of Evolutionary Computation: 19th European Conference, EvoApplications 2016, Proceedings, Part II, ch. Implementing Parallel Differential Evolution on Spark, pp. 75–90. 2016.
  • D. R. Penas, J. R. Banga, P. Gonz´alez, and R. Doallo, “Enhanced parallel differential evolution algorithm for problems in computational systems biology,” Applied Soft Computing, vol. 33, pp. 86 – 99, 2015.
  • D. Teijeiro, X. C. Pardo, D. R. Penas, P. Gonz´alez, J. R. Banga, and R. Doallo, “Evaluation of parallel differential evolution implementations on mapreduce and spark,” in Euro-Par 2016: Parallel Processing Workshops, pp. 397–408, Springer International Publishing, 2017.
  • D. Teijeiro, X. C. Pardo, P. Gonz´alez, J. R. Banga, and R. Doallo, “Towards cloud-based parallel metaheuristics: A case study in computational biology with differential evolution and spark,” The International Journal of High Performance Computing Applications, 2016.
  • P. Gonz´alez, X. C. Pardo, D. R. Penas, D. Teijeiro, J. R. Banga, and R. Doallo, “Using the cloud for parameter estimation problems: Comparing spark vs mpi with a case-study,” in IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid ’17), pp. 197–206, 2017.
  • J. Locke, A. Millar, and M. Turner, “Modelling genetic networks with noisy and varied experimental data: the circadian clock in arabidopsis thaliana,” Journal of Theoretical Biology, vol. 234, no. 3, pp. 383–393, 2005.
  • T. G. Crainic, “Parallel meta-heuristics and cooperative search,” CIRRELT, vol. 58, 2017.
  • J. Apolloni, J. Garca-Nieto, E. Alba, and G. Leguizamn, “Empirical evaluation of distributed differential evolution on standard benchmarks,” Applied Mathematics and Computation, vol. 236, pp. 351–366, 2014.
  • A. W. McNabb, C. K. Monson, and K. D. Seppi, “Parallel PSO using MapReduce,” in IEEE Congress on Evolutionary Computation, CEC2007, pp. 7–14, IEEE, 2007.
  • C. Jin, C. Vecchiola, and R. Buyya, “MRPGA: an extension of MapReduce for parallelizing genetic algorithms,” in IEEE Fourth International Conference on eScience, eScience’08, pp. 214–221, IEEE, 2008.
  • A. Verma, X. Llora, D. E. Goldberg, and R. H. Campbell, “Scaling genetic algorithms using MapReduce,” in Ninth International Conference on Intelligent Systems Design and Applications, ISDA’09, pp. 13–18, IEEE, 2009.
  • A. Radenski, “Distributed simulated annealing with MapReduce,” in Applications of Evolutionary Computation, pp. 466–476, Springer, 2012.
  • W.-P. Lee, Y.-T. Hsiao, and W.-C. Hwang, “Designing a parallel evolutionary algorithm for inferring gene networks on the cloud computing environment,” BMC systems biology, vol. 8, no. 1, p. 5, 2014.
  • C. Zhou, “Fast parallelization of differential evolution algorithm usingMapReduce,” in Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, pp. 1113–1114, ACM, 2010.
  • K. Tagawa and T. Ishimizu, “Concurrent differential evolution based on MapReduce,” International Journal of Computers, vol. 4, no. 4, pp. 161–168, 2010.
  • M. Daoudi, S. Hamena, Z. Benmounah, and M. Batouche, “Parallel differential evolution clustering algorithm based on MapReduce,” in 6th International Conference of Soft Computing and Pattern Recognition (SoCPaR), pp. 337–341, IEEE, 2014.
  • K. Govindarajan, D. Boulanger, V. S. Kumar, and Kinshuk, “Parallel particle swarm optimization (ppso) clustering for learning analytics,” in 2015 IEEE International Conference on Big Data (Big Data), pp. 1461–1465, Oct 2015.
  • C.-W. Tsai, S.-J. Liu, and Y.-C. Wang, “A parallel metaheuristic data clustering framework for cloud,” Journal of Parallel and Distributed Computing, vol. 116, pp. 39–49, 2018.
  • R. Qi, Z. Wang, and S. Li, “Pairwise test generation based on parallel genetic algorithm with spark,” in Proceedings of the International Conference on Computer Information Systems and Industrial Applications, pp. 67–70, 2015.
  • L.Wang, Y.Wang, and Y. Xie, “Implementation of a parallel algorithm based on a spark cloud computing platform,” Algorithms, vol. 8, no. 3, pp. 407–414, 2015.
  • C.-W. Tsai, H.-C. Chang, K.-C. Hu, and M.-C. Chiang, “Parallel coral reef algorithm for solving jsp on spark,” in 2016 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pp. 001872–001877,Oct 2016.
  • J. Garcia Conejeros, F. Altimiras, A. Pe˜na Fritz, G. Astorga, and O. Peredo, “A binary cuckoo search big data algorithm applied to large-scale crew scheduling problems,” Complexity, 05 2018.
  • C. Deng, X. Tan, X. Dong, and Y. Tan, “A parallel version of differential evolution based on resilient distributed datasets model,” in Bio-Inspired Computing-Theories and Applications, pp. 84–93, Springer, 2015.
Data source: Dialnet