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

doi:10.3778/j.issn.1002-8331.1803-0102

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

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

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

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.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

摘要/Abstract

摘要： 针对确定性算法难以求解的大规模折扣{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

刘雪静1，贺毅朝1，吴聪聪1，李靓2. 自适应细菌觅食算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2018, 54(18): 139-146.

LIU Xuejing1, HE Yichao1, WU Congcong1, LI Liang2. Adaptive bacterial foraging optimization algorithm for discounted {0-1} knapsack problem[J]. Computer Engineering and Applications, 2018, 54(18): 139-146.

[1]	马珺，王昱皓. 结合自适应更新策略和再检测技术的跟踪算法[J]. 计算机工程与应用, 2021, 57(9): 217-224.
[2]	张松灿，普杰信，司彦娜，孙力帆. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77.
[3]	邹杰，李俊. 多策略协方差矩阵学习差分进化算法[J]. 计算机工程与应用, 2021, 57(7): 78-87.
[4]	赵林锁，马瑞强，姜天，宋宝燕，潘一山. 两级回归的流式大数据事件自适应预警方法[J]. 计算机工程与应用, 2021, 57(7): 88-94.
[5]	卜冠南，刘建华，姜磊，张冬阳. 一种自适应分组的蚁群算法[J]. 计算机工程与应用, 2021, 57(6): 67-73.
[6]	倪宗军，陈辉，张昀，苏敏，郑秀娟. 自适应去噪的非接触式生理参数检测方法[J]. 计算机工程与应用, 2021, 57(5): 153-160.
[7]	陈世明，林子朋，高彦丽，裴惠琴. 自适应耦合权重下的异质群体一致性研究[J]. 计算机工程与应用, 2021, 57(4): 231-235.
[8]	王芙银，张德生，张晓. 结合鲸鱼优化算法的自适应密度峰值聚类算法[J]. 计算机工程与应用, 2021, 57(3): 94-102.
[9]	陈明月，刘三阳. 自适应流形学习在故障诊断中的应用[J]. 计算机工程与应用, 2021, 57(3): 247-252.
[10]	肖振久，孔祥旭，宗佳旭，杨玥莹. 自适应聚焦损失的图像目标检测算法[J]. 计算机工程与应用, 2021, 57(23): 185-192.
[11]	张忠林，赵昱，闫光辉. 自然邻居密度极值聚类算法[J]. 计算机工程与应用, 2021, 57(23): 200-210.
[12]	畅雅雯，赵冬青，单彦虎. 多特征融合和自适应聚合的立体匹配算法研究[J]. 计算机工程与应用, 2021, 57(23): 219-225.
[13]	李雅，侯彦东，刘畅. 基于故障程度的自适应优化容错控制[J]. 计算机工程与应用, 2021, 57(23): 295-302.
[14]	陈瑶，陈思. 基于自适应多普勒及动态邻域的改进BA算法[J]. 计算机工程与应用, 2021, 57(22): 166-176.
[15]	陈富健，谢维信，夏婷. 基于LCT+的自适应抗遮挡目标跟踪算法[J]. 计算机工程与应用, 2021, 57(22): 190-198.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics