A MODIFIED AND EFFICIENT GENETIC ALGORITHM TO SOLVE 0-1 KNAPSACK PROBLEM

Abstract

This paper presents a fast and efficient Genetic Algorithms, which is successful in reducing the computational effort required. Time complexity can be avoidable if scale of problem is small but in case of large data set it is noticeable factor. And to prove its effectiveness and efficiency it is applied on 0-1 Knapsack Problem. Knapsack Problem is one of well known Np-hard problem, Np-hard  problem solution is verified in polynomial time. Every new research carried out some enhancement over earlier researches. In the same way this research presents some improvement by comparing its results with conventional GA.  Early Researches works out on many approaches to solve Knapsack Problems but here we are focussing on one of them, i.e. GA. In this a 0-1 Knapsack Problem is created and fast GA is applied on that to show its effective performance. Results shows that time complexity reduces and we achieved a solution in less amount of time in comparision to conventional GA.