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

Modified binary cuckoo search algorithm for multidimensional knapsack problem

作　　者：张晶[1] 吴虎胜 

机构地区：[1]西安建筑科技大学管理学院,西安710055 [2]武警工程大学装备工程学院,西安710086

出　　处：《计算机应用》2015年第1期183-188,共6页journal of Computer Applications

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

摘　　要：针对多约束组合优化问题——多维背包问题(MKP),提出了一种改进二进制布谷鸟搜索(MBCS)算法。首先,采用经典的二进制代码变换公式构建了二进制布谷鸟搜索(BCS)算法。其次,引入病毒生物进化机制和病毒感染操作,一方面赋予布谷鸟鸟巢位置自变异机制增加种群多样性;一方面将布谷鸟鸟巢位置所组成的主群体的纵向全局搜索和病毒群体的横向局部搜索进行动态结合,进一步提高了算法的收敛速度,降低了陷入局部极值的概率。再次,针对MKP特点设计了不可行解的混合修复策略。最后将MBCS算法同量子遗传算法(QGA)、二进制粒子群优化(BPSO)算法、BCS算法就来源于ELIB数据库和OR_LIB数据库的15个算例进行了仿真对比。实验结果表明,所提算法计算误差均小于1%,标准差小于170,相比这3种算法具有相对更好的寻优精度和求解稳定性,是一种求解多维背包等NP难问题有效的算法。The Multidimensional Knapsack Problem（ MKP） is a typical multi-constraint combinatorial problem. In order to solve this problem, a Modified Binary Cuckoo Search（ MBCS） algorithm was proposed. Firstly, with the help of classical binary code transformer, the Binary Cuckoo Search（ BCS） algorithm was built; Secondly, the virus evolution mechanism and virus infection operation were introduced into the BCS. Specifically, on one hand, it made the position of bird＇s nest have mutation mechanism, which could improve the diversity of the population; on another hand, the main groups that consisted of nest position transmitted information cross the vertical generations and guided the global search, while the virus groups transfered evolutionary information cross the same generation through virus infection and guided the local search. These improved the convergence speed and decreased the probability of falling into the local optimum. Thirdly, the hybrid repair strategy for infeasible solutions was designed according to the characteristics of the MKP. At last, comparison experiments among the MBCS algorithm, Quantum Genetic Algorithm（ QGA）, Binary Particle Swarm Optimization（ BPSO） algorithm and BCS algorithm were given on 15 different problems from ELIB and OR_LIB database. The experimental results show that the computational error and standard deviation of MBCS are less than 1% and 170, respectively, which shows the MBCS algorithm can achieve better solutions with good accuracy and robustness than QGA, BPSO and BCS algorithm. It is an effective algorithm in solving NP-hard problems such as the MKP.

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

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