Centre Of Mass Selection Operator Based Meta-Heuristic For Unbounded Knapsack Problem
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.
[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.
[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.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:59955", author = "D.Venkatesan and K.Kannan and S. Raja Balachandar", title = "Centre Of Mass Selection Operator Based Meta-Heuristic For Unbounded Knapsack Problem", 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", volume = "4", number = "7", pages = "979-4", }
