Evaluation Approach for Parameter Settings in Genetic Algorithm: A Case of the 0-1 Knapsack Problem
DOI:
https://doi.org/10.35588/jyravv64Keywords:
Genetic algorithm, 0-1 knapsack problem, Parameter configuration, Combinatorial OptimizationAbstract
Experimentation with different configurations of the genetic algorithm revealed that a low mutation probability, combined with an appropriate tournament size, significantly improves the algorithm's performance. This is reflected in the reduction of the average GAP and the maximization of the achieved objective value, thereby establishing quantifiable benchmark parameters for efficient implementations of the 0-1 knapsack problem. The novelty of the study lies in providing concrete guidelines for practical applications, identifying consistent relationships between parameter configuration and algorithm behavior. While genetic algorithms are effective in exploring large search spaces in NP-complete problems, this work demonstrates that they require precise calibration to avoid premature convergence. It was found that the mutation probability and tournament size directly influence the algorithm's exploratory and exploitative dynamics. In general, combinations with low mutation and intermediate tournament sizes offered a good balance between solution quality and stability, whereas extreme values (mutation of 0.20 or tournament size k = 2/k = 4) increased performance variability, especially in larger-scale problems. These findings highlight the algorithm’s sensitivity to these parameters and underscore the importance of careful tuning to preserve its effectiveness in complex scenarios.
Downloads
References
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
Downloads
Published
Issue
Section
License
Copyright (c) 2025 People and Technology Management Journal
This work is licensed under a Creative Commons Attribution 4.0 International License.
