Centre Of Mass Selection Operator Based Meta-Heuristic For Unbounded Knapsack Problem

Authors: D.Venkatesan, K.Kannan, S. Raja Balachandar

Abstract:

In this paper a new Genetic Algorithm based on a heuristic operator and Centre of Mass selection operator (CMGA) is designed for the unbounded knapsack problem(UKP), which is NP-Hard combinatorial optimization problem. The proposed genetic algorithm is based on a heuristic operator, which utilizes problem specific knowledge. This center of mass operator when combined with other Genetic Operators forms a competitive algorithm to the existing ones. Computational results show that the proposed algorithm is capable of obtaining high quality solutions for problems of standard randomly generated knapsack instances. Comparative study of CMGA with simple GA in terms of results for unbounded knapsack instances of size up to 200 show the superiority of CMGA. Thus CMGA is an efficient tool of solving UKP and this algorithm is competitive with other Genetic Algorithms also.

Keywords: Genetic Algorithm, Unbounded Knapsack Problem, Combinatorial Optimization, Meta-Heuristic, Center of Mass

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1076162

References:

[1] Andonov R, Poirriez V, Rajopadhye S, Unbounded knapsack problem: Dynamic Programming revisited, European Journal of Operation Research, Vol. 123, pp.394-407, 2000.
[2] Back T. Fogel D B, Michalewiez Z (eds.), Handbook of Evolutionary Computation, Oxford University Press, 1975.
[3] D.Beasley, D.R.Bull, and R.R.Martin ,An overview of genetic algorithms: Part I. fundamentals, University computing , 15, 58-69, 1993.
[4] D. Beasley, D.R.Bull, and R.R.Martin, An overview of genetic algorithms: Part II. Research topics, University computing ,15,170-181, 1993.
[5] Bellman R. and Dreyfus.S.E., Applied Dynamic Programming, Princeton University Press, Princeton, NJ, 27-31 , 1962.
[6] Chanin Srisuwannapa, Peerayuth Charnsethikul, An Exact Algorithm for the Unbounded Knapsack problem with Minimizing Maximum Processing Time, Journal of Computer Science 3 (3): 138-143, 2007.
[7] P.C.Chu and J.E.Beasely, A Genetic Algorithm for the Generalized Assignment Problem, Computer Ops. Res. , vol. 24, No.1, 17-23, 1997..
[8] P.C.Chu and J.E.Beasely, A Genetic Algorithm for the Multi-dimensional Knapsack problem, Journal of Heuristics, Vol. 4, 63-86,1998.
[9] Dudzinski.K, A note on dominance relation in unbounded knapsack problems, Operation Research Letters, 10(7), 417-419, 1991.
[10] Garey M R. Johnson D S, Computers and intractability, A guide to theory of NP-Completeness, Freeman and Co., San Francisco, 1979.
[11] D.E. Goldberg, Genetic Algorithms in search, optimization and machine learning, Addition Wesley, Reading, MA,1989.
[12] Hans Kellerer, Ulrich Pferschy, David Pisinger, Knapsack Problems, Springer - Verlag , 2003.
[13] Ken-li Li, Guang-ming Dal, Qing-hua Li, A Genetic Algorithm for the Unbounded Knapsack Problem, Proceedings of the Second International conference on Machine Learning and Cybernetics, Xi-an, IEEE, 2-5 November 2003.
[14] Kulanoot Araya , Algorithms for some hard knapsack problems , PhD Thesis , Curtin University of Technology, 2000.
[15] 15. Martello S Toth P, Knapsack problems: Algorithms and Computer implementation, Wiley, New York, 1990.
[16] Martello.S, toth.P., An exact algorithm for large unbounded knapsack problems, Operation Research letters, 9(1), 15-20, 1990.
[17] Osman K.Erol, Ibrahim Eksin, A new optimization method: Big Bang- Big Crunch, Advances in Engineering Software 37, 106-111, 2006.
[18] Poirriez, V., Yanev, N., Andonov, R., A hybrid algorithm for the unbounded knapsack problem, Discrete Optimization, 6(1),110-124, 2009.
[19] Rung-Ching Chen, Cheng-Huei Jian,Yung-Fa Huang, Solving Unbounded Knapsack Problem using an Adaptive Genetic Algorithm with Elitism Strategy, International Journal of Smart Home, Vol. 2, No. 2, 139-150, 2008.
[20] Shih.w, A branch and bound method for the multi constraint 0-1 knapsack problem, J.Oper.Res.Soc., 30, 369-378, 1979.
[21] D.Venkatesan, K.Kannan, R.Saravanan, A genetic algorithm-based artificial neural network model for The optimization of machining processes, Neural Computing and Applications, 18,135-140, 2009.