Enfoque de Evaluación para la Configuración de Parámetros en Algoritmo Genético: Un Caso del Problema de la Mochila 0-1
DOI:
https://doi.org/10.35588/jyravv64Palabras clave:
Algoritmo genético, Problema mochila 0-1, Configuración de parámetros, Optimización CombinatoriaResumen
La experimentación con diferentes configuraciones del algoritmo genético reveló que una baja probabilidad de mutación, combinada con un tamaño de torneo adecuado, mejora significativamente el rendimiento del algoritmo. Esto se refleja en la reducción del GAP promedio y la maximización del valor objetivo alcanzado, estableciendo así parámetros de referencia cuantificables para implementaciones eficientes del problema de la mochila 0-1. La novedad del estudio radica en ofrecer directrices concretas para aplicaciones prácticas, identificando relaciones consistentes entre la configuración de parámetros y el comportamiento del algoritmo. Si bien los AG son eficaces en la exploración de grandes espacios de búsqueda en problemas NP-completos, este trabajo demuestra que requieren una calibración precisa para evitar la convergencia prematura. Se constató que la probabilidad de mutación y el tamaño del torneo influyen directamente en las dinámicas exploratoria y explotadora del algoritmo. En general, combinaciones con baja mutación y torneos intermedios ofrecieron un buen equilibrio entre calidad de solución y estabilidad, mientras que valores extremos (mutación de 0.20 o torneo k = 2/k=4) incrementaron la variabilidad del rendimiento, especialmente en problemas de mayor escala. Estos hallazgos evidencian la sensibilidad del algoritmo a dichos parámetros y destacan la importancia de ajustes cuidadosos para preservar su eficacia ante escenarios complejos.
Descargas
Referencias
Ahmed, Z. y Younas, I. (2011). A Dynamic Programming based GA for 0-1 Modified
Knapsack Problem. International Journal of Computer Applications, 16(7), 1-6. https://doi.org/10.5120/2028-2668
Eiben, A. E. y Smit, S. K. (2011). Parameter tuning for configuring and analyzing evolutionary algorithms. Swarm and Evolutionary Computation, 1(1), 19-31. https://doi.org/10.1016/j.swevo.2011.02.001
Ezziane, Z. (2002). Solving the 0/1 knapsack problem using an adaptive genetic algorithm. Artificial Intelligence for Engineering Design, Analysis and Manufacturing, 16(1), 23-30. https://doi.org/10.1017/s0890060401020030
He, J., He, F. y Dong, H. (2014). A Novel Genetic Algorithm using Helper Objectives for the 0-1 Knapsack Problem. arXiv:1404.0868 [cs.NE]. https://doi.org/10.48550/arXiv.1404.0868
Hinterding, R., Michalewicz, Z. y Eiben, A. E. (1997). Adaptation in evolutionary computation: a survey. IEEE International Conference on Evolutionary Computation (ICEC ’97), 65-69. https://doi.org/10.1109/icec.1997.592270
Hota, A. R. y Pat, A. (2010). An adaptive quantum‑inspired differential evolution algorithm for 0-1 knapsack problem. 2010 Second World Congress on Nature and Biologically Inspired Computing (NaBIC), 703-708. https://doi.org/10.1109/nabic.2010.5716320
Khuri, S., Bäck, T. y Heitkötter, J. (1994). The zero/one multiple knapsack problem and genetic algorithms. ACM symposium on Applied computing - SAC ’94, 188-193. https://doi.org/10.1145/326619.326694
Krasnogor, N. y Smith, J. (2005). A tutorial for competent memetic algorithms: model, taxonomy, and design issues. IEEE Transactions on Evolutionary Computation, 9(5), 474-488. https://doi.org/10.1109/tevc.2005.850260
Malanthara, A. y Kale, I. R. (2025). Hybrid Firefly-Genetic Algorithm for Single and Multi-dimensional 0-1 Knapsack Problems (Versión 1). arXiv:2501.14775 [cs.NE]. https://doi.org/10.48550/ARXIV.2501.14775
Owais, W. B., Alkhazendar, I. W. J. y Saleh, M. (2020). Evaluating the impact of different types of crossover and selection methods on the convergence of 0/1 Knapsack using Genetic Algorithm. Computer Science & Information Technology (CS & IT), 01-16. https://doi.org/10.5121/csit.2020.101101
Pisinger, D. (2005). Where are the hard knapsack problems? Computers & Operations Research, 32(9), 2271-2284. https://doi.org/10.1016/j.cor.2004.03.002
Pradhan, T., Israni, A. y Sharma, M. (2014). Solving the 0–1 Knapsack problem using Genetic Algorithm and Rough Set Theory. IEEE International Conference on Advanced Communications, Control and Computing Technologies, 1120-1125. https://doi.org/10.1109/icaccct.2014.7019272
Raidl, G. R. (1998). An improved genetic algorithm for the multiconstrained 0-1 knapsack problem. IEEE International Conference on Evolutionary Computation Proceedings. IEEE World Congress on Computational Intelligence (Cat. No.98TH8360), 207-211. https://doi.org/10.1109/icec.1998.699502
Umbarkar, A. J. y Joshi, M. S. (2014). 0/1 Knapsack Problem using Diversity based Dual Population Genetic Algorithm. International Journal of Intelligent Systems and Applications, 6(10), 34-40. https://doi.org/10.5815/ijisa.2014.10.05
Yan, T. S., Guo, G. Q., Li, H. M. y He, W. (2013). A Genetic Algorithm for Solving Knapsack Problems Based on Adaptive Evolution in Dual Population. Advanced Materials Research, 756-759, 2799-2802. https://doi.org/10.4028/www.scientific.net/amr.756-759.2799
Yang, Y. (2024). An upper bound of the mutation probability in the genetic algorithm for general 0-1 knapsack problem. arXiv:2403.11307 [cs.NE]. https://doi.org/10.48550/arXiv.2403.11307
Kim, Y., Kim, J.‑H. y Han, K.‑H. (2006). Quantum-inspired Multiobjective Evolutionary Algorithm for Multiobjective 0/1 Knapsack Problems. IEEE International Conference on Evolutionary Computation, 2601‑2606. https://doi.org/10.1109/cec.2006.1688633
Descargas
Publicado
Número
Sección
Licencia
Derechos de autor 2025 Revista Gestión de las Personas y Tecnología
Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.
