KaydedilenlerDerginizi ekleyin

Dergiler / Mathematical and Computational Applications / 2013 / Cilt: 18 - Sayı: 3

A GENETIC ALGORITHM TO SOLVE THE MULTIDIMENSIONAL KNAPSACK PROBLEM

MURAT ERŞEN BERBERLER
Aslı GÜLER
Urfat G. NURİYEV
Sayfa
486–494
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 Multidimensional Knapsack Problem (MKP) which occurs in many different applications is studied and a genetic algorithm to solve the MKP is proposed.
📊
Temel Bulgular & Veri:Unlike the technique of the classical genetic algorithm, initial population is not randomly generated in the proposed algorithm, thus the solution space is scanned more efficiently.
💡
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 Multidimensional Knapsack Problem (MKP) which occurs in many different applications is studied and a genetic algorithm to solve the MKP is proposed. Unlike the technique of the classical genetic algorithm, initial population is not randomly generated in the proposed algorithm, thus the solution space is scanned more efficiently. Moreover, the algorithm is written in C programming language and is tested on randomly generated instances. It is seen that the algorithm yields optimal solutions for all instances.

🔖

Bu Makaleye Atıf Yap

BERBERLER, M. E., GÜLER, A., NURİYEV, U. G. (2013). A GENETIC ALGORITHM TO SOLVE THE MULTIDIMENSIONAL KNAPSACK PROBLEM. Mathematical and Computational Applications, Cilt: 18 - Sayı: 3, 486–494. https://ajindex.com/articles/279804

📄 Tam Metin PDF Okuyucu

📄

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

Kaynakça (16)

  1. R Battiti, G. Tecchiolli, Parallel biased search for combinatorial optimization: Genetic algorithms and tabu search, Microprocessors and Microsystems 16, 351- 367, 1992
  2. P. C. Chu and J. E. Beasley, A genetic algorithm for the multidimensional knapsack problem, Journal of Heuristics 4, 63-86, 1998
  3. A. Freville, The multidimensional 0-1 knapsack problem: An overview, European Journal of Operational Research 155, 1-21, 2004
  4. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 338p, 1979
  5. B. Gavish, H. Pirkul, Efficient Algorithms for Solving Multiconstraint Zero-One Knapsack Problems to Optimality, Mathematical Programming 31, 78-105, 1985
  6. D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, 1989
  7. J. Gotlieb, On the effectivity of evolutionary algorithms for multidimensional knapsack problem, Proceedings of the 4th European Conference of Artificial Evolution, Dunkerque, France, LNCS no. 1829, 23-27, 1999
  8. C. Haul, S. Voss, Using surrogate constraints in genetic algorithms for solving multidimensional knapsack problems, D.L Woodruff (Ed.), Advances in Computational and Stochastic Optimization, Logic Programming, and Heuristic Search, Kluwer Academic Publishers, pp. 235-251, 1998
  9. H. Kellerer, U. Pferschy, D. Pisinger, Knapsack Problems, Springer, Berlin, 546p, 2004
  10. S. Khuri, T. Back, J. Heitkotter, The Zero/One Multiple Knapsack Problem and Genetic Algorithms, ACM Symposium on Applied Computing, 188-193, ACM Press, 1994
  11. E. Lin, A bibliographical survey on some well-known non-standard knapsack problems, INFOR, 36:274-317, 1998
  12. J. Puchinger, G. R. Raidl, U. Pferschy, The Multidimensional Knapsack Problem: Structure and Algorithms, INFORMS Journal on Computing 22:2, 250-265, 2010
  13. R. Raidl Gunther, An improved genetic algorithm for the multiconstrained 0-1 knapsack problem, D. Fogel, et al., eds., Proceedings of the 5th IEEE International Conference on Evolutionary Computation. IEEE Press, 207-211, 1998
  14. R. Raidl Gunther, Jens Gottlieb, Empirical analysis of locality, heritability and heuristic bias in evolutionary algorithms: A case study for the multidimensional knapsack problem, Evolutionary Computation Journal 13:4, 441-475, 2005
  15. J. Thiel, S. Voss, Some experiences on solving multiconstraint zero-one knapsack problems with genetic algorithms, INFOR 32, 226-242, 1994
  16. M. Vasquez, J.-