摘要
针对大规模的折扣{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,能得到满意的近似解。
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.
作者
刘雪静
贺毅朝
路凤佳
吴聪聪
才秀凤
LIU Xuejing;HE Yichao;LU Fenjia;WU Congcong;CAI Xiufeng(School of Information Technology,Hebei GEO University,Shijiazhuang Hebei 050031,China)
出处
《计算机应用》
CSCD
北大核心
2018年第2期433-442,共10页
journal of Computer Applications
基金
河北省高等学校科学研究计划项目(ZD2016005)
河北省自然科学基金资助项目(F2016403055)
关键词
乌鸦算法
折扣{0-1}背包问题
Lévy飞行
差分策略
Crow Search Algorithm(CSA)
Discounted{0-1}Knapsack Problem(D{0-1}KP)
Lévy flight
differential strategy
