Yıl 2016, Cilt 4, Sayı 3, Sayfalar 0 - 0 2016-10-01

A New Genetic Algorithm for the 0-1 Knapsack Problem

Murat Erşen Berberler [1] , Aslı Güler [2] , Urfat Nuriyev [3]

670 290

In this paper, The 0-1 Knapsack Problem (KP) which occurs in many different applications is studied and a new genetic algorithm to solve the KP is proposed. In our methodology, n items are represented by n genes on a bit array that compactly stores the values 0 or 1. When calculating fitness values of items, coefficients of items whose values are 1 in the bit array are summed. Roulette wheel method is used for chosing parents; in this way it is provided that strong individuals produce more children. Crossover is applied in such a way  that roulette wheel is rotated on genes with the same index of parents, that the dominant parent can transfer its genes to the child. Mutation is applied for randomly chosen 25% genes and this process is repeated for the number of individuals. The algorithm is written in C programming language and is tested on randomly generated instances. In order to find the optimal solutions of these problems, a program that has been written by dynamic programming technique is used. It is seen that the algorithm yields optimal solutions for all instances.

  • R. Battiti, G. Tecchiolli, Parallel biased search for combinatorial optimization: Genetic algorithms and tabu search, Microprocessors and Microsystems, 16, 351–367 (1992).
  • P. C. Chu: A Genetic Algorithm Approach for Combinatorial Optimization Problems, Ph.D. thesis at the Management School, Imperial College of Science, London, (1997).
  • Chu, P., and Beasley, J., A genetic algorithm for the multidimensional knapsack problem. Journal of Heuristics, 4, 63–86 (1998).
  • Falkenauer, E., A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics, 2, 5–30 (1996).
  • Garey M. R. and Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, (Freeman, San Francisco, 1979).
  • D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, (Addison–Wesley, 1989).
  • Horowitz E., Sahni, S. and Rajasekaran, S., Computer algorithms, (New York: Computer Science Press, W.H. Freeman & Co., 1994).
  • Hussain, S. A., and Sastry, V. U. K., Application of genetic algorithm for bin packing, International Journal of Computer Mathematics, 63, 203–214 (1997).
  • Ibarra, O. H and Kim, C. E., Fast approximation algorithms for the knapsack and sum of subset problems, Journal of ACM, 22(4), 463-468 (1975).
  • Kellerer H., Pferschy U., Pisinger D., Knapsack Problems, (Springer, Berlin, 2004).
  • Khan M. H. A., An Evolutionary Algorithm with Masked Mutation for 0/1 Knapsack Problem, Proceedings of Informatics, Electronics & Vision (ICIEV), 2013 International Conference on, IEEE, 1-6 (2013).
  • Khuri, S., Back, T., Heitkotter, J.: The zero/one multiple knapsack problem and genetic algorithms. In: Deaton, E., et al. (eds.) Proc. of the 1994 ACM symposium of Applied Computation, ACM Press, New York 188–193 (1994).
  • Martello, S. and Toth, P., Knapsack Problems, (John Wiley&Sons, England, 1990).
  • Neoh S. C., Morad N., Lim C. P. and Aziz Z. A., A GA-PSO layered encoding evolutionary approach to 0/1 knapsack optimization, International journal of innovative computing, information and control 6 (8) 3489-3505 (2010).
  • Sahni, S., Approximate algorithms for the 0/1 knapsack problems, Journal of ACM, 1, 115-124 (1975).
  • Spillman, R., Solving large knapsack problems with a genetic algorithm. Proceedings of IEEE International Conference Systems, Man, and Cybernetics, Vancouver, Canada. Piscataway, NJ: IEEE, 632– 637 (1995).
  • Zhao J., Pang F., Huang T. and Liu Y., Genetic algorithm based on Greedy strategy in the 0-1 Knapsack Problem, Proceedings of Third International Conference on Genetic and Evolutionary Computing, IEEE, 105-107 (2009).
Konular
Dergi Bölümü Makaleler
Yazarlar

Yazar: Murat Erşen Berberler

Yazar: Aslı Güler

Yazar: Urfat Nuriyev

Bibtex @ { apjes287564, journal = {Akademik Platform Mühendislik ve Fen Bilimleri Dergisi}, issn = {}, eissn = {2147-4575}, address = {Akademik Platform}, year = {2016}, volume = {4}, pages = {0 - 0}, doi = {10.21541/apjes.14020}, title = {A New Genetic Algorithm for the 0-1 Knapsack Problem}, key = {cite}, author = {Nuriyev, Urfat and Berberler, Murat Erşen and Güler, Aslı} }
APA Berberler, M , Güler, A , Nuriyev, U . (2016). A New Genetic Algorithm for the 0-1 Knapsack Problem. Akademik Platform Mühendislik ve Fen Bilimleri Dergisi, 4 (3), 0-0. DOI: 10.21541/apjes.14020
MLA Berberler, M , Güler, A , Nuriyev, U . "A New Genetic Algorithm for the 0-1 Knapsack Problem". Akademik Platform Mühendislik ve Fen Bilimleri Dergisi 4 (2016): 0-0 <http://dergipark.gov.tr/apjes/issue/27314/287564>
Chicago Berberler, M , Güler, A , Nuriyev, U . "A New Genetic Algorithm for the 0-1 Knapsack Problem". Akademik Platform Mühendislik ve Fen Bilimleri Dergisi 4 (2016): 0-0
RIS TY - JOUR T1 - A New Genetic Algorithm for the 0-1 Knapsack Problem AU - Murat Erşen Berberler , Aslı Güler , Urfat Nuriyev Y1 - 2016 PY - 2016 N1 - doi: 10.21541/apjes.14020 DO - 10.21541/apjes.14020 T2 - Akademik Platform Mühendislik ve Fen Bilimleri Dergisi JF - Journal JO - JOR SP - 0 EP - 0 VL - 4 IS - 3 SN - -2147-4575 M3 - doi: 10.21541/apjes.14020 UR - http://dx.doi.org/10.21541/apjes.14020 Y2 - 2018 ER -
EndNote %0 Akademik Platform Mühendislik ve Fen Bilimleri Dergisi A New Genetic Algorithm for the 0-1 Knapsack Problem %A Murat Erşen Berberler , Aslı Güler , Urfat Nuriyev %T A New Genetic Algorithm for the 0-1 Knapsack Problem %D 2016 %J Akademik Platform Mühendislik ve Fen Bilimleri Dergisi %P -2147-4575 %V 4 %N 3 %R doi: 10.21541/apjes.14020 %U 10.21541/apjes.14020
ISNAD Berberler, Murat Erşen , Güler, Aslı , Nuriyev, Urfat . "A New Genetic Algorithm for the 0-1 Knapsack Problem". Akademik Platform Mühendislik ve Fen Bilimleri Dergisi 4 / 3 (Ekim 2016): 0-0. http://dx.doi.org/10.21541/apjes.14020