An Adaptive Genetic Algorithm for the 0-1 Knapsack Problem

Year 2025, Volume: 1 Issue: 1, 34 - 40, 20.06.2025

Kazım Erdoğdu

Abstract

Solving the 0-1 knapsack problem is a combinatorial optimization problem. Although genetic algorithms (GAs) provide strong global search capabilities, early convergence and static parameter sets frequently impair their performance. In this study, an Adaptive Genetic Algorithm is proposed that adaptively selects crossover types during the search. The suggested AGA was tested on a set of small and large benchmark instance sets and compared with the three crossovers' performances.

Keywords

0-1 Knapsack Problem , Genetic Algorithm , Adaptive Metaheuristic

References

• Bellman, R. (1957, October). Letter to the Editor—Comment on Dantzig’s Paper on Discrete Variable Extremum Problems. Operations Research, 5(5), 723-724. doi: 10.1287/opre.5.5.723
• Berberler, M. E., Güler, A., & Nuriyev, U. (2016). A new genetic algorithm for the 0-1 knapsack problem. Academic Platform - Journal of Engineering and Science, 4(3). doi: 10.21541/apjes.14020
• Cacchiani, V., Iori, M., Locatelli, A., & Martello, S. (2022). Knapsack problems — an overview of recent advances. part ii: Multiple, multidimensional, and quadratic knapsack problems. Computers & Operations Research, 143, 105693. doi: doi.org/10.1016/j.cor.2021.105693
• Changdar, C., Mahapatra, G., & Pal, R. K. (2013). Solving 0–1 knapsack problem by continuous aco algorithm. International Journal of Computational Intelligence Studies, 2(3/4), 333–349. doi: 10.1504/ IJCISTUDIES.2013.057638
• Changdar, C., Mahapatra, G. S., & Pal, R. K. (2017). A modified artificial bee colony approach for the 0–1 knapsack problem. Applied Intelligence, 47(4), 1011–1028. doi: 10.1007/s10489-017-1025-x
• Chen, Y. (2016). A novel bat algorithm of solving 0-1 knapsack problem. In Proceedings of the 2016 4th international conference on machinery, materials and computing technology (p. 1597-1600). Atlantis Press. doi: 10.2991/icmmct-16.2016.318
• Dantzig, G. B. (1957). Discrete-variable extremum problems. Operations Research, 5(2), 266–277. doi: 10.1287/opre.5.2.266
• Drexl, A. (1988). A simulated annealing approach to the multiconstraint zero-one knapsack problem. Computing, 40(3), 211–221. doi: 10.1007/BF02242185
• Ekmekci, D. (2020). 0-1 Çok boyutlu sırt Çantası probleminin feromonal yapay arı koloni (fyak) algoritması ile Çözümü. Academic Platform - Journal of Engineering and Science, 8(2), 355–364. doi: 10.21541/ apjes.640252
• Feng, Y., Jia, K., & He, Y. (2014, 01). An improved hybrid encoding cuckoo search algorithm for 0-1 knapsack problems. Computational intelligence and neuroscience, 2014, 970456. doi: 10.1155/2014/970456
• Gherboudj, M., Layeb, A., & Drias, H. (2013). Solving 0-1 knapsack problems by a discrete binary version of cuckoo search algorithm. International Journal of Computer Science Issues (IJCSI), 10(3), 87–93. Greenberg, H. (1969). An algorithm for the computation of knapsack functions. Journal of Mathematical Analysis and Applications, 26(1), 159-162. doi: 10.1016/0022-247X(69)90185-1
• Holland, J. H. (1975). Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press.
• Karp, R. M. (1972). Reducibility among combinatorial problems. In R. E. Miller, J. W. Thatcher, & J. D. Bohlinger (Eds.), "complexity of computer computations: Proceedings of a symposium on the complexity of computer computations, held march 20–22, 1972, at the ibm thomas j. watson research center, yorktown heights, new york (pp. 85–103). Boston, MA: Springer US. doi: 10.1007/978-1-4684-2001-2_9
• Khuri, S., Bäck, T., & Heitkötter, J. (1994). The zero/one multiple knapsack problem and genetic algorithms. In Proceedings of the 1994 acm symposium on applied computing (p. 188–193). New York, NY, USA: Association for Computing Machinery. doi: 10.1145/326619.326694
• 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. doi: 10.1007/s00366-020-01240-3
• Orucova, G. B., & Haklı, H. (2023). Binary honey badger algorithm for 0-1 knapsack problem. Journal of Intelligent Systems: Theory and Applications, 6(2), 108–118. doi: 10.38016/jista.1200225
• Pisinger, D. (2005). Where are the hard knapsack problems? Computers & Operations Research, 32(9), 2271–2284. doi: 10.1016/j.cor.2004.03.002
• Schiff, K. (2013). Ant colony optimization algorithm for the 0–1 knapsack problem. Technical Transactions, 110(3-AC), 39–52.
• Shen, X., Wang, W., Zheng, B., & Li, Y. (2006). Based on improved optimizing particle swarm optimization to solve 0-1 knapsack problem. Computer Engineering, 32(18), 23–24.
• Sun, W.-Z., Zhang, M., Wang, J.-S., Guo, S.-S., Wang, M., & Hao, W.-K. (2021). Binary particle swarm optimization algorithm based on z-shaped probability transfer function to solve 0–1 knapsack problem. IAENG International Journal of Computer Science, 48(2), 294–303.
• Yormark, J. S. (1975). Accelerating greenberg’s method for the computation of knapsack functions. Journal of Mathematical Analysis and Applications, 49(3), 695–702. doi: 10.1016/0022-247X(75)90202-4
• Zhou, Y., Bao, Z., Luo, Q., & Zhang, S. (2017). A complex-valued encoding wind driven optimization for the 0-1 knapsack problem. Applied Intelligence, 46(3), 684–702. doi: 10.1007/s10489-016-0855-2
• Zhou, Y., Li, L., & Ma, M. (2015). A complex-valued encoding bat algorithm for solving 0–1 knapsack problem. Neural Processing Letters, 44(3), 407–430. doi: 10.1007/s11063-015-9465-y