计算机工程与应用 ›› 2018, Vol. 54 ›› Issue (18): 139-146.DOI: 10.3778/j.issn.1002-8331.1803-0102

• 模式识别与人工智能 • 上一篇    下一篇

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

刘雪静1,贺毅朝1,吴聪聪1,李  靓2   

  1. 1.河北地质大学 信息工程学院,石家庄 050031
    2.中国邮政集团公司 河北省邮政信息技术局,石家庄 050011
  • 出版日期:2018-09-15 发布日期:2018-10-16

Adaptive bacterial foraging optimization algorithm for discounted {0-1} knapsack problem

LIU Xuejing1, HE Yichao1, WU Congcong1, LI Liang2   

  1. 1.College of Information Engineering, Hebei GEO University, Shijiazhuang 050031, China
    2.Hebei Post Information Technology Bureau, China Post Group Corporation, Shijiazhuang 050011, China
  • Online:2018-09-15 Published:2018-10-16

摘要: 针对确定性算法难以求解的大规模折扣{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}背包问题, 细菌觅食算法, 自适应, 贪心修复与优化

Abstract: For the large-scale Discount{0-1} Knapsack Problem(D{0-1}KP) which is difficult to be solved by deterministic algorithm, two algorithms based on Adaptive Bacterial Foraging Optimization(ABFO) are proposed. Firstly, two mathematical models of D{0-1}KP are given. Secondly, the adaptive chemotaxis strategy is proposed. Thirdly, two greedy repair and optimization strategies are used to deal with non-normal solutions, and FirABFO and SecABFO are proposed. The simulation results show that both FirABFO and SecABFO are very suitable for solving large-scale D{0-1}KP instances, they can get best solution or approximate solution with approximate ratio almost closing to 1, and SecABFO has better solution performance than FirABFO.

Key words: discounted{0-1} knapsack problem, bacterial foraging algorithm, adaptive, greedy repair and optimization