计算机工程与应用 ›› 2018, Vol. 54 ›› Issue (2): 155-162.DOI: 10.3778/j.issn.1002-8331.1608-0168

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

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

刘雪静,贺毅朝,吴聪聪,才秀凤   

  1. 河北地质大学 信息工程学院,石家庄 050031
  • 出版日期:2018-01-15 发布日期:2018-01-31

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

LIU Xuejing, HE Yichao, WU Congcong, CAI Xiufeng   

  1. College of Information Engineering, Hebei GEO University, Shijiazhuang 050031, China
  • Online:2018-01-15 Published:2018-01-31

摘要: 折扣{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}背包问题, 细菌觅食算法, 贪心策略, 修复与优化

Abstract: The Discounted {0-1} Knapsack Problem (D{0-1}KP) is an extension of the classical 0-1 Knapsack Problem(0-1KP). In this paper, it uses Bacterial Foraging Optimization algorithm(BFO) to solve D{0-1}KP, Firstly, the two mathematical models of the D{0-1}KP are described, and then BFO is combined with the two mathematical models, the bacterial individual uses the binary vector and the four binary vector coding method, and the greedy strategy is used to optimize the initial solution and repair the non normal coding individuals, FirBFO and SecBFO algorithms for solving D{0-1}KP are given. The calculations of four instances show that, FirBFO and SecBFO are suitable for solving large scale hard D{0-1}KP. And they can also obtain the approximate solution whose approximation rate is almost equal to 1.

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