变异蝙蝠算法求解折扣{0-1}背包问题

doi:10.11772/j.issn.1001-9081.2017.05.1292

计算机应用 ›› 2017, Vol. 37 ›› Issue (5): 1292-1299.DOI: 10.11772/j.issn.1001-9081.2017.05.1292

变异蝙蝠算法求解折扣{0-1}背包问题

吴聪聪, 贺毅朝, 陈嶷瑛, 刘雪静, 才秀凤

河北地质大学信息工程学院, 石家庄 050031

收稿日期:2016-10-24 修回日期:2016-12-08 出版日期:2017-05-10 发布日期:2017-05-16
通讯作者: 吴聪聪
作者简介:吴聪聪(1975-),女,河北唐山人,讲师,硕士,主要研究方向:智能计算、信息检索、机器学习;贺毅朝(1969-),男,河北晋州人,教授,CCF高级会员,主要研究方向:进化算法理论与应用、算法设计与分析、计算复杂性理论与群测试理论;陈嶷瑛(1971-),女,湖南宁远人,教授,博士,主要研究方向:机器学习、地理信息系统;刘雪静(1980-),女,河北定州人,讲师,硕士,主要研究方向:智能计算、机器学习;才秀凤(1979-),女,河北丰润人,讲师,硕士,主要研究方向:智能计算、机器学习。
基金资助:
河北省高等学校科学研究计划项目（ZD2016005）；河北省自然科学基金资助项目（F2016403055）。

Mutated bat algorithm for solving discounted {0-1} knapsack problem

WU Congcong, HE Yichao, CHEN Yiying, LIU Xuejing, CAI Xiufeng

College of Information Engineering, Hebei GEO University, Shijiazhuang Hebei 050031, China

Received:2016-10-24 Revised:2016-12-08 Online:2017-05-10 Published:2017-05-16
Supported by:
This work is partially supported by Scientific Research Project Program of Colleges and Universities in Hebei Province (ZD2016005), the Natural Science Foundation of Hebei Province (F2016403055).

摘要/Abstract

摘要： 针对确定性算法难于求解规模大、数据范围广的折扣{0-1}背包问题（D{0-1}KP），提出了基于蝙蝠算法的快速求解D{0-1}KP的变异蝙蝠算法（MDBBA）。首先，利用双重编码解决D{0-1}KP的编码问题；其次，将贪心修复与优化算法（GROA）应用于蝙蝠个体适应度计算中，使算法快速得到有效解；然后，选择使用差分演化（DE）的变异策略提高算法的全局寻优能力；最后，蝙蝠个体按一定概率进行Lévy飞行，增强算法探索能力和跳出局部极值的能力。对四类大规模实例的仿真计算表明：MDBBA非常适于求解大规模的D{0-1}KP，比第一遗传算法（FirEGA）和双重编码蝙蝠算法（DBBA）求得的最优值和平均值都更优，MDBBA收敛速度明显快于DBBA。

关键词: 折扣{0-1}背包问题, 蝙蝠算法, 差分演化, Lé, vy飞行, 贪心策略, 非正常编码

Abstract: Since the deterministic algorithms are difficult to solve the Discounted {0-1} Knapsack Problem (D{0-1}KP) with large-scale and wide data range, a Mutated Double codes Binary Bat Algorithm (MDBBA) was proposed. Firstly, the coding problem of D{0-1} KP was solved by double coding. Secondly, the Greedy Repair and Optimization Algorithm (GROA) was applied to the individual fitness calculation of bats, and the algorithm was quickly and effectively solved. Then, the mutation strategy in Differential Evolution (DE) was selected to improve the global optimization ability. Finally, Lévy flight was carried out by the bat individual according to certain probability to enhance the ability of the algorithm to explore and jump out of local extrema. Simulation was tested on four large-scale instances. The result shows that MDBBA is very suitable for solving large-scale D {0-1} KP, which has better optimal value and mean value than FirEGA (First Genetic Algorithm) algorithm and Double Binary Bat Algorithm (DBBA), and MDBBA converges significantly faster than DBBA.

Key words: Discounted {0-1} Knapsack Problem (D{0-1}KP), Bat Algorithm (BA), differential evolution, Lévy flight, greedy strategy, non-normal coding

中图分类号:

TP18

吴聪聪, 贺毅朝, 陈嶷瑛, 刘雪静, 才秀凤. 变异蝙蝠算法求解折扣{0-1}背包问题[J]. 计算机应用, 2017, 37(5): 1292-1299.

WU Congcong, HE Yichao, CHEN Yiying, LIU Xuejing, CAI Xiufeng. Mutated bat algorithm for solving discounted {0-1} knapsack problem[J]. Journal of Computer Applications, 2017, 37(5): 1292-1299.

参考文献

[1] GULDAN B. Heuristic and exact algorithms for discounted knapsack problems[D]. Nuremberg:University of Erlangen-Nuremberg, 2007.
[2] RONG A, FIGUEIRA J R, KLAMROTH K. Dynamic programming based algorithms for the discounted {0-1} knapsack problem[J]. Applied Mathematics and Computation, 2012, 218(12):6921-6933.
[3] 贺毅朝, 王熙照,李文斌, 等. 基于遗传算法求解折扣{0-1}背包问题的研究[J].计算机学报,2016,39(12):2614-2630.(HE Y C,WANG X Z, LI W B, et al. Research on genetic algorithms for the discounted {0-1} knapsack problem[J]. Chinese Journal of Computers, 2016,39(12):2614-2630.)
[4] HE Y, WANG X, HE Y,et al. Exact and approximate algorithms for discounted {0-1} knapsack problem[J]. Information Sciences, 2016, 369(10):634-647.
[5] YANG X. A new metaheuristic bat-inspired algorithm[C]//NICSO 2010:Nature Inspired Cooperative Strategies for Optimization. Berlin:Springer, 2010, 284:65-74.
[6] 吴聪聪,贺毅朝,陈嶷瑛,等. 求解0-1背包问题的二进制蝙蝠算法[J].计算机工程与应用, 2015, 51(19):71-74.(WU C C,HE Y C,CHEN Y Y, et al. Binary bat algorithm for solving 0-1 knapsack problem[J]. Computer Engineering and Applications, 2015,51(19):71-74.)
[7] 贺兴时,丁文静,杨新社.基于模拟退火高斯扰动的蝙蝠优化算法[J],计算机应用研究,2013, 31(2):392-397.(HE X S,DING W J,YANG X S. Bat algorithm based on simulated annealing and Gaussian perturbations[J].Application Research of Computers, 2013, 31(2):392-397.)
[8] 谢健,周永权,陈欢.一种基于Lévy飞行轨迹的蝙蝠算法[J].模拟识别与人工智能,2013,26(9):829-837.(XIE J, ZHOU Y Q, CHEN H. A bat algorithm based on Lévy flights trajectory[J]. Pattern Recognition and Artificial Intelligence, 2013,26(9):829-837.)
[9] 刘长平,叶春明.具有混沌搜索策略的蝙蝠优化算法及性能仿真[J].系统仿真学报,2013,25(6):1183-1188.(LIU C P, YE C M. Bat algorithm with chaotic search strategy and analysis of its property[J]. Journal of System Simulation,2013,25(6):1183-1188.)
[10] YANG X. Bat algorithm for multiobjective optimization[J]. International Journal of Bio-Inspired Computation, 2011, 3(5):267-274.
[11] YANG X, GANDOMI A H. Bat algorithm:a novel approach for global engineering optimization[J].Engineering Computations,2012, 29(5):464-483.
[12] LEMMA T A, BIN M H F. Use of fuzzy systems and bat algorithm for energy modeling in a gas turbine generator[C]//Proceedings of the 2011 IEEE Colloquium on Humanities, Science and Engineering. Piscataway, NJ:IEEE, 2011:305-310.
[13] 盛晓华,叶春明.基于蝙蝠算法的PFSP调度干扰管理研究[J]. 计算机工程与应用, 2014,50(8):241-246. (SHENG X H, YE C M. Research of bat algorithm for disruption management on PFSP scheduling[J]. Computer Engineering and Applications, 2014,50(8):241-246.)
[14] MISHRA S, SHAW K, MISHRA D. A new meta-heuristic bat inspired classification approach for microarray data[J]. Procedia Technology, 2012, 4(1):802-806.
[15] KHAN K, SAHAI A. A comparison of BA,GA,PSO,BP and LM for training feed forward neural networks in e-learning context[J].International Journal of Intelligent Systems and Applications,2012,4(7):23-29.
[16] KHAN K,NIKOV A,SAHAI A. A fuzzy bat clustering method forergonomic screening of office workplaces[C]//Proceedings of the 3rd International Conference on Software, Services and Semantic Technologies. Berlin:Springer, 2011:59-66.
[17] 贺毅朝,王彦祺,刘建芹.一种适于求解离散问题的二进制粒子群优化算法[J].计算机应用与软件, 2007,24(1):157-159.(HE Y C, WANG Y Q,LIU J Q. A new binary particle swarm optimization for solving discrete problems[J]. Computer Applications and Software, 2007,24(1):157-159.)
[18] NOMAN N, IBA H. Enhancing differential evolution performance with local search for high dimensional function optimization[C]//Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation. New York:ACM, 2005:967-974.
[19] 贺毅朝,王熙照, 刘坤起,等.差分演化的收敛性分析与算法改进[J]. 软件学报,2010,21(5):875-885.(HE Y C,WANG X Z,LIU K Q, et al.Convergent analysis and algorithmic improvement of differential evolution[J].Journal of Software, 2010, 21(5):875-885.)
[20] YANG X, DEB S. Cuckoo search via Lévy flights[C]//Proceedings of World Congress on Nature & Biologically Inspired Computing. Piscataway, NJ:IEEE, 2009:210-214.
[21] 刘长平,叶春明.具有Lévy飞行特征的蝙蝠算法[J].智能系统学报,2013,8(3):240-246.(LIU C P,YE C M. Bat algorithm with the characteristics of Lévy flights[J]. CAAI Transactions on Intelligent Systems,2013,8(3):240-246.)
[22] CORMEN T H, LEISERSON C E, RIVEST R L, et al. Introduction to Algorithms[M]. 3rd ed. Cambridge:MIT Press, 2001:1117-1119.
[23] ALSUWAIYEL M H. Algorithms Design Techniques and Analysis[M]. Singapore:World Scientific Publishing Company, 1999:410-418.

变异蝙蝠算法求解折扣{0-1}背包问题

Mutated bat algorithm for solving discounted {0-1} knapsack problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	曾明华, 全轲. 双层规划的改进混合布谷鸟搜索量子行为粒子群优化算法[J]. 计算机应用, 2020, 40(7): 1908-1912.
[2]	韩雨涝, 房鼎益. 联合无线充电与数据收集的移动充电装置多目标路径规划算法[J]. 计算机应用, 2020, 40(6): 1745-1750.
[3]	徐小平, 徐丽, 王峰, 刘龙. 基于Lagrange插值的学习猴群算法求解折扣｛0-1｝背包问题[J]. 计算机应用, 2020, 40(11): 3113-3118.
[4]	史文旭, 杨洋, 鲍胜利. 贪心核加速动态规划算法求解折扣{0-1}背包问题[J]. 计算机应用, 2019, 39(7): 1912-1917.
[5]	杨洋, 潘大志, 刘益, 谭代伦. 折扣{0-1}背包问题的简化新模型及遗传算法求解[J]. 计算机应用, 2019, 39(3): 656-662.
[6]	蔺凯青, 李志华, 郭曙杰, 李双俐. 云环境中多目标优化的虚拟机放置算法[J]. 计算机应用, 2019, 39(12): 3597-3603.
[7]	刘晓明, 沈明玉, 侯整风. 基于Levy飞行的萤火虫模糊聚类算法[J]. 计算机应用, 2019, 39(11): 3257-3262.
[8]	刘雪静, 贺毅朝, 路凤佳, 吴聪聪, 才秀凤. 基于Lévy飞行的差分乌鸦算法求解折扣{0-1}背包问题[J]. 计算机应用, 2018, 38(2): 433-442.
[9]	董柏宏, 邓健, 张定杰, 吴维刚. 软件定义车联网的数据转发策略和路由选择技术[J]. 计算机应用, 2018, 38(1): 26-30.
[10]	刘雪静, 贺毅朝, 路凤佳, 吴聪聪, 才秀凤. 基于差分演化策略的混沌乌鸦算法求解折扣{0-1}背包问题[J]. 计算机应用, 2018, 38(1): 137-145.
[11]	王则林, 郝水侠. 运用差分演化算法实现包匹配多层核心基的提取[J]. 计算机应用, 2017, 37(3): 777-781.
[12]	殷亚, 张惠珍. 易腐生鲜货品车辆路径问题的改进混合蝙蝠算法[J]. 计算机应用, 2017, 37(12): 3602-3607.
[13]	付强, 葛洪伟, 苏树智. 引入萤火虫行为和Levy飞行的粒子群优化算法[J]. 计算机应用, 2016, 36(12): 3298-3302.
[14]	李康顺, 左磊, 李伟. 基于单形正交实验设计的差分演化算法[J]. 计算机应用, 2016, 36(1): 143-149.
[15]	张前图, 房立清, 赵玉龙. 具有Levy飞行特征的双子群果蝇优化算法[J]. 计算机应用, 2015, 35(5): 1348-1352.