改进二进制布谷鸟搜索算法求解多维背包问题

来源：计算机应用杂志2015年第1期北京时间：

作者：张晶, 吴虎胜

单位：1. 西安建筑科技大学 管理学院, 西安710055;2. 武警工程大学 装备工程学院, 西安710086

摘要：针对多约束组合优化问题——多维背包问题(MKP),提出了一种改进二进制布谷鸟搜索(MBCS)算法.首先,采用经典的二进制代码变换公式构建了二进制布谷鸟搜索(BCS)算法.其次,引入病毒生物进化机制和病毒感染操作,一方面赋予布谷鸟鸟巢位置自变异机制增加种群多样性;一方面将布谷鸟鸟巢位置所组成的主群体的纵向全局搜索和病毒群体的横向局部搜索进行动态结合,进一步提高了算法的收敛速度,降低了陷入局部极值的概率.再次,针对MKP特点设计了不可行解的混合修复策略.最后将MBCS算法同量子遗传算法(QGA)、二进制粒子群优化(BPSO)算法、BCS算法就来源于ELIB数据库和OR_LIB数据库的15个算例进行了仿真对比.实验结果表明,所提算法计算误差均小于1%,标准差小于170,相比这3种算法具有相对更好的寻优精度和求解稳定性,是一种求解多维背包等NP难问题有效的算法.

关键词：进化计算,二进制布谷鸟搜索算法,病毒机制,多维背包问题,组合优化

基金资助：陕西省重点学科专项(E08001,E08003,E08005);陕西省教育厅科研计划项目(2013JK0185);陕西省高校重点研究基地建设专项(DA08046);西安建筑科技大学人才科技基金资助项目(RC1324).