{"title":"Centre Of Mass Selection Operator Based Meta-Heuristic For Unbounded Knapsack Problem","authors":"D.Venkatesan, K.Kannan, S. Raja Balachandar","volume":43,"journal":"International Journal of Mathematical and Computational Sciences","pagesStart":1031,"pagesEnd":1035,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/10903","abstract":"<p>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.<\/p>\r\n","references":"[1] Andonov R, Poirriez V, Rajopadhye S, Unbounded knapsack problem:\r\nDynamic Programming revisited, European Journal of Operation Research,\r\nVol. 123, pp.394-407, 2000.\r\n[2] Back T. Fogel D B, Michalewiez Z (eds.), Handbook of Evolutionary\r\nComputation, Oxford University Press, 1975.\r\n[3] D.Beasley, D.R.Bull, and R.R.Martin ,An overview of genetic algorithms:\r\nPart I. fundamentals, University computing , 15, 58-69, 1993.\r\n[4] D. Beasley, D.R.Bull, and R.R.Martin, An overview of genetic algorithms:\r\nPart II. Research topics, University computing ,15,170-181, 1993.\r\n[5] Bellman R. and Dreyfus.S.E., Applied Dynamic Programming, Princeton\r\nUniversity Press, Princeton, NJ, 27-31 , 1962.\r\n[6] Chanin Srisuwannapa, Peerayuth Charnsethikul, An Exact Algorithm for\r\nthe Unbounded Knapsack problem with Minimizing Maximum Processing\r\nTime, Journal of Computer Science 3 (3): 138-143, 2007.\r\n[7] P.C.Chu and J.E.Beasely, A Genetic Algorithm for the Generalized\r\nAssignment Problem, Computer Ops. Res. , vol. 24, No.1, 17-23, 1997..\r\n[8] P.C.Chu and J.E.Beasely, A Genetic Algorithm for the Multi-dimensional\r\nKnapsack problem, Journal of Heuristics, Vol. 4, 63-86,1998.\r\n[9] Dudzinski.K, A note on dominance relation in unbounded knapsack\r\nproblems, Operation Research Letters, 10(7), 417-419, 1991.\r\n[10] Garey M R. Johnson D S, Computers and intractability, A guide to\r\ntheory of NP-Completeness, Freeman and Co., San Francisco, 1979.\r\n[11] D.E. Goldberg, Genetic Algorithms in search, optimization and machine\r\nlearning, Addition Wesley, Reading, MA,1989.\r\n[12] Hans Kellerer, Ulrich Pferschy, David Pisinger, Knapsack Problems,\r\nSpringer - Verlag , 2003.\r\n[13] Ken-li Li, Guang-ming Dal, Qing-hua Li, A Genetic Algorithm for the\r\nUnbounded Knapsack Problem, Proceedings of the Second International\r\nconference on Machine Learning and Cybernetics, Xi-an, IEEE, 2-5\r\nNovember 2003.\r\n[14] Kulanoot Araya , Algorithms for some hard knapsack problems , PhD\r\nThesis , Curtin University of Technology, 2000.\r\n[15] 15. Martello S Toth P, Knapsack problems: Algorithms and Computer\r\nimplementation, Wiley, New York, 1990.\r\n[16] Martello.S, toth.P., An exact algorithm for large unbounded knapsack\r\nproblems, Operation Research letters, 9(1), 15-20, 1990.\r\n[17] Osman K.Erol, Ibrahim Eksin, A new optimization method: Big Bang-\r\nBig Crunch, Advances in Engineering Software 37, 106-111, 2006.\r\n[18] Poirriez, V., Yanev, N., Andonov, R., A hybrid algorithm for the unbounded\r\nknapsack problem, Discrete Optimization, 6(1),110-124, 2009.\r\n[19] Rung-Ching Chen, Cheng-Huei Jian,Yung-Fa Huang, Solving Unbounded\r\nKnapsack Problem using an Adaptive Genetic Algorithm with\r\nElitism Strategy, International Journal of Smart Home, Vol. 2, No. 2,\r\n139-150, 2008.\r\n[20] Shih.w, A branch and bound method for the multi constraint 0-1\r\nknapsack problem, J.Oper.Res.Soc., 30, 369-378, 1979.\r\n[21] D.Venkatesan, K.Kannan, R.Saravanan, A genetic algorithm-based artificial\r\nneural network model for The optimization of machining processes,\r\nNeural Computing and Applications, 18,135-140, 2009.","publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 43, 2010"}