Implementing cloud-based parallel metaheuristicsan overview

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

ISSN: 1666-6038

Año de publicación: 2018

Título del ejemplar: Special Issue JCC&BD 2018; e27

Volumen: 18

Número: 3

Tipo: Artículo

DOI: 10.24215/16666038.18.E26 DIALNET GOOGLE SCHOLAR

Otras publicaciones en: Journal of Computer Science and Technology

Objetivos de desarrollo sostenible

Resumen

Las metaheurísticas son uno de los métodos más populares en muchas áreas de la ciencia y la ingeniería para la resolución de problemas de optimización global difíciles. Su implementación paralela, aplicando técnicas de HPC, es una aproximación común a la hora de reducir el tiempo necesario para obtener una solución lo suficientemente buena con un uso eficiente de los recursos disponibles. Paradigmas como MPI u OMP son las opciones habituales cuando se ejecutan en clústeres o supercomputadores. Además, la utilización generalizada de la computación en la nube y la aparición de modelos de programación como MapReduce o Spark, han generado un interés creciente por portar aplicaciones HPC a la nube, como ocurre en el caso de las metaheurísticas paralelas. En este trabajo recogemos una visión general de nuestra experiencia con diferentes opciones a la hora de portar metaheurísticas paralelas a la nube, proporcionando información útil al lector interesado, que hemos ido adquiriendo a través de nuestra experiencia práctica.

Referencias bibliográficas

  • 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.
Fuente de los datos: Dialnet