Greedy quantum-inspired evolutionary algorithm for quadratic knapsack problem
Zheng Jian-guo · Computer Integrated Manufacturing Systems · 2012
The quadratic knapsack problem is a kind of NP-Hard problem.It is difficult to solve this problem with the exact algorithms.To solve the problem,a new quantum-inspired evolutionary algorithm was proposed.The algorithm had a dynamic repair operator which considered two types of value: the value of an object and the value of associated with an object in the knapsack problem.At the same time,an improved quantum updating mode using three kinds of knowledge based on particle swarm optimization algorithm was presented.In this updating mode,the quantum could get more comprehensive knowledge during evolution.Performance of the algorithm on 100 standard quadratic knapsack problem instances was compared with other heuristic techniques.Results showed that the proposed algorithm was superior to these techniques in many aspects.