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

doi:10.3778/j.issn.1002-8331.1608-0168

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

基于细菌觅食算法求解折扣{0-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

College of Information Engineering, Hebei GEO University, Shijiazhuang 050031, China

Online:2018-01-15 Published:2018-01-31

摘要/Abstract

摘要： 折扣{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

刘雪静，贺毅朝，吴聪聪，才秀凤. 基于细菌觅食算法求解折扣{0-1}背包问题的研究[J]. 计算机工程与应用, 2018, 54(2): 155-162.

LIU Xuejing, HE Yichao, WU Congcong, CAI Xiufeng. Research on bacterial foraging optimization algorithm for discounted {0-1} knapsack problem[J]. Computer Engineering and Applications, 2018, 54(2): 155-162.

[1]	郝翔，贺毅朝，朱晓斌，翟庆雷. 基于离散混合多宇宙算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2021, 57(18): 103-113.
[2]	张铭，邓文瀚，林娟，钟一文. 改进蚁群优化算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2021, 57(13): 85-95.
[3]	吴聪聪，贺毅朝，赵建立. 求解折扣{0-1}背包问题的新遗传算法[J]. 计算机工程与应用, 2020, 56(7): 57-66.
[4]	杨洋1，潘大志1，贺毅朝2. 改进修复策略遗传算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2018, 54(21): 37-42.
[5]	刘雪静1，贺毅朝1，吴聪聪1，李靓2. 自适应细菌觅食算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2018, 54(18): 139-146.
[6]	刘雪静1，贺毅朝1，吴聪聪1，李靓2. 求解0-1背包问题的混沌二进制乌鸦算法[J]. 计算机工程与应用, 2018, 54(10): 173-179.
[7]	吴聪聪，贺毅朝，陈嶷瑛，刘雪静，才秀凤. 求解0-1背包问题的二进制蝙蝠算法[J]. 计算机工程与应用, 2015, 51(19): 71-74.
[8]	李童1，毛力1，吴滨1，杨弘2，肖炜2. 一种基于竞选领导策略的改进粒子群算法[J]. 计算机工程与应用, 2014, 50(20): 36-40.
[9]	杨大炼，李学军，蒋玲莉. 一种细菌觅食算法的改进及其应用[J]. 计算机工程与应用, 2012, 48(13): 31-34.
[10]	赵洋¹，单娟². 二进制混合蛙跳算法求解0-1背包问题[J]. 计算机工程与应用, 2010, 46(35): 39-41.
[11]	陈云川，徐峥，罗克露. Rotate-N-Puzzle问题可解性分析及求解 [J]. 计算机工程与应用, 2010, 46(15): 37-40.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 11

编辑推荐

Metrics