KaydedilenlerDerginizi ekleyin

Dergiler / ACADEMIC PLATFORM-JOURNAL OF ENGINEERING AND SCIENCE / 2016 / Cilt: 4 - Sayı: 3

A New Genetic Algorithm for the 0-1 Knapsack Problem

Aslı GÜLER
MURAT ERŞEN BERBERLER
Urfat G. NURİYEV
Sayfa
9–14
DOI
—
🏛️Bu makalenin bibliyografik verileri ve tam metin bağlantısı DergiPark üzerinden sağlanmıştır.
DergiPark Kaydı ↗
✨

Yapay Zeka Hızlı Bakış & Çıkarımlar

AI Insight
⚡ TL;DR(1 Cümlede Hızlı Çıkarım)

It is seen that the algorithm yields optimal solutions for all instances.

📌 3 Maddede Bu Makale

🎯
Amaç & Hipotez: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.
📊
Temel Bulgular & Veri:In our methodology, n items are represented by n genes on a bit array that compactly stores the values 0 or 1.
💡
Sonuç & Katkı:It is seen that the algorithm yields optimal solutions for all instances.
🔬Tür:Araştırma Makalesi
📍Kapsam:Genişletilmiş Akademik Örneklem
⚙️Değişkenler:Alan Parametreleri

Abstract

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 choosing 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.

🔖

Bu Makaleye Atıf Yap

GÜLER, A., BERBERLER, M. E., NURİYEV, U. G. (2016). A New Genetic Algorithm for the 0-1 Knapsack Problem. ACADEMIC PLATFORM-JOURNAL OF ENGINEERING AND SCIENCE, Cilt: 4 - Sayı: 3, 9–14. https://ajindex.com/articles/146207

📄 Tam Metin PDF Okuyucu

📄

PDF görüntüleyici hazırlanıyor...

Kaynakça (20)

  1. Kellerer H., Pferschy U., Pisinger D., Knapsack Problems, (Springer, Berlin, 2004).
  2. Garey M. R. and Johnson D. S., Computers and Intractability: A Guide to the Theory of NP- Completeness, (Freeman, San Francisco, 1979).
  3. Sahni, S., Approximate algorithms for the 0/1 knapsack problems, Journal of ACM, 1, 115-124 (1975).
  4. 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).
  5. Martello, S. and Toth, P., Knapsack Problems, (John Wiley&Sons, England, 1990).
  6. Horowitz E., Sahni, S. and Rajasekaran, S., Computer algorithms, (New York: Computer Science Press, W.H. Freeman & Co., 1994).
  7. Berberler M.E., Nuriyev U.G., A new heuristic algorithm for the one-dimensional cutting stock problem, Applied and Computational Mathematics, Vol. 9, No. 1, 19-30, (2010).
  8. Goldberg, D.E., Genetic Algorithms in Search, Optimization and Machine Learning, (Addison- Wesley, 1989).
  9. Chu, P., A Genetic Algorithm Approach for Combinatorial Optimization Problems, Ph.D. thesis at the Management School, Imperial College of Science, London, (1997).
  10. 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).
  11. Falkenauer, E., A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics, 2, 5-30 (1996).
  12. Hussain, S. A., and Sastry, V. U. K., Application of genetic algorithm for bin packing, International Journal of Computer Mathematics, 63, 203-214 (1997).
  13. 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
  14. ACM symposium of Applied Computation, ACM Press, New York 188-193 (1994).
  15. Battiti, R., Tecchiolli, G., Parallel biased search for combinatorial optimization: Genetic algorithms and tabu search, Microprocessors and Microsystems, 16, 351-367 (1992).
  16. Khan M. H. A., An Evolutionary Algorithm with Masked Mutation for 0/1 Knapsack Problem, Proceedings of Informatics, Electronics & Vision (ICIEV), 2013
  17. International Conference on, IEEE, 1-6 (2013).
  18. Zhao J., Pang F., Huang T. and Liu Y., Genetic algorithm based on Greedy strategy in the 0-1
  19. Knapsack Problem, Proceedings of Third International Conference on Genetic and Evolutionary Computing, IEEE, 105-107 (2009).
  20. Neoh S. C., Morad N., Lim C. P. and Aziz Z. A., A GA-PSO layered encoding evolutionary approach to 0/1 knaps