“Cooperation Greedy Monkey Algorithm”: Parallel algorithm to solve the strongly correlated class of the knapsack problem 0-1
DOI:
https://doi.org/10.30973/progmat/2021.13.2/6Keywords:
Cooperation Greedy Monkey Algorithm, Swarm Intelligence, Knapsack Problem 0-1Abstract
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.
References
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
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2021 Programación Matemática y Software
This work is licensed under a Creative Commons Attribution 4.0 International License.
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. |