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

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.