0-1 Knapsack Problem Solving using Genetic Optimization Algorithm
Downloads
A 0-1 knapsack problem with m constraints is known as the 0-1 multidimensional knapsack problem, and it is challenging to solve using standard techniques like branch and bound algorithms or dynamic programming. The goal of the Knapsack problem is to maximize the utility of the items in a knapsack while staying within its carrying capacity. This paper presents a genetic algorithm with Python code that can solve publicly available instances of the multidimensional knapsack problem in a very quick computational time. By identifying the significant genes, the attribute reduction method that uses the rough set theory reduces the search space and guarantees that useful information is not lost. To regulate convergence, the algorithm makes use of many additional hyperparameters that can be adjusted in the code.
Bansal, A., Gadia, H., Dhanusha, S., & Pandey, A. (2021). Solving 0-1 Knapsack Problem using Genetic Algorithm.
Shu, Z., Ye, Z., Zong, X., Liu, S., Zhang, D., Wang, C., & Wang, M. (2022). A modified hybrid rice optimization algorithm for solving 0-1 knapsack problem. Applied Intelligence, 52(5), 5751-5769.
Yang, Y. (2024). An upper bound of the mutation probability in the genetic algorithm for general 0-1 knapsack problem. arXiv preprint arXiv:2403.11307.
Wei, Y., & Luo, Q. (2020, March). Cognitive Behavior Optimization Algorithm Application for Large-scale Knapsack Problem. In 2020 IEEE International Conference on Artificial Intelligence and Information Systems (ICAIIS) (pp. 179-183). IEEE.
Moradi, N., Kayvanfar, V., & Rafiee, M. (2022). An efficient population-based simulated annealing algorithm for 0–1 knapsack problem. Engineering with Computers, 38(3), 2771-2790.
Liu, K., Ouyang, H., Li, S., & Gao, L. (2022). A hybrid harmony search algorithm with distribution estimation for solving the 0-1 knapsack problem. Mathematical Problems in Engineering, 2022.
Wang, C., Li, D., Kaewniam, P., Wang, J., & Al Hababi, T. (2023). An ED-PSO model updating algorithm for structure health monitoring of beam-like structures. Journal of Measurements in Engineering, 11(3), 358-372.
Okwu, M., Otanocha, O. B., Omoregbee, H. O., & Edward, B. A. (2020). Appraisal of genetic algorithm and its application in 0-1 knapsack problem. Journal of Mechanical and Energy Engineering, 4(1), 39-46.
Nand, R., & Sharma, P. (2019, December). Iteration split with Firefly Algorithm and Genetic Algorithm to solve multidimensional knapsack problems. In 2019 IEEE Asia-Pacific Conference on Computer Science and Data Engineering (CSDE) (pp. 1-7). IEEE.
Gupta, I. K. (2018, March). A hybrid GA-GSA algorithm to solve multidimensional knapsack problem. In 2018 4th International Conference on Recent Advances in Information Technology (RAIT) (pp. 1-6). IEEE.
Al Etawi, N. A., & Aburomman, F. T. (2020). 0/1 KNAPSACK PROBLEM: GREEDY VS. DYNAMIC-PROGRAMMING. Int J Adv Eng Manag Res, 5(2), 1-10.
do Vale Pereda, M., Scarpin, C. T., Junior, J. E. P., Puhl, C., & Ferrer, L. W. U. (2023). Comparison of Metaheuristics in Solving the Knapsack Problem: An Experimental Analysis. Revista de Gestão Social e Ambiental, 17(9), e03814-e03814.
Agrawal, P., Ganesh, T., & Mohamed, A. W. (2021). Solving knapsack problems using a binary gaining sharing knowledge-based optimization algorithm. Complex & Intelligent Systems, 1-21.
Yang, Y., Liu, S., & ZHOU, Y. (2020). Greedy binary lion swarm optimization algorithm for solving multidimensional knapsack problem. Journal of Computer Applications, 40(5), 1291.
Saraswat, M., & Tripathi, R. C. (2021). Solving Knapsack Problem with Genetic Algorithm Approach. In Mathematical Modeling and Computation of Real-Time Problems (pp. 169-177). CRC Press.
Kabadurmus, O., Tasgetiren, M. F., Oztop, H., & Erdogan, M. S. (2021). Solving 0-1 bi-objective multi-dimensional knapsack problems using binary genetic algorithm. Heuristics for Optimization and Learning, 51-67.
Abdel-Basset, M., Mohamed, R., Elkomy, O. M., & Abouhawwash, M. (2022). Recent metaheuristic algorithms with genetic operators for high-dimensional knapsack instances: A comparative study. Computers & Industrial Engineering, 166, 107974.
He, Y., Wang, J., Liu, X., Wang, X., & Ouyang, H. (2024). Modeling and solving of knapsack problem with setup based on evolutionary algorithm. Mathematics and Computers in Simulation, 219, 378-403.
Gen, M., & Lin, L. (2023). Genetic algorithms and their applications. In Springer handbook of engineering statistics (pp. 635-674). London: Springer London.
Gazioğlu, E. (2022). Solving Multidimensional Knapsack Problem with Bayesian Multiploid Genetic Algorithm. Journal of Soft Computing and Artificial Intelligence, 3(2), 58-64.
Wang, R., & Zhang, Z. (2021). Set theory-based operator design in evolutionary algorithms for solving knapsack problems. IEEE Transactions on Evolutionary Computation, 25(6), 1133-1147.
Zhang, X., Qi, F., Hua, Z., & Yang, S. (2020, April). Solving billion-scale knapsack problems. In Proceedings of The Web Conference 2020 (pp. 3105-3111).
P. T. Pantzan, GitHub - Pantzan/KnapsackGA: Knapsack Problem solved using Genetic optimization algorithm, (2020).
Baş, E. (2023). Binary aquila optimizer for 0–1 knapsack problems. Engineering Applications of Artificial Intelligence, 118, 105592.
William, I. O., & Altamimi, E. M. (2024). Hierarchical Long Short-Term Memory (LSTM) Model for News Sentiment Analysis.
