A New Genetic Algorithm for the 0-1 Knapsack Problem
Loading...
Date
2016
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 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.
Description
ORCID
Keywords
Bilgisayar Bilimleri- Yazılım Mühendisliği, Bilgisayar Bilimleri, Yazılım Mühendisliği
Fields of Science
Citation
Kellerer H. Pferschy U. Pisinger D. Knapsack Problems (Springer Berlin 2004).Garey M. R. and Johnson D. S. Computers and Intractability: A Guide to the Theory of NP- Completeness (Freeman San Francisco 1979).Sahni S. Approximate algorithms for the 0/1 knapsack problems Journal of ACM 1 115-124 (1975).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).Martello S. and Toth P. Knapsack Problems (John Wiley&Sons England 1990).Horowitz E. Sahni S. and Rajasekaran S. Computer algorithms (New York: Computer Science Press W.H. Freeman & Co. 1994).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).Goldberg D.E. Genetic Algorithms in Search Optimization and Machine Learning (Addison- Wesley 1989).Chu P. A Genetic Algorithm Approach for Combinatorial Optimization Problems Ph.D. thesis at the Management School Imperial College of Science London (1997).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).Falkenauer E. A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics 2 5-30 (1996).Hussain S. A. and Sastry V. U. K. Application of genetic algorithm for bin packing International Journal of Computer Mathematics 63 203-214 (1997).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).Battiti R. Tecchiolli G. Parallel biased search for combinatorial optimization: Genetic algorithms and tabu search Microprocessors and Microsystems 16 351-367 (1992).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).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).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)
WoS Q
Scopus Q
Source
Academic Platform-Journal of Engineering and Science
Volume
4
Issue
3
Start Page
9
End Page
14
Collections
