基于差分演化策略的混沌乌鸦算法求解折扣{0-1}背包问题

doi:10.11772/j.issn.1001-9081.2017061445

计算机应用 ›› 2018, Vol. 38 ›› Issue (1): 137-145.DOI: 10.11772/j.issn.1001-9081.2017061445

基于差分演化策略的混沌乌鸦算法求解折扣{0-1}背包问题

刘雪静, 贺毅朝, 路凤佳, 吴聪聪, 才秀凤

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

收稿日期:2017-06-13 修回日期:2017-08-31 出版日期:2018-01-10 发布日期:2018-01-22
通讯作者: 刘雪静
作者简介:刘雪静(1980-),女,河北定州人,讲师,硕士,CCF会员,主要研究方向:演化计算、机器学习;贺毅朝(1969-),男,河北晋州人,教授,硕士,CCF高级会员,主要研究方向:智能计算、计算复杂性理论;路凤佳(1980-),女,河北沧州人,讲师,硕士,主要研究方向:大数据、机器学习;吴聪聪(1975-),女,河北唐山人,讲师,硕士,主要研究方向:智能计算、信息检索、机器学习;才秀凤(1978-),女,河北丰润人,讲师,硕士,主要研究方向:智能计算、机器学习。
基金资助:
河北省高等学校科学研究计划项目（ZD2016005）；河北省自然科学基金资助项目（F2016403055）。

Chaotic crow search algorithm based on differential evolution strategy for solving discount {0-1} knapsack problem

LIU Xuejing, HE Yichao, LU Fengjia, WU Congcong, CAI Xiufeng

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

Received:2017-06-13 Revised:2017-08-31 Online:2018-01-10 Published:2018-01-22
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），提出了基于差分演化策略的混沌乌鸦算法（DECCSA）。首先，采用混沌映射生成初始乌鸦种群；然后，采用混合编码方式和贪心修复与优化策略（GROS）解决了D{0-1}KP的编码问题；最后，引入差分演化策略提高算法的收敛速度。对4类大规模D{0-1}KP实例的计算结果表明：DECCSA比遗传算法、细菌觅食算法和变异蝙蝠算法求得的最好值和平均值更优，能得到最优解或更好的近似解，非常适于求解D{0-1}KP。

关键词: 乌鸦算法, 折扣{0-1}背包问题, 混沌, 贪心修复与优化策略, 差分演化策略

Abstract: In Discount {0-1} Knapsack Problem (D{0-1}KP), the weight coefficients and the value coefficients in a large range, are difficult to solve by deterministic algorithms. To solve this problem, a Chaotic Crow Search Algorithm based on Differential Evolution strategy (DECCSA) was proposed. Firstly, the initial crow population was generated by chaotic mapping. Secondly, mixed coding and Greedy Repair and Optimization Strategy (GROS) were used to solve the coding problem of D{0-1}KP. Finally, Difference Evolution (DE) strategy was introduced to improve the convergence rate of the algorithm. The experimental results on four large-scale D{0-1}KP instances show that DECCSA is better than Genetic Algorithm (GA), bacterial foraging optimization algorithm, and mutated bat algorithm, and it can get the optimal solution or approximate optimal solution. It's very suitable for solving D{0-1}KP.

Key words: crow search algorithm, Discount {0-1} Knapsack Problem (D{0-1}KP), chaotic, Greedy Repair and Optimization Strategy (GROS), Difference Evolution (DE) strategy

中图分类号:

TP301.6
TP18

刘雪静, 贺毅朝, 路凤佳, 吴聪聪, 才秀凤. 基于差分演化策略的混沌乌鸦算法求解折扣{0-1}背包问题[J]. 计算机应用, 2018, 38(1): 137-145.

LIU Xuejing, HE Yichao, LU Fengjia, WU Congcong, CAI Xiufeng. Chaotic crow search algorithm based on differential evolution strategy for solving discount {0-1} knapsack problem[J]. Journal of Computer Applications, 2018, 38(1): 137-145.

参考文献

[1] KELLERER H, PFERSCHY U, PISINGER D. Knapsack Problems[M]. Berlin:Springer, 2004:55-75.
[2] WILBAUT C, SALHI S, HANAFI S. An iterative variable-based fixation heuristic for the 0-1 multidimensional knapsack problem[J]. European Journal of Operational Research, 2009, 199(2):339-348.
[3] CHU P C, BEASLEY J E. A genetic algorithm for the multidimensional knapsack problem[J]. Journal of Heuristics, 1998, 4(1):63-86.
[4] DJANNATY F, DOOSTDAR S. A hybrid genetic algorithm for the multidimensional knapsack problem[J]. International Journal of Contemporary Mathematical Sciences, 2008, 3(9/10/11/12):443-456.
[5] SBIHI A. A best first search exact algorithm for the multiple-choice multidimensional knapsack problem[J]. Journal of Combinatorial Optimization, 2006, 13(4):337-351.
[6] FURINI F, LORI M, MARTELLO S, et al. Heuristic and exact algorithms for the interval min-max regret knapsack problem[J]. INFORMS Journal on Computing, 2015, 27(2):392-405.
[7] GULDAN B. Heuristic and exact algorithms for discounted knapsack problems[D]. Erlangen:University of Erlangen-Nürnberg, 2007:1-78.
[8] RONG A Y, 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.
[9] 贺毅朝,王熙照,李文斌,等.基于遗传算法求解折扣{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.)
[10] 刘雪静,贺毅朝,吴聪聪,等.基于细菌觅食算法求解折扣{0-1}背包问题的研究[J/OL].计算机工程与应用,2017:1-11. (2017-02-16)[2017-08-18]. http://kns.cnki.net/kcms/detail/11.2127.TP.20170216.1044.038.html.(LIU X J, HE Y C, WU C C, et al. Research on bacterial foraging optimization algorithm for the Discounted {0-1} knapsack problem[J/OL]. Computer Engineering and Applications, 2017:1-11. (2017-02-16)[2017-08-18]. http://kns.cnki.net/kcms/detail/11.2127.TP.20170216.1044.038.html.)
[11] 吴聪聪,贺毅朝,陈嶷瑛,等.变异蝙蝠算法求解折扣{0-1}背包问题[J].计算机应用,2017,37(5):1292-1299.(WU C C, HE Y C, CHEN Y Y, et al. Mutated bat algorithm for solving the discounted{0-1}KP[J]. Journal of Computer Applications, 2017, 37(5):1292-1299.)
[12] ASKARZADEH A. A novel metaheuristic method for solving constrained engineering optimization problems:crow search algorithm[J]. Computers & Structures, 2016, 169:1-12.
[13] ABDELAZIZ A Y, FATHY A. A novel approach based on crow search algorithm for optimal selection of conductor size in radial distribution networks[J]. Engineering Science & Technology:An International Journal, 2017, 20(2):391-402.
[14] SHEN L, XU L, WEI R, et al. Multi-swarm optimization with chaotic mapping for dynamic optimization problems[C]//Proceedings of the 2016 International Symposium on Computational Intelligence and Design. Piscataway, NJ:IEEE, 2016:132-137.
[15] 贺毅朝,王熙照,寇应展.一种具有混合编码的二进制差分演化算法[J].计算机研究与发展,2007,44(9):1476-1484.(HE Y C, WANG X Z, KOU Y Z. A binary differential evolution algorithm with hybrid encoding[J]. Journal of Computer Research and Development, 2007, 44(9):1467-1484.)
[16] NOMAN N, IBA H. Enhancing differential evolution performance with local search for high dimensional function optimization[C]//GECCO 2005:Proceedings of the 2005 Conference on Genetic and Evolutionary Computation. New York:ACM, 2005:967-974.
[17] MICHALEWICZ Z, JANIKOW C Z, KRAWCZYK J B. A modified genetic algorithm for optimal control problems[J]. Computers & Mathematics with Applications, 1992, 23(12):83-94.

基于差分演化策略的混沌乌鸦算法求解折扣{0-1}背包问题

Chaotic crow search algorithm based on differential evolution strategy for solving discount {0-1} knapsack problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	徐丽云, 闫涛, 钱宇华. 基于级联混沌系统的分数域语音加密算法[J]. 计算机应用, 2021, 41(9): 2623-2630.
[2]	汤安迪, 韩统, 徐登武, 谢磊. 混沌精英哈里斯鹰优化算法[J]. 计算机应用, 2021, 41(8): 2265-2272.
[3]	汤安迪, 韩统, 徐登武, 谢磊. 基于混沌麻雀搜索算法的无人机航迹规划方法[J]. 计算机应用, 2021, 41(7): 2128-2136.
[4]	贾鹤鸣, 姜子超, 李瑶, 孙康健. 基于改进斑点鬣狗优化算法的同步优化特征选择[J]. 计算机应用, 2021, 41(5): 1290-1298.
[5]	李珊珊, 赵莉, 张红丽. 基于猫映射的图像灰度值加密[J]. 计算机应用, 2021, 41(4): 1148-1152.
[6]	沈子懿, 王卫亚, 蒋东华, 荣宪伟. 基于Hopfield混沌神经网络和压缩感知的可视化图像加密算法[J]. 计算机应用, 2021, 41(10): 2893-2899.
[7]	许秋艳, 马良, 刘勇. 基于混沌搜索和错卦变换的阴阳平衡优化算法[J]. 计算机应用, 2020, 40(8): 2305-2312.
[8]	段宇君, 王耀力, 常青, 刘鑫. 改进型蚁群算法融合混沌优化的pSPIEL算法的无线传感器布局优化[J]. 计算机应用, 2020, 40(3): 793-798.
[9]	徐小平, 徐丽, 王峰, 刘龙. 基于Lagrange插值的学习猴群算法求解折扣｛0-1｝背包问题[J]. 计算机应用, 2020, 40(11): 3113-3118.
[10]	史文旭, 杨洋, 鲍胜利. 贪心核加速动态规划算法求解折扣{0-1}背包问题[J]. 计算机应用, 2019, 39(7): 1912-1917.
[11]	贺利芳, 陈俊, 张天骐. 无信号间干扰的相关延迟差分混沌移位键控混沌通信方案[J]. 计算机应用, 2019, 39(7): 2014-2018.
[12]	徐光宪, 王栋. 基于混沌加密对抗窃听的安全网络编码方案[J]. 计算机应用, 2019, 39(5): 1374-1377.
[13]	张刚, 黄南飞, 张天骐. 多用户正交相关延迟键控方案性能分析[J]. 计算机应用, 2019, 39(5): 1425-1428.
[14]	杨洋, 潘大志, 刘益, 谭代伦. 折扣{0-1}背包问题的简化新模型及遗传算法求解[J]. 计算机应用, 2019, 39(3): 656-662.
[15]	黄滨, 保利勇, 丁洪伟. 基于均匀化分布的Chebyshev映射系统构建及特性分析[J]. 计算机应用, 2019, 39(10): 2997-3001.