"Cooperation Greedy Monkey Algorithm": Algoritmo paralelo para resolver la clase fuertemente correlacionada del problema de la mochila 0-1
Título del documento: "Cooperation Greedy Monkey Algorithm": Algoritmo paralelo para resolver la clase fuertemente correlacionada del problema de la mochila 0-1
Revista: Programación matemática y software
Base de datos:
Número de sistema: 000573256
ISSN: 2007-3283
Autores: 1
2
3
4
Instituciones: 1Facultad de contaduría, administración e Informática UAEM, Av. Universidad 1001, Col. Chamilpa, Cuernavaca, Morelos CP: 62210,
2Departamento de Ciencias Computacionales, TecNM/Centro Nacional de Investigación y Desarrollo Tecnológico, Interior Internado Palmira S/N, Col. Palmira, Cuernavaca, Morelos CP: 62490,
3Divisió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,
4acultad de contaduría, administración e Informática UAEM, Av. Universidad 1001, Col. Chamilpa, Cuernavaca, Morelos CP: 62210,
Año:
Volumen: 13
Número: 2
Paginación: 62-80
País: México
Idioma: Español
Resumen en inglés 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 established by Pisinger, the uncorrelated, the weakly correlated and the strongly correlated. The solution capacity of the algorithm is extended to solve instances with different percentages 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.
Resumen en español 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
Keyword: Cooperation Greedy Monkey Algorithm,
Swarm Intelligence,
Knapsack Problem 0-1
Texto completo: Texto completo (Ver PDF)