自适应细菌觅食算法求解折扣{0-1}背包问题

来源：计算机工程与应用杂志2018年第18期北京时间：

作者：刘雪静1，贺毅朝1，吴聪聪1，李 靓2

单位：1.河北地质大学 信息工程学院，石家庄 050031 ；2.中国邮政集团公司 河北省邮政信息技术局，石家庄 050011

摘要：针对确定性算法难以求解的大规模折扣{0-1}背包问题（D{0-1}KP），提出了自适应细菌觅食算法（ABFO）求解D{0-1}KP的两种算法。首先，给出了D{0-1}KP的两种数学模型；然后，针对细菌觅食算法的趋化操作提出了自适应趋化策略；最后，利用两种贪心修复与优化策略处理两种数学模型中的不可行解，得到求解D{0-1}KP的FirABFO和SecABFO算法。仿真实验表明，FirABFO和SecABFO均能得到最优解或近似比几乎等于1的近似解，非常适于求解D{0-1}KP，并且SecABFO 的求解性能比FirABFO更优。

关键词：折扣{0-1}背包问题,细菌觅食算法,自适应,贪心修复与优化