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

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

Computer Engineering and Applications ›› 2018, Vol. 54 ›› Issue (18): 139-146.DOI: 10.3778/j.issn.1002-8331.1803-0102

Previous Articles Next Articles

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

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

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

1.河北地质大学信息工程学院，石家庄 050031
2.中国邮政集团公司河北省邮政信息技术局，石家庄 050011

Abstract

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

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

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

[1]	MA Jun，WANG Yuhao. Object Tracking Algorithm Based on Adaptive Update Strategy and Re-detection Technology [J]. Computer Engineering and Applications, 2021, 57(9): 217-224.
[2]	ZHANG Songcan, PU Jiexin, SI Yanna, SUN Lifan. Adaptive Improved Ant Colony Algorithm Based on Population Similarity and Its Application [J]. Computer Engineering and Applications, 2021, 57(8): 70-77.
[3]	ZHAO Linsuo, MA Ruiqiang, JIANG Tian, SONG Baoyan,PAN Yishan. Adaptive Early Warning Method for Streaming Big Data Events Based on Two-Stage Regression [J]. Computer Engineering and Applications, 2021, 57(7): 88-94.
[4]	BU Guannan, LIU Jianhua, JIANG Lei, ZHANG Dongyang. Ant Colony Algorithm with Adaptive Grouping [J]. Computer Engineering and Applications, 2021, 57(6): 67-73.
[5]	NI Zongjun, CHEN Hui, ZHANG Yun, SU Min, ZHENG Xiujuan. Non-contact Physiological Parameter Estimation Method Based on Adaptive Denoising [J]. Computer Engineering and Applications, 2021, 57(5): 153-160.
[6]	CHEN Shiming, LIN Zipeng, GAO Yanli, PEI Huiqin. Heterogeneous Group Consensus Under Adaptive Coupling Weights [J]. Computer Engineering and Applications, 2021, 57(4): 231-235.
[7]	WANG Fuyin, ZHANG Desheng, ZHANG Xiao. Adaptive Density Peaks Clustering Algorithm Combining with Whale Optimization Algorithm [J]. Computer Engineering and Applications, 2021, 57(3): 94-102.
[8]	CHEN Mingyue, LIU Sanyang. Application of Adaptive Manifold Learning in Fault Diagnosis [J]. Computer Engineering and Applications, 2021, 57(3): 247-252.
[9]	XIAO Zhenjiu, KONG Xiangxu, ZONG Jiaxu, YANG Yueying. Image Object Detection Algorithm Based on Adaptive Focal Loss [J]. Computer Engineering and Applications, 2021, 57(23): 185-192.
[10]	ZHANG Zhonglin, ZHAO Yu, YAN Guanghui. Natural Neighbor Density Extremum Clustering Algorithm [J]. Computer Engineering and Applications, 2021, 57(23): 200-210.
[11]	CHANG Yawen, ZHAO Dongqing, SHAN Yanhu. Research on Stereo Matching Algorithm Based on Multi-feature Fusion and Adaptive Aggregation [J]. Computer Engineering and Applications, 2021, 57(23): 219-225.
[12]	LI Ya, HOU Yandong, LIU Chang. Adaptive Optimal Fault-Tolerant Control Based on Fault Degree [J]. Computer Engineering and Applications, 2021, 57(23): 295-302.
[13]	CHEN Yao, CHEN Si. Improved Bat Algorithm Based on Self-adaptive Doppler and Dynamic Neighborhood Strategy [J]. Computer Engineering and Applications, 2021, 57(22): 166-176.
[14]	CHEN Fujian, XIE Weixin, XIA Ting. Adaptive Anti-occlusion Target Tracking Algorithm Based on LCT+ [J]. Computer Engineering and Applications, 2021, 57(22): 190-198.
[15]	QI Xiaoxiang, LI Min, ZHU Ying, SONG Yu, DU Weidong. Adaptive Region Segmentation of SAR Image Based on Edge Detection [J]. Computer Engineering and Applications, 2021, 57(22): 232-240.

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

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics