We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

A Dynamic Programming based GA for 0-1 Modified Knapsack Problem

by Zaheed Ahmed, Irfan Younas
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 16 - Number 7
Year of Publication: 2011
Authors: Zaheed Ahmed, Irfan Younas
10.5120/2028-2668

Zaheed Ahmed, Irfan Younas . A Dynamic Programming based GA for 0-1 Modified Knapsack Problem. International Journal of Computer Applications. 16, 7 ( February 2011), 1-6. DOI=10.5120/2028-2668

@article{ 10.5120/2028-2668,
author = { Zaheed Ahmed, Irfan Younas },
title = { A Dynamic Programming based GA for 0-1 Modified Knapsack Problem },
journal = { International Journal of Computer Applications },
issue_date = { February 2011 },
volume = { 16 },
number = { 7 },
month = { February },
year = { 2011 },
issn = { 0975-8887 },
pages = { 1-6 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume16/number7/2028-2668/ },
doi = { 10.5120/2028-2668 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:04:13.926459+05:30
%A Zaheed Ahmed
%A Irfan Younas
%T A Dynamic Programming based GA for 0-1 Modified Knapsack Problem
%J International Journal of Computer Applications
%@ 0975-8887
%V 16
%N 7
%P 1-6
%D 2011
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The classical 0-1 knapsack problem is one of the more studied combinatorial optimization problem which belong to the NP class of algorithms. A number of its generalized forms have been addressed by various researchers using different designing techniques. In this paper, we design and analyze the Multiple Knapsack Problems (MKP) by using genetic algorithms. A modified Genetic Algorithm (mGA) is developed with the key focus on efficient encoding scheme for binary string representation and a competent dynamic programming based method for initial population generation. Furthermore transposition is applied in mGA instead of crossover for maintaining the population diversity. Performance analysis of the mGA, justifies our claims that the population incorporates adequate quality and diversity to reach a near optimal solution and transposition reduces the overall computation time.

References
  1. Farhad Djannaty and Saber Doostdar, A Hybrid Genetic Algorithm for the Multidimensional Knapsack Problem, Int. J. Contemp. Math. Sciences, Vol. 3, 2008, no. 9, pp. 443 – 456.
  2. Anabela Simões Ernesto Costa, “Using Genetic Algorithms with Asexual Transposition,” Proceedings of the Genetic and Evolutionary Computation Conference (GECCO' 2000), Las Vegas, USA, 2000, pp. 323-330.
  3. A. Simoes and E. Costa, “On Biologically Inspired Genetic Operators: Transformation in the Standard Genetic Algorithm,” Proceedings the Genetic and Evolutionary Computation Conference, GECCO-2001, San Francisco, USA, 2001, pp.584-591.
  4. Raymond R. Hill, Chaitr S. Hiremath, “Generation Methods for Multidimensional Knapsack Problems and their Implications”, Journal of Systemics, Cybernetics and Informatics, 2007, pp. 59-64.
  5. Gunther R. Raidl, “An Improved Genetic Algorithm for the Multi-constrained 0–1 Knapsack Problem,” Evolutionary Computation Proceedings, 1998. IEEE World Congress on Computational Intelligence, 1998, pp.207 - 211.
  6. Christine L. Mumford, “Comparing Representations and Recombination Operators for the Multi-Objective 0/1 Knapsack Problem,” The 2003 Congress on Evolutionary Computation, IEEE, 2003, pp.854- 861.
  7. Hill, R.R. and Hiremath, C. ‘Improving genetic algorithm convergence using problem structure and domain knowledge in multidimensional knapsack problems’, Int. J. Operational Research, Vol. 1, Nos. 1/2, 2005, pp.145–159.
  8. Crina Groşan, Mihai Oltean, D. Dumitrescu, “A new evolutionary algorithm for the multi-objective 0/1 knapsack problem,” Proceedings of the International Conference on Theory and Applications of Mathematics and Informatics – ICTAMI, 2003, pp. 233-237.
  9. Crina Grosan, “Improving the performance of evolutionary algorithms for the multi-objective 0/1 knapsack problem using ε-dominance,” 2003.
  10. Rajeev Kumar, Nilanjan Banerjee, Analysis of a Multiobjective Evolutionary Algorithm on the 0–1 knapsack problem, Theoretical Computer Science, Elsevier, 2006, pp. 104 – 120.
  11. Yehoon Kim, Jong-Hwan Kim, and Kuk-Hyun Han, Quantum-inspired Multiobjective Evolutionary Algorithm for Multiobjective 0/1 Knapsack Problems, IEEE Congress on Evolutionary Computation, 2006, pp. 2601-2606.
  12. Sachi Nandan Mohanty, Rabinarayan Satapathy, An Evolutionary Multi-Objective Genetic Algorithm To Solve 0 / 1 Knapsack problem, IEEE, 2009.
  13. Khuri, S., Back, T. and Heitkotter, J., “The zero/one multiple knapsack problem and genetic algorithms,” Proceedings of the 1994 ACM Symposium on Applied Computing, SAC ’92, ACM Press, 1994, pp.188–193.
  14. GEN M, CHENG R, IDA K, JIN Y, “Multiple Objective 0-1 Knapsack Problem Using Genetic Algorithms,” Research Reports Ashikaga Institute of Technology, 1998, pp.295-301.
  15. Koksalan, M. and B. Soylu, “An Evolutionary Algorithm for the Multi-objective Multiple Knapsack Problem”, 20th International Conference on Multiple Criteria Decision Making, China, July 2009, pp. 1-8.
  16. Michalewicz, Z. (1996). Genetic Algorithm + Data Structures = Evolution Programming, Springer Verlag, 3rd edition.
  17. Arild Hoff, Arne Løkketangen, Ingvar Mittet, “Genetic Algorithms for 0/1 Multidimensional Knapsack Problems,” Proceedings of Norsk informatikk konferanse, NIK’96, 1996, pp. 291-301.
  18. Z. Ezziane, Solving the 0/1 knapsack problem using an adaptive genetic algorithm, Cambridge Journal, 2002, pp 23-30.
  19. J. L. Gould and W. T. Keeton (1996). Biological Science. W. W. Norton & Company.
  20. A. Simões and E. Costa. “Transposition: A Biologically Inspired Mechanism to Use with Genetic Algorithms,” In the Proceedings of the Fourth International Conference on Neural Networks and Genetic Algorithms (ICANNGA'99), Springer-Verlag, 1999, pp. 612-619.
  21. Anabela Simoes, Ernesto Costa, An Evolutionary Approach to the Zero/One Knapsack Problem: Testing Ideas from Biology, International Conference on Neural Networks and Genetic Algorithms(ICANNGA'01), Prague, Czech Republic, Springer,2001, pp. 236-239.
  22. A. Simões and E. Costa, Enhancing Transposition Performance. Proceedings of the 1999 Congress on Evolutionary Computation (CEC'99), Piscataway, NJ: IEEE Press, 1999, pp.1434-1441
  23. Chanin Srisuwannapa and Peerayuth Charnsethikul,”An Exact Algorithm for the Unbounded Knapsack Problem with Minimizing Maximum Processing Time,” Journal of Computer Science, 2007, 3 (3): 138-143.
  24. Y. Yoon, Y.-H. Kim, B.-R. Moon, “An Evolutionary Lagrangian Method for the 0/1 Multiple Knapsack Problem” ACM, GECCO’05, Washington, DC, USA, 2005
Index Terms

Computer Science
Information Sciences

Keywords

Multiple knapsack problem Genetic algorithm Dynamic programming and transposition

Powered by PhDFocusTM