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

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 clúster de 5 servidores. Los resultados son alentadores y en algunas ocasiones se calcula la solución óptima.

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