Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (2): 433-442.DOI: 10.11772/j.issn.1001-9081.2017071852

Previous Articles     Next Articles

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   

  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).


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

  1. 河北地质大学 信息工程学院, 石家庄 050031
  • 通讯作者: 刘雪静
  • 作者简介:刘雪静(1980-),女,河北定州人,讲师,硕士,CCF会员,主要研究方向:演化计算、机器学习;贺毅朝(1969-),男,河北晋州人,教授,硕士,CCF高级会员,主要研究方向:智能计算、计算复杂性理论;路凤佳(1980-),女,河北沧州人,讲师,硕士,主要研究方向:大数据、机器学习;吴聪聪(1975-),女,河北唐山人,讲师,硕士,主要研究方向:智能计算、信息检索、机器学习;才秀凤(1978-),女,河北丰润人,讲师,硕士,主要研究方向:智能计算、机器学习。
  • 基金资助:

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

摘要: 针对大规模的折扣{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飞行, 差分策略

CLC Number: