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

Publicación:
Entidad Editora:
Director Editorial:
ISSN:
Ejemplar/Número:

Categoría:
Páginas:
Colección:
Fecha de inicio:
Periodicidad:

Programación Matemática y Software
Universidad Autónoma del Estado de Morelos
Dr.Marco Antonio Cruz Chávez
2007-3283
Volumen 13, Número 2/Junio de 2021
Periodo Junio-Septiembre 2021
Artículo de Investigación
62-80
Computación
Junio del 2021
Cuatrimestral

PDF(1053 KB)

José Crispín Zavala-Díaz¹, Joaquín Pérez-Ortega², Nely Nelva Almanza-Ortega³, Jaqueline López-Calderón¹ 

¹Facultad de contaduría, administración e Informática UAEM, Av. Universidad 1001, Col. Chamilpa, Cuernavaca, Morelos CP: 62210.

²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.

³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.

Recibido: 12 de diciembre  del 2020   Aceptado: 25 de mayo del 2021     Publicado en línea: 4 de junio del 2021

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. 

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

Abstract. The parallelization of the Cooperation Greedy Monkey Algorithm and the adjustment of parameters to solve the problem KP 0-1 (0-1 Knapsack Problem) is presented. The solved problems are taken from the specialized literature up to the instances estab-lished by Pisinger, the uncorrelated, the weakly correlated and the strongly correlated. The solution capacity of the algorithm is extended to solve instances with different per-centages of 25% and 50% of the sum of the weights of the elements, and not only 75% as the algorithm was originally designed. A master-slave model was used for its parallel implementation in a cluster of 5 servers. The results are encouraging and the optimal solution is sometimes calculated.

Keywords:Cooperation Greedy Monkey Algorithm, Swarm Intelligence, Knapsack Problem 0-1.

José Crispín Zavala Díaz (Autor de correspondencia)