A New Genetic Algorithm for the 0-1 Knapsack Problem

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

References

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: A Genetic Algorithm Approach for Combinatorial Optimization Problems, Ph.D. thesis at the Management School, Imperial College of Science, London, (1997).
3. Chu, P., and Beasley, J., A genetic algorithm for the multidimensional knapsack problem. Journal of Heuristics, 4, 63–86 (1998).
4. Falkenauer, E., A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics, 2, 5–30 (1996).
5. Garey M. R. and Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, (Freeman, San Francisco, 1979).
6. D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, (Addison–Wesley, 1989).
7. Horowitz E., Sahni, S. and Rajasekaran, S., Computer algorithms, (New York: Computer Science Press, W.H. Freeman & Co., 1994).
8. Hussain, S. A., and Sastry, V. U. K., Application of genetic algorithm for bin packing, International Journal of Computer Mathematics, 63, 203–214 (1997).

9. 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).
10. Kellerer H., Pferschy U., Pisinger D., Knapsack Problems, (Springer, Berlin, 2004).
11. 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).
12. 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).
13. Martello, S. and Toth, P., Knapsack Problems, (John Wiley&Sons, England, 1990).
14. 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).
15. Sahni, S., Approximate algorithms for the 0/1 knapsack problems, Journal of ACM, 1, 115-124 (1975).
16. 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).
17. 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).