基于Lévy飞行的差分乌鸦算法求解折扣{0-1}背包问题
来源：计算机应用杂志2018年第2期北京时间：
作者：刘雪静, 贺毅朝, 路凤佳, 吴聪聪, 才秀凤
单位：河北地质大学 信息工程学院, 石家庄 050031
摘要：针对大规模的折扣{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飞行,差分策略
基金资助：河北省高等学校科学研究计划项目（ZD2016005）；河北省自然科学基金资助项目（F2016403055）。
