SavedAdd your journal

Journals / 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
Pages
486–494
DOI
—
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

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

📌 3 Key Takeaways

🎯
Objective & Hypothesis: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.
📊
Key Findings & Data: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.
💡
Conclusion & Impact:It is seen that the algorithm yields optimal solutions for all instances.
🔬Design:Research Article
📍Scope:Comprehensive Sample
⚙️Variables:Domain Parameters

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.

🔖

Cite This Article

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

📄 Full Text PDF Viewer

📄

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

References (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.-