基于细菌觅食算法求解折扣{0-1}背包问题的研究

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

作者：刘雪静，贺毅朝，吴聪聪，才秀凤

单位：河北地质大学 信息工程学院，石家庄 050031

摘要：折扣{0-1}背包问题（D{0-1}KP）是新型的0-1背包问题。提出了基于细菌觅食算法（BFO）求解D{0-1}KP的方法，首先描述了D{0-1}KP的两个数学模型，然后将BFO分别与两个数学模型相结合，即细菌个体分别采用二进制向量和四进制向量的编码方法，并利用贪心策略优化初始解和修复非正常编码个体，给出了求解D{0-1}KP的FirBFO和SecBFO算法。对四类实例的计算结果表明，FirBFO和SecBFO都非常适于求解大规模的D{0-1}KP实例，能得到最优解或近似比接近1的近似解。

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