Study Of Knapsack Problem Based On Probability Particle Swarm Optimization Algorithm

Knapsack problem is belongs among NP-hard problems, and it is also one of the combinatorial optimization problems. Knapsack problem has wide applications in a lot of fields, so it is meaningful for optimizing the combinatorial optimization problem.In this thesis, an improved algorithm based on probability particle swarm optimization is proposed, which is used for solving 0-1 knapsack problem, after analyzing and comparing kinds of methods to knapsack problem. It improves the performance through operating on the probability vector which helps the group evolve. And then we solve different scales of knapsack problem with the new algorithm. The experiment results show that the algorithm has advantages in implement efficiency and constringent speed.