Application of Genetic Algorithm on Knapsack Problem for Optimization of Goods Selection

Indah Mauludina Hasanah, Lukman Widoyo Mulyo, Muhammad Fardeen Khan, Rizki Apriva Hidayana

Abstract


Knapsack Problemis one of the combinatorial optimization problems that often arise in everyday life, especially in making decisions about selecting goods with limited capacity. This study combines two previous studies that apply genetic algorithms to real cases: the selection of basic necessities and packaged fruits in limited containers. Genetic algorithms are used because they are flexible and able to find more than one optimal solution. The process includes the formation of an initial population, fitness evaluation, selection (roulette wheel), crossover, and mutation. From the two case studies analyzed, it was found that genetic algorithms consistently produce increased fitness between generations and are able to maximize the value of goods without exceeding capacity or budget limits. This study strengthens the potential of genetic algorithms as an effective method in solving Knapsack Problems based on real needs.

Keywords


Genetic Algorithm; Knapsack Problem; Optimization of Goods; Selection of Basic Necessities; Packaged Fruits

Full Text:

PDF

References


Abdennadher, S., & Schlenker, H. (1999). Genetic Algorithms for Course Scheduling Problems. Proceedings of the First International Conference on the Practice and Theory of Automated Timetabling (PATAT).

Chu, P. C., & Beasley, J. E. (1998). A Genetic Algorithm for the Multidimensional Knapsack Problem. Journal of Heuristics, 4, 63–86. http://dx.doi.org/10.1023/A:1009642405419

Deep, K., Singh, K. P., Kansal, M. L., & Mohan, C. (2009). A real coded genetic algorithm for solving integer and mixed integer optimization problems. Applied Mathematics and Computation, 212(2), 505–518.

Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley.

Hassan, O. M. S., & Saleh, S. A. (2025). Comprehensive Analysis of Recent Studies on Using Genetic Algorithms for Optimizing Solutions to the 0/1 Knapsack Problem. European Journal of Applied Science & Engineering Technology, 3(2), 74–86.

Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.

Kaya, M. (2023). “Applying Developed Genetic Algorithm Operators to Knapsack Problems.” Global Journal of Computer Sciences: Theory and Research, 13(2), 75–91.

Kilincli Taskiran, G. (2010). An Improved Genetic Algorithm for Knapsack Problems (Master’s thesis). Wright State University.

https://corescholar.libraries.wright.edu/etd_all/1034/

Kumar, A., & Kapoor, A. (2021). Consumer Behavior Towards Traditional and Modern Retail Outlets: A Comparative Study in India. International Journal of Retail & Distribution Management, 49(6), 745–760.

https://doi.org/10.1108/IJRDM-01-2020-0015

Martello, S., & Toth, P. (1990). Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons.

Okwu, M. O., Otanocha, O. B., et al. (2020). Appraisal of Genetic Algorithm and Its Application in 0–1 Knapsack Problem. Journal of Mechanical and Energy Engineering, 4(44), 39–46.

Rajabioun, R. (2011). Genetic Algorithm for Solving the 0–1 Knapsack Problem. International Journal of Computer Applications, 25(10), 21–25.

https://doi.org/10.5120/3111-4295




DOI: https://doi.org/10.46336/ijqrm.v6i2.1020

Refbacks

  • There are currently no refbacks.


Copyright (c) 2025 Indah Mauludina Hasanah, Lukman Widoyo Mulyo, Muhammad Fardeen Khan, Rizki Apriva Hidayana

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Published By: 

IJQRM: Jalan Riung Ampuh No. 3, Riung Bandung, Kota Bandung 40295, Jawa Barat, Indonesia

 

IJQRM Indexed By: 

width=width= width= width= width= width= width= 

 


Lisensi Creative Commons Creation is distributed below Lisensi Creative Commons Atribusi 4.0 Internasional.


View My Stats