Genetic Tabu Search Algorithm To Solve The Knapsack Problem

The Knapsack problem is one of combinatorial optimization problem, It is also an NP-complete problem and as such an exact solution for a large input is practically impossible to obtain. The Knapsack problem is used in many fields. On the design of solving the cosmically complicated combinatorial optimization problem, The Knapsack problem often appears as sub-problem. So it is meaningful for optimizing the combinatorial optimization problem to improving the Knapsack problem by the results of the former investigation .On the base of researching of knapsack problem, This paper compares and analyses several algorithm which are applied to a single problem - the 0/1 Knapsack problem, presents a comparative study of the brute force, dynamic programming, memory functions, branch and bound, greedy, and genetic algorithms. Our experimental results show that the most promising approaches are dynamic programming and genetic algorithms. In allusion to genetic algorithms is subjected to premature, we utilize the main frame of parallel search supplied by the genetic algorithm and the tabu algorithm .TS adopts individual serial search mode. So TS is able to overcome premature convergence of genetic algorithms.At the same time, In allusion to the constringent speed of GA added with tabu search algorithm are slow and the implement efficiencies are low, this paper introduces greedy algorithm to the above algorithm .The experiment results show that the algorithm have advantages in implement efficiency and constringent speed.