关键词: 量子粒子群优化算法, 多维多选择背包问题, 精英保留, 局部扰动

Abstract: Aiming at the problem that the multidimensional multichoice knapsack problem (MMKP) couldnot find the optimal solution in polynomialtime. Besides, due to the strong constraint, the solving process would fall into the local optimization easily. We proposed an improved quantum particle swarm optimization (QPSO) algorithm to solve the problem. Firstly, in the process of quantum particle moving, the availability of the position information was determined by judging the position relationship between it and the next iteration individual, and the diversity of the particle was fully preserved by the information. Secondly, a new position disturbance method was proposed to avoid  population falling into local optimization. Finally, the algorithm was tested on the standard data set, and the convergence rate and running time of the algorithm were analyzed. Test results show that the algorithm is significantly improved in solving accuracy.

Key words: quantum particle swarm optimization （QPSO） algorithm, multidimensional multichoice knapsack problem (MMKP), elite retained, local disturbance