基于Lévy飞行的差分乌鸦算法求解折扣{0-1}背包问题

doi:10.11772/j.issn.1001-9081.2017071852

计算机应用 ›› 2018, Vol. 38 ›› Issue (2): 433-442.DOI: 10.11772/j.issn.1001-9081.2017071852

基于Lévy飞行的差分乌鸦算法求解折扣{0-1}背包问题

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

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

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

Differential crow search algorithm based on Lévy flight for solving discount {0-1} knapsack problem

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

School of Information Technology, Hebei GEO University, Shijiazhuang Hebei 050031, China

Received:2017-07-27 Revised:2017-09-08 Online:2018-02-10 Published:2018-02-10
Supported by:
This work is partially supported by Scientific Research Planning Program of Colleges and Universities in Hebei Province (ZD2016005), the Natural Science Foundation of Hebei Province (F2016403055).

摘要/Abstract

摘要： 针对大规模的折扣{0-1}背包问题（D{0-1}KP）难以用确定性算法求解的问题，提出了基于Lévy飞行的差分乌鸦算法（LDECSA）。首先，利用混合编码解决D{0-1}KP的第二数学模型的编码问题；其次，利用新的贪心修复与优化算法（NROA）处理求解过程中产生的不可行解；然后，针对乌鸦个体过早陷入局部最优和收敛较慢等缺陷，引入Lévy飞行和差分策略；最后，通过实验确定了感知概率和飞行长度的合理取值以及差分策略的选择。对四类大规模D{0-1}KP实例的计算结果表明：LDECSA非常适合求解大规模D{0-1}KP，能得到满意的近似解。

关键词: 乌鸦算法, 折扣{0-1}背包问题, Lévy飞行, 差分策略

Abstract: A large-scale Discount {0-1} Knapsack Problem (D{0-1} KP) is difficult to solve with the deterministic algorithms, thus a differential crow search algorithm based on Lévy flight named LDECSA was proposed. Firstly, the coding problem about the second mathematical model of D{0-1} KP was solved by using mixed coding. Secondly, a New greedy Repair and Optimization Algorithm (NROA) was used to deal with the infeasible solution. Thirdly, in order to avoid the problems of local optimum and slow convergence, Lévy flight and differential strategy were introduced. Finally, the reasonable value of awareness probability and flight length were determined through experiments, the differential strategy was also chosen. The experimental results on four types of large-scale D{0-1} KP show that LDECSA is very suitable for solving large-scale D{0-1} KP with very satisfactory approximate solution.

Key words: Crow Search Algorithm (CSA), Discounted{0-1} Knapsack Problem (D{0-1} KP), Lévy flight, differential strategy

中图分类号:

TP18
TP301.6

刘雪静, 贺毅朝, 路凤佳, 吴聪聪, 才秀凤. 基于Lévy飞行的差分乌鸦算法求解折扣{0-1}背包问题[J]. 计算机应用, 2018, 38(2): 433-442.

LIU Xuejing, HE Yichao, LU Fengjia, WU Congcong, CAI Xiufeng. Differential crow search algorithm based on Lévy flight for solving discount {0-1} knapsack problem[J]. Journal of Computer Applications, 2018, 38(2): 433-442.

参考文献

[1] FAYARD D, PLATEAU G. Resolution of the 0-1 knapsack problem:comparison of methods[J]. Mathematical Programming, 1975, 8(1):272-307.
[2] CHU P C, BEASLEY J E. A genetic algorithm for the multidimensional knapsack problem[J]. Journal of Heuristics, 1998, 4(1):63-86.
[3] CHEN Y, HAO J-K. An iterated "hyperplane exploration" approach for the quadratic knapsack problem[J]. Computers & Operations Research, 2017, 77:226-239.
[4] HILEY A, JULSTROM B A. The quadratic multiple knapsack problem and three heuristic approaches to it[C]//GECCO'06:Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation. New York:ACM, 2006:547-552.
[5] GULDAN B. Heuristic and exact algorithms for discounted knapsack problems[D]. Erlangen and Nuremberg, Bavaria, Germany:University of Erlangen-Nürnberg, 2007:1-78.
[6] 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.
[7] 贺毅朝,王熙照,李文斌,等.基于遗传算法求解折扣{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.)
[8] HE Y-C, WANG X-Z, HE Y-L, et al. Exact and approximate algorithms for discounted {0-1} knapsack problem[J]. Information Sciences, 2016, 369:634-647.
[9] 刘雪静,贺毅朝,吴聪聪,等.基于细菌觅食算法求解折扣{0-1}背包问题的研究[J/OL]. 计算机工程与应用(2017-02-16)[2017-08-30]. 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-02-16)[2017-08-18]. http://kns.cnki.net/kcms/detail/11.2127.TP.20170216.1044.038.html.)
[10] 吴聪聪,贺毅朝,陈嶷瑛,等.变异蝙蝠算法求解折扣{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.)
[11] ZHU H, HE Y, WANG X, et al. Discrete differential evolutions for the discounted {0-1} knapsack problem[J]. International Journal of Bio-inspired Computation, 2017, 10(4):219-238.
[12] ASKARZADEH A. A novel metaheuristic method for solving constrained engineering optimization problems:crow search algorithm[J]. Computers & Structures, 2016, 169:1-12.
[13] 贺毅朝,王熙照,寇应展.一种具有混合编码的二进制差分演化算法[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.)
[14] REYNOLDS A M. Cooperative random Lévy flight searches and the flight patterns of honeybees[J]. Physics Letters A, 2006, 354(5/6):384-388.
[15] YANG X-S, DEB S. Cuckoo search via Lévy flights[C]//NaBIC 2009:Proceedings of the 2009 World Congress on Nature & Biologically Inspired Computing. Piscataway, NJ:IEEE, 2009:210-214.
[16] NOMAN N, IBA H. Enhancing differential evolution performance with local search for high dimensional function optimization[C]//GECCO'05:Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation. New York:ACM, 2005:967-974.
[17] 刘雪静,贺毅朝,路凤佳,等.基于差分策略的混沌乌鸦算法求解折扣{0-1}背包问题[J].计算机应用,2018,38(1):137-145. (LIU X J, HE Y C, LU F J, et al, 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.)

基于Lévy飞行的差分乌鸦算法求解折扣{0-1}背包问题

Differential crow search algorithm based on Lévy flight for solving discount {0-1} knapsack problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

[1]	曾明华, 全轲. 双层规划的改进混合布谷鸟搜索量子行为粒子群优化算法[J]. 计算机应用, 2020, 40(7): 1908-1912.
[2]	徐小平, 徐丽, 王峰, 刘龙. 基于Lagrange插值的学习猴群算法求解折扣｛0-1｝背包问题[J]. 计算机应用, 2020, 40(11): 3113-3118.
[3]	史文旭, 杨洋, 鲍胜利. 贪心核加速动态规划算法求解折扣{0-1}背包问题[J]. 计算机应用, 2019, 39(7): 1912-1917.
[4]	杨洋, 潘大志, 刘益, 谭代伦. 折扣{0-1}背包问题的简化新模型及遗传算法求解[J]. 计算机应用, 2019, 39(3): 656-662.
[5]	刘雪静, 贺毅朝, 路凤佳, 吴聪聪, 才秀凤. 基于差分演化策略的混沌乌鸦算法求解折扣{0-1}背包问题[J]. 计算机应用, 2018, 38(1): 137-145.
[6]	吴聪聪, 贺毅朝, 陈嶷瑛, 刘雪静, 才秀凤. 变异蝙蝠算法求解折扣{0-1}背包问题[J]. 计算机应用, 2017, 37(5): 1292-1299.