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

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.