An Adaptive Genetic Algorithm for the 0-1 Knapsack Problem

Kazım Erdoğdu

An Adaptive Genetic Algorithm for the 0-1 Knapsack Problem

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

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/ ĲCISTUDIES.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 (ĲCSI), 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

Details

Primary Language

English

Subjects

Performance Evaluation, Algorithms and Calculation Theory, Query Processing and Optimisation

Journal Section

Research Article

Authors

Kazım Erdoğdu ^*
0000-0001-6256-3114
Türkiye

Publication Date

June 20, 2025

Submission Date

May 1, 2025

Acceptance Date

May 7, 2025

Published in Issue

Year 2025 Volume: 1 Number: 1

IZ

https://izlik.org/JA29WJ42DL

Cite

RIS / Bibtex

APA

Erdoğdu, K. (2025). An Adaptive Genetic Algorithm for the 0-1 Knapsack Problem. Smyrna Journal of Natural and Data Sciences, 1(1), 34-40. https://izlik.org/JA29WJ42DL

AMA

1.Erdoğdu K. An Adaptive Genetic Algorithm for the 0-1 Knapsack Problem. Smyrna Journal of Natural and Data Sciences. 2025;1(1):34-40. https://izlik.org/JA29WJ42DL

Chicago

Erdoğdu, Kazım. 2025. “An Adaptive Genetic Algorithm for the 0-1 Knapsack Problem”. Smyrna Journal of Natural and Data Sciences 1 (1): 34-40. https://izlik.org/JA29WJ42DL.

EndNote

Erdoğdu K (June 1, 2025) An Adaptive Genetic Algorithm for the 0-1 Knapsack Problem. Smyrna Journal of Natural and Data Sciences 1 1 34–40.

IEEE

[1]K. Erdoğdu, “An Adaptive Genetic Algorithm for the 0-1 Knapsack Problem”, Smyrna Journal of Natural and Data Sciences, vol. 1, no. 1, pp. 34–40, June 2025, [Online]. Available: https://izlik.org/JA29WJ42DL

ISNAD

Erdoğdu, Kazım. “An Adaptive Genetic Algorithm for the 0-1 Knapsack Problem”. Smyrna Journal of Natural and Data Sciences 1/1 (June 1, 2025): 34-40. https://izlik.org/JA29WJ42DL.

JAMA

1.Erdoğdu K. An Adaptive Genetic Algorithm for the 0-1 Knapsack Problem. Smyrna Journal of Natural and Data Sciences. 2025;1:34–40.

MLA

Erdoğdu, Kazım. “An Adaptive Genetic Algorithm for the 0-1 Knapsack Problem”. Smyrna Journal of Natural and Data Sciences, vol. 1, no. 1, June 2025, pp. 34-40, https://izlik.org/JA29WJ42DL.

Vancouver

1.Kazım Erdoğdu. An Adaptive Genetic Algorithm for the 0-1 Knapsack Problem. Smyrna Journal of Natural and Data Sciences [Internet]. 2025 Jun. 1;1(1):34-40. Available from: https://izlik.org/JA29WJ42DL