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

doi:10.11772/j.issn.1001-9081.2015.01.0183

计算机应用 ›› 2015, Vol. 35 ›› Issue (1): 183-188.DOI: 10.11772/j.issn.1001-9081.2015.01.0183

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

张晶¹, 吴虎胜²

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

收稿日期:2014-08-14 修回日期:2014-09-22 出版日期:2015-01-01 发布日期:2015-01-26
通讯作者: 张晶
作者简介:张晶(1981-),女,陕西西安人,博士,主要研究方向:投资决策、资产管理、运筹学、智能计算;吴虎胜(1986-),男,湖北荆门人,博士研究生,主要研究方向:信息系统工程、智能决策、智能计算、军事装备学.
基金资助:
陕西省重点学科专项(E08001,E08003,E08005);陕西省教育厅科研计划项目(2013JK0185);陕西省高校重点研究基地建设专项(DA08046);西安建筑科技大学人才科技基金资助项目(RC1324).

Modified binary cuckoo search algorithm for multidimensional knapsack problem

ZHANG Jing¹, WU Husheng²

1. School of Management, Xi'an University of Architecture and Technology, Xi'an Shaanxi 710055, China;
2. Materiel Engineering Institute, Engineering University of Armed Police Force, Xi'an Shaanxi 710086, China

Received:2014-08-14 Revised:2014-09-22 Online:2015-01-01 Published:2015-01-26

摘要/Abstract

摘要：

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

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

Abstract:

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.

Key words: evolutionary computation, Binary Cuckoo Search (BCS) algorithm, virus mechanism, Multidimensional Knapsack Problem (MKP), combinatorial optimization

中图分类号:

TP301.6
TP18

张晶, 吴虎胜. 改进二进制布谷鸟搜索算法求解多维背包问题[J]. 计算机应用, 2015, 35(1): 183-188.

ZHANG Jing, WU Husheng. Modified binary cuckoo search algorithm for multidimensional knapsack problem[J]. Journal of Computer Applications, 2015, 35(1): 183-188.

参考文献

[1] DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem [J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66.
[2] KARABOGA D, BASTURK B. A powerful and efficient algorithm for numerical function optimization: Artificial Bee Colony (ABC) algorithm [J]. Journal of Global Optimization, 2007, 39(3): 459-471.
[3] YANG X, DEB S. Cuckoo search via Lévy flights [C]// Proceedings of the 2009 World Congress on Nature & Biologically Inspired Computing. Piscataway: IEEE, 2009: 210-214.
[4] WU H, ZHANG F, WU L. New swarm intelligence algorithm—wolf pack algorithm [J]. Systems Engineering and Electronics, 2013, 35(11): 3430-3438.(吴虎胜,张凤鸣,吴庐山.一种新的群体智能算法——狼群算法[J].系统工程与电子技术,2013,35(11):3430-3438.)
[5] LI Z, ZHANG X, ZHANG Z, et al. Monkey-king genetic algorithm hybridized with immune evolutionary [J]. Journal of Computer Applications, 2014, 34(6): 1641-1644.(李祚泳,张小丽,张正健,等.免疫进化混合猴王遗传算法[J].计算机应用,2014,34(6): 1641-1644.)
[6] XIAO H, DUAN Y. Cuckoo search algorithm based on differential evolution [J]. Journal of Computer Applications, 2014, 34(6): 1631-1635.(肖辉辉,段艳明.基于差分进化的布谷鸟搜索算法 [J].计算机应用,2014,34(6):1631-1635.)
[7] VALIAN E, MOHANNA S, TAVAKOLI S. Improved cuckoo search algorithm for global optimization [J]. International Journal of Communications and Information Technology, 2011, 1(1): 31-44.
[8] HU S, XU X, LI X. A virus coevolution genetic algorithm for project optimization scheduling [J]. Journal of Software, 2004, 15(1): 49-57.(胡仕成,徐晓飞,李向阳.项目优化调度的病毒协同进化遗传算法[J].软件学报,2004,15(1):49-57.)
[9] GU F, CHEN H, LU B. Virus genetic algorithm for flexible job shop scheduling [J]. Systems Engineering and Electronics, 2005, 27(11): 1953-1956.(谷峰,陈华平,卢冰原.病毒遗传算法在柔性工作车间调度中的应用[J].系统工程与电子技术,2005, 27(11): 1953-1956.)
[10] TUO S. A harmony search algorithm for resolving multi-dimensional knapsack problems [J]. Microelectronics & Computer, 2012, 29(6): 76-80.(拓守恒.一种求解多维背包问题的和声优化搜索算法[J].微电子学与计算机,2012, 29(6):76-80.)
[11] DEANE J, AGARWAL A. Neural, genetic, and neurogenetic approaches for solving the 0-1 multidimensional knapsack problem [J]. International Journal of Management & Information Systems, 2013, 17(1): 43-54.
[12] PAVLYUKEVICH I. Lévy flights, non-local search and simulated annealing [J]. Journal of Computational Physics, 2007, 226(2): 1830-1844.
[13] YANG X, DEB S. Engineering optimization by cuckoo search [J]. International Journal of Mathematical Modeling and Numerical Optimization, 2010, 1(4): 330-343.
[14] VALIAN E, MOHANNA S, TAVAKOLI S. Improved cuckoo search algorithm for global optimization [J]. International Journal of Communications and Information Technology, 2011, 1(1): 31-44.
[15] GHERBOUDJ A, LAYEB A, CHIKHI S. Solving 0-1 knapsack problems by a discrete binary version of cuckoo search algorithm [J]. International Journal of Bio-Inspired Computation, 2012, 4(4): 229-236.
[16] HAN K-H, KIM J-H. Quantum genetic algorithm and its application to combinatorial optimization problem [C]// Proceedings of the 2000 Congress on Evolutionary Computation. Piscataway: IEEE, 2000: 1354-1360.

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

Modified binary cuckoo search algorithm for multidimensional knapsack problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	赵秋云, 魏乐, 舒红平. 面向制造任务的云制造虚拟车间构造方法[J]. 计算机应用, 2021, 41(7): 2003-2011.
[2]	王宇, 刘燕丽, 陈劭武. 基于顶点冲突学习的最大公共子图算法[J]. 计算机应用, 2021, 41(6): 1756-1760.
[3]	王泽昆, 贺毅朝, 李焕哲, 张发展. 基于新颖S型转换函数的二进制粒子群优化算法求解具有单连续变量的背包问题[J]. 计算机应用, 2021, 41(2): 461-469.
[4]	李章洪, 梁晓磊, 田梦丹, 周文峰. 求解排列组合问题的解空间动态缩减策略[J]. 计算机应用, 2020, 40(7): 2016-2020.
[5]	杨云亭, 王鹏. 求解旅行商问题的多尺度量子自由粒子优化算法[J]. 计算机应用, 2020, 40(5): 1278-1283.
[6]	杨艳, 刘生建, 周永权. 贪心二进制狮群优化算法求解多维背包问题[J]. 计算机应用, 2020, 40(5): 1291-1294.
[7]	郭羽含, 张美琪, 周楠. 基于偏好矩阵遗传算法求解长期车辆合乘问题[J]. 计算机应用, 2017, 37(2): 602-607.
[8]	黄虹玮, 葛笑天, 陈烜松. 基于复杂学习分类系统的密度聚类方法[J]. 计算机应用, 2017, 37(11): 3207-3211.
[9]	盛小东, 李强, 刘昭昭. 云环境下基于模板遗传算法的任务调度方法[J]. 计算机应用, 2016, 36(3): 633-636.
[10]	孙家泽, 耿国华. 基于群体智能的三维碎片全局最优匹配方法[J]. 计算机应用, 2016, 36(1): 266-270.
[11]	刘晓红, 曲志坚, 曹雁锋, 张先伟, 冯刚. 基于自适应机制的多宇宙并行量子衍生进化算法[J]. 计算机应用, 2015, 35(2): 369-373.
[12]	张炎亮陈鑫李亚东. 小波神经网络模型的改进方法[J]. 计算机应用, 2013, 33(11): 3107-3110.
[13]	张敬敏李霞. 求解作业车间调度问题的差分和声搜索算法[J]. 计算机应用, 2013, 33(02): 329-356.
[14]	王超董兴业. 求解护士排班问题的变邻域搜索算法[J]. 计算机应用, 2013, 33(02): 338-352.
[15]	王念桥姚四改. 基于改进粒子群优化算法的排课问题[J]. 计算机应用, 2013, 33(01): 207-210.