Journal of Computer Science

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

Sunanda Gupta and M. L. Garg

DOI : 10.3844/jcssp.2009.544.547

Journal of Computer Science

Volume 5, Issue 8

Pages 544-547

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.

Copyright

© 2009 Sunanda Gupta and M. L. Garg. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.