CAJ | 학술논문

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