A quantum evolutionary algorithm for quadratic multiple knapsack problem

The quadratic multiple knapsack problem is a new problem that combines the two classical NP-hard problems of quadratic knapsack problem and multiple knapsack problem. It is difficult to solve this problem due to the multi-variable coupling. In addition, the existing heuristic algorithms for this problem are not accurate and efficient enough. To solve the problem, a new quantum-inspired evolutionary algorithm (QEA) is proposed. New quantum observation in this algorithm is able to decode quantum and to handle a part of the constraints of this problem at the same time. This ensures that there is no problem of trapping in a local optimality and frequent decoding that often plagues standard QEA. A self-adaptive quantum updating mode in this algorithm is more efficient compared with the traditional look-up table in QEA. Local and global repair operators are developed to maintain the feasibility of the populations. Moreover, an exchange operator is presented to enhance the searching around the boundary. In experiments on standard quadratic multiple knapsack problem instances, the algorithm performs better than the other related algorithms in terms of accuracy and efficiency. ©, 2015, Science Press. All right reserved.