Research Article Open Access

An Improved Genetic Algorithm Based on Adaptive Repair Operator for Solving the Knapsack Problem

Sunanda Gupta and M. L. Garg

Abstract

Problem statement: Knapsack problem is a typical NP complete problem. During last few decades, Knapsack problem has been studied through different approaches, according to the theoretical development of combinatorial optimization. Approach: In this study, modified evolutionary algorithm was presented for 0/1 knapsack problem. Results: A new objective_func_evaluation operator was proposed which employed adaptive repair function named as repair and elitism operator to achieve optimal results in place of problem specific knowledge or domain specific operator like penalty operator (which are still being used). Additional features had also been incorporated which allowed the algorithm to perform more consistently on a larger set of problem instances. Conclusion/Recommendations: This study also focused on the change in behavior of outputs generated on varying the crossover and mutation rates. New algorithm exhibited a significant reduction in number of function evaluations required for problems investigated.

Journal of Computer Science
Volume 5 No. 8, 2009, 544-547

DOI: https://doi.org/10.3844/jcssp.2009.544.547

Submitted On: 6 November 2008 Published On: 31 August 2009

How to Cite: Gupta, S. & Garg, M. L. (2009). An Improved Genetic Algorithm Based on Adaptive Repair Operator for Solving the Knapsack Problem . Journal of Computer Science, 5(8), 544-547. https://doi.org/10.3844/jcssp.2009.544.547

  • 3,619 Views
  • 2,288 Downloads
  • 4 Citations

Download

Keywords

  • Knapsack problem
  • genetic algorithm
  • adaptive repair operator