改进的量子粒子群优化算法对多维多选择背包问题的求解

来源：吉林大学学报·理学版杂志2018年第6期北京时间：

作者：杨雪, 董红斌, 董宇欣

单位：哈尔滨工程大学 计算机科学与技术学院, 哈尔滨 150001

摘要：针对多维多选择背包问题无法在多项式时间内找到最优解, 且由于其强约束限制条件, 在求解过程中易陷入局部最优的问题, 提出一种改进的量子粒子群优化算法对该问题进行求解. 首先, 在量子粒子移动过程中, 通过判断其与下次迭代个体的位置关系确定其位置信息的可用性, 通过该信息充分保留粒子位置的多样性; 其次, 提出一种新的位置扰动方法, 避免种群陷入局部最优. 最后, 将该算法在标准数据集上进行测试, 对算法的收敛速度和运行时间进行分析, 测试结果表明, 该算法在求解准确性上得到明显提升.

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