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

作     者：钱洁 王保华 郑建国 陈宇峰 周奎 QIAN Jie;WANG Bao-Hua;ZHENG Jian-Guo;CHEN Yu-Feng;ZHOU Kui

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

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

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：2015年第38卷第8期

页      码：1518-1529页

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

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

学科分类：0810[工学-土木类] 0808[工学-自动化类] 0839[0839] 08[工学] 0835[0835] 0811[工学-水利类] 0812[工学-测绘类] 081202[081202] 

核心收录：

D　O　I：10.11897/SP.J.1016.2015.01518

馆 藏 号：203725779...