多重二次背包问题的量子进化求解算法  

A Quantum Evolutionary Algorithm for Quadratic Multiple Knapsack Problem

作　　者：钱洁[1,2] 王保华[2] 郑建国[1] 陈宇峰[2] 周奎[2] 

机构地区：[1]湖北汽车工业学院汽车动力传动与电子控制湖北省重点实验室,湖北十堰442002 [2]东华大学智能系统研究中心,上海200051

出　　处：《计算机学报》2015年第8期1518-1529,共12页Chinese Journal of Computers

基　　金：国家自然科学基金(70971020;51175155);湖北省自然科学基金(2013CFA054);湖北省教育厅项目(D20131804)资助~~

摘　　要：多重二次背包问题是二次背包与多重背包两种NP(Non-Deterministic Polynomial,非确定多项式)难问题融合后的一种新问题,由于其决策变量间具有高耦合性,已有的启发式算法求解效率和精度不够理想.针对这一问题提出一种量子进化求解算法,这种算法的量子观测操作能将部分约束处理与观测一步完成,解码效率高且不易陷入局部极值.算法中的量子更新采用自适应调节整体更新方式,相比传统查表方式更简洁和高效.算法还设计了一种局部和全局修补算子以保证解的可行性.另外,设计的交换算子能增强算法在约束边界的搜索性能.标准算例测试实验的结果表明文中提出的求解算法比传统算法的精度和效率更高.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.

关 键 词：多重二次背包问题 量子进化计算 约束优化 组合优化 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]