A GENETIC ALGORITHM TO SOLVE THE MULTIDIMENSIONAL KNAPSACK PROBLEM
Loading...
Date
2013
Authors
MURAT ERSEN BERBERLER
Urfat G. NURİYEV
Aslı GÜLER
Journal Title
Journal ISSN
Volume Title
Publisher
Open Access Color
OpenAIRE Downloads
OpenAIRE Views
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.
Description
Keywords
Matematik-Bilgisayar Bilimleri- Teori ve Metotlar
Fields of Science
Citation
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.-K. Hao A hybrid approach for the 0-1 multidimensional knapsack problem Proceedings of the Int. Joint Conference on Artificial Intelligence Seattle Washington 328-333 2001.17. M. Vasquez V. Yannick Improved results on the 0-1 multidimensional knapsack problem European Journal of Operational Research 165 70-81 2005.
WoS Q
Scopus Q
Source
Volume
Issue
Start Page
End Page
Collections
