“Cooperation Greedy Monkey Algorithm”: Algoritmo paralelo para resolver la clase fuertemente correlacionada del problema de la mochila 0-1

Autores/as

  • José Crispín Zavala-Díaz Facultad de contaduría, administración e Informática UAEM, Av. Universidad 1001, Col. Chamilpa, Cuernavaca, Morelos CP: 62210
  • Joaquín Pérez-Ortega Departamento de Ciencias Computacionales, TecNM/Centro Nacional de Investigación y Desarrollo Tecnológico, Interior Internado Palmira S/N, Col. Palmira, Cuernavaca, Morelos CP: 62490
  • Nely Nelva Almanza-Ortega División de Estudios de Posgrado e Investigación, TecNM/Instituto Tecnológico de Tlalnepantla, Av. Instituto Tecnológico s/n, Col. La Comunidad, Tlalnepantla de Baz, Estado de México CP: 54070
  • Jaqueline López-Calderón acultad de contaduría, administración e Informática UAEM, Av. Universidad 1001, Col. Chamilpa, Cuernavaca, Morelos CP: 62210

DOI:

https://doi.org/10.30973/progmat/2021.13.2/6

Palabras clave:

Algoritmo del mono ávido cooperativo, Inteligencia de enjambre, El problema del peso en la mochila 0-1

Resumen

Se presenta la paralelización del Cooperation Greedy Monkey Algorithm y el ajuste de parámetros para resolver el problema KP 0-1 (0-1 Knapsack Problem). Los problemas resueltos son tomados de la literatura especializada hasta las instancias establecidas por Pisinger, las no correlacionadas, las débilmente correlacionadas y las fuertemente correlacionadas. Se amplía la capacidad de solución del algoritmo para resolver instancias con diferentes porcentajes del 25% y 50% de la suma de los pesos de los elementos, y no únicamente el 75% como está diseñado el algoritmo originalmente. Se utilizó un modelo maestro-esclavo para su implementación paralela en un cluster de 5 servidores. Los resultados son alentadores y en algunas ocasiones se calcula la solución óptima.

Biografía del autor/a

José Crispín Zavala-Díaz, Facultad de contaduría, administración e Informática UAEM, Av. Universidad 1001, Col. Chamilpa, Cuernavaca, Morelos CP: 62210

Obtuvo el grado de Doctor en Ciencias Computacionales por el Instituto Tecnológico y de Estudios Superiores de Monterrey. Actualmente tiene la distinción de Investigador Nacional Nivel I del SNI. Está adscrito a la Facultad de Contaduría, Administración e Informática de la Universidad Autónoma del Estado de Morelos, desde 1990 a la fecha. Sus áreas de interés en investigación son optimización combinatoria, cómputo paralelo y algorítmica.

Joaquín Pérez-Ortega, Departamento de Ciencias Computacionales, TecNM/Centro Nacional de Investigación y Desarrollo Tecnológico, Interior Internado Palmira S/N, Col. Palmira, Cuernavaca, Morelos CP: 62490

btuvo los grados de Doctorado y Maestría en Ciencias Computacionales por el Instituto Tecnológico y de Estudios Superiores de Monterrey, y el de Ingeniero Industrial en Producción por el Instituto Tecnológico de León. Actualmente tiene la distinción de Investigador Nacional Nivel II del SNI. Está adscrito al Departamento de Ciencias Computacionales del Centro Nacional de investigación y Desarrollo Tecnológico (CENIDET), desde 1989 a la fecha. Sus áreas de interés en investigación son Ciencia de Datos, Minería de Datos, Algoritmia, Optimización y Modelación Matemática. A llevado a buen fin la dirección de más de doce tesis de doctorado y más de cuarenta de maestría. Algunas de las tesis que ha dirigido han obtenido premios nacionales e internacionales. Cuenta con un artículo reconocido como Best Paper en un congreso internacional especializado y de gran prestigio.

Nely Nelva Almanza-Ortega, División de Estudios de Posgrado e Investigación, TecNM/Instituto Tecnológico de Tlalnepantla, Av. Instituto Tecnológico s/n, Col. La Comunidad, Tlalnepantla de Baz, Estado de México CP: 54070

rofesora adscrita al Departamento de División de Estudios de Posgrado e Investigación del IT de Tlalnepantla (ITTLA) desde abril de 2019. Doctorado y Maestría en Ciencias de la Computación otorgados por el Centro Nacional de investigación y Desarrollo Tecnológico (CENIDET). Miembro del Sistema Nacional de Investigadores (SNI), Nivel C. Las áreas de interés en investigación son Ciencia de Datos, Minería de Datos, Análisis y Desarrollo de Algoritmos Heurísticos.

Jaqueline López-Calderón, acultad de contaduría, administración e Informática UAEM, Av. Universidad 1001, Col. Chamilpa, Cuernavaca, Morelos CP: 62210

Obtuvo el grado de Maestra en Optimización y Cómputo Aplicado por la Facultad de Contaduría, Administración e Informática de la Universidad Autónoma del Estado de Morelos en el 2019. Sus áreas de interés algorítmica y cómputo paralelo.

Citas

Dantzig G. B. Discrete-Variable Extremum Problems. Operations Research. 1957, 5(2), 266- 277. https://doi.org/10.1287/opre.5.2.266

Bretthauer K. M., & Shetty B., The nonlinear knapsack problem-algorithms and applications. European Journal of Operational Research, 2002. 138(3) 459-472. https://doi.org/10.1016/S0377-2217(01)00179-5

Pisinger D., Where are the hard knapsack problems? Computers & Operations Research, 2005, 32(9), 2271-2284. https://doi.org/10.1016/j.cor.2004.03.002

Hristakeva M., & Shrestha D., Different approaches to solve the 0/1 knapsack problem. In The Midwest Instruction and Computing Symposium. 2005

Kellerer H., Pferschy U., & Pisinger D., Knapsack Problems. Springer, Berlin. 2004, ISBN 978-3-540- 24777-7.

Zhang, J., Comparative study of several intelligent algorithms for knapsack problem. Procedia Environmental Sciences, 2011, 11, 163-168. https://doi.org/10.1016/j.proenv.2011.12.025

Alfonso H., Salto C., Minetti G. F., Stark, N., Bermúdez, C., Orellana, A., & Sanz Troiani, F. (2010). Metaheurísticas aplicadas a problemas de optimización. In XII Workshop de Investigadores en Ciencias de la Computación. 2010, 72-76

Alba E., Luque G., & Nesmachnow S., Metaheurísticas paralelas: avances recientes y nuevas tendencias. Transacciones internacionales en investigación operativa, 2013, 20(1), 1-48.

Kaur MD., Revisión de diferentes técnicas metaheurísticas para computación paralela. Revista de investigación avanzada en computación en la nube, virtualización y aplicaciones web, 2018, 1(2), 28-32.

Zhou Y., Chen X., & Zhou G., An improved monkey algorithm for a 0-1 knapsack problem. Applied Soft Computing, 2016, 38, 817-830. https://doi.org/10.1016/j.asoc.2015.10.043

Yang X. S., & Karamanoglu M., Swarm intelligence and bio-inspired computation: an overview. In Swarm intelligence and bio-inspired computation, Elsevier, 2013, 3-23. https://doi.org/10.1016/B978-0-12-405163-8.00001-6

Chakraborty A., & Kar A. K., Swarm intelligence: A review of algorithms. In Nature-Inspired Computing and Optimization. Springer, 2017, 475-494. https://doi.org/10.1007/978-3-319-50920-4_19

Adi S., & Aldasht M., Parallel Evolutionary Algorithms for Feature Selection in High Dimensional Datasets. International Journal of Computer Science and Information Security (IJCSIS), 2018, 16(3).

Cotta C., Talbi EG., y Alba E., Metaheurísticas híbridas paralelas. Metaheurísticas paralelas: una nueva clase de algoritmos, 2005 Vol.47, No.347.

Talbi E. G., A taxonomy of hybrid metaheuristics. Journal of heuristics, 2002, 8(5), 541-564. A taxonomy of hybrid metaheuristics

Pospichal P., Schwarz J., y Jaros J., Algoritmo genético paralelo que resuelve 0/1 problema de mochila que se ejecuta en el gpu. En la 16ª Conferencia Internacional sobre Soft Computing MENDEL, 2010, 64-70.

Hajarian M., Shahbahrami A., & Hoseini F., A parallel solution for the 0–1 knapsack problem using firefly algorithm. Conference on Swarm Intelligence and Evolutionary Computation (CSIEC), 2016 pp. 25-30. https://doi.org/10.1109/CSIEC.2016.7482134

Sonuc E., Sen B., & Bayir S., A parallel approach for solving 0/1 knapsack problem using simulated annealing algorithm on CUDA platform. International Journal of Computer Science and Information Security, 2016, 14(12).

El-Shafei M., Ahmad I., & Alfailakawi M. G., Hardware accelerator for solving 0–1 knapsack problems using binary harmony search. International Journal of Parallel, Emergent and Distributed Systems, 2018, 33(1), 87-102. https://doi.org/10.1080/17445760.2017.1324025

Zhao R. Q., & Tang W. S., Monkey algorithm for global numerical optimization. Journal of Uncertain Systems, 2008, 2(3), 165-176.

Yi T. H., Li H. N., & Zhang X. D., A modified monkey algorithm for optimal sensor placement in structural health monitoring. Smart Materials and Structures, 2012, 21(10), https://doi.org/10.1088/0964-1726/21/10/105033

Zheng L., An improved monkey algorithm with dynamic adaptation. Applied Mathematics and Computation, 2013, 222, 645-657. https://doi.org/10.1016/j.amc.2013.07.067

Yi T. H., Li H. N., Song G., & Zhang X. D., Optimal sensor placement for health monitoring of high‐rise structure using adaptive monkey algorithm. Structural Control and Health Monitoring, 2015, 22(4), 667-681 https://doi.org/10.1002/stc.1708

Zou D., Gao L., Li S., & Wu J., Solving 0–1 knapsack problem by a novel global harmony search algorithm. Applied Soft Computing, 2011, 11(2), 1556-1564. https://doi.org/10.1016/j.asoc.2010.07.019

Feng Y., Wang G. G., Feng Q., & Zhao X. J., An effective hybrid cuckoo search algorithm with improved shuffled frog leaping algorithm for 0-1 knapsack problems. Computational intelligence and neuroscience, 2014, pp. 36 https://doi.org/10.1155/2014/857254

Feng Y., Wang G. G., & Gao X. Z., A novel hybrid cuckoo search algorithm with global harmony search for 0-1 Knapsack problems. International Journal of Computational Intelligence Systems, 2016, 9(6), 1174-1190. https://doi.org/10.1080/18756891.2016.1256577

Rizk-Allah R. M., & Hassanien A. E., New binary bat algorithm for solving 0-1 knapsack problem. Complex & Intelligent Systems, 2018, 4(1), 31-53. https://doi.org/10.1007/s40747-017-0050-z

Kulkarni AJ., y Shabir H., Resolver un problema de mochila 0-1 usando el algoritmo de inteligencia de cohorte. Revista internacional de aprendizaje automático y cibernética, 2016, 7(3), 427-441.

Zavala Díaz J. C., Optimización con cómputo paralelo, México DF. México Ed. AM EDITORES., 2013. ISBN 9786074372267

Descargas

Publicado

04-06-2021

Cómo citar

Zavala-Díaz, J. C., Pérez-Ortega, J. ., Almanza-Ortega, N. N., & López-Calderón, J. (2021). “Cooperation Greedy Monkey Algorithm”: Algoritmo paralelo para resolver la clase fuertemente correlacionada del problema de la mochila 0-1. Programación matemática Y Software, 13(2), 62–80. https://doi.org/10.30973/progmat/2021.13.2/6

Número

Vol. 13 Núm. 2 (2021): Junio de 2021

Sección

Artículos

Licencia

Derechos de autor 2021 Programación Matemática y Software

Creative Commons License

Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.

Usted es libre de:

Compartir — compartir y redistribuir el material publicado en cualquier medio o formato.
Adaptar — combinar, transformar y construir sobre el material para cualquier propósito, incluso comercialmente.

Bajo las siguientes condiciones:

Atribución — Debe otorgar el crédito correspondiente, proporcionar un enlace a la licencia e indicar si se realizaron cambios. Puede hacerlo de cualquier manera razonable, pero de ninguna manera que sugiera que el licenciador lo respalda a usted o a su uso.
  Sin restricciones adicionales: no puede aplicar términos legales o medidas tecnológicas que restrinjan legalmente a otros a hacer cualquier cosa que permita la licencia.