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

作者：刘雪静; 贺毅朝; 吴聪聪; 李靓

来源：计算机工程与应用, 2018, 54(18): 139-270.

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

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

• 单位
  河北地质大学; 中国邮政集团公司