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

• •

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

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

1. 河北地质大学
2. 河北地质大学信息工程学院
3. 石家庄经济学院信息工程学院

收稿日期:2017-07-27 修回日期:2017-09-08 发布日期:2017-09-08
通讯作者: 刘雪静

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

Received:2017-07-27 Revised:2017-09-08 Online:2017-09-08
Contact: Xue-Jing LIU

摘要/Abstract

摘要： 摘要: 针对大规模的折扣{0-1}背包问题（Discount {0-1}Knapsack Problem, D{0-1}KP）难以用确定性算法求解的问题，提出了基于Lévy飞行的差分乌鸦算法(Differential Crow Search Algorithm based on Lévy Flight, LDECSA)。首先，利用混合编码解决D{0-1}KP的第二数学模型的编码问题；其次，利用新的贪心修复与优化算法（New greedy Repair and Optimization Algorithm, 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) was difficult to solve with the deterministic algorithm, a differential crow algorithm based on Lévy flight (LDECSA) was proposed. Firstly, the coding problem of the second mathematical model of D{0-1}KP was solved by using mixed coding. Secondly, the new greedy repair and optimization algorithm (NROA) was used to deal with the infeasible solution. Thirdly, in order to avoid the local optimum and the slowly 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 choosed. The results show that LDECSA is very suitable for solving large-scale D{0-1}KP, and it can obtain very satisfactory approximate solution.

Key words: crow search algorithm, discount {0-1} knapsack problem, Lévy flight, greedy repair and optimization strategy, differential strategy

中图分类号:

TP18

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

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