• 人工智能 •

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

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

1. 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: 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.