Binary bat algrorithm for solving 0-1 knapsack problem

Abstract

Abstract: For solving the optimization problem in discrete space, a Binary Bat Algorithm（BBA） is proposed, and time-varying inertia factor is introduced to improve the global convergence speed of the algorithm. In order to increase the probability of finding the optimal solution in solving 0-1 knapsack problem, greedy strategy is used in the algorithm, thus a Greedy Binary Bat Algorithm（GBBA） is proposed. Simulations show that the proposed algorithm is much superior to GMBA algorithm in searching capability and convergence performance.

Key words: bat algorithm, 0-1 knapsack problem, optimization problem, greedy strategy

摘要： 为了求解离散空间中的最优化问题，提出了一种二进制蝙蝠算法，并引入时变惯性因子来提高算法的全局收敛速度；在此基础上，为提高求解0-1背包问题时找到最优解的机率，利用贪心优化策略对无效的蝙蝠个体进行优化，从而给出了贪心二进制蝙蝠算法（GBBA）。仿真计算结果表明，GBBA算法在寻优能力和收敛性能方面比已有的GMBA算法都更优越。

关键词: 蝙蝠算法, 0-1背包问题, 最优化问题, 贪心策略

WU Congcong, HE Yichao, CHEN Yiying, LIU Xuejing, CAI Xiufeng. Binary bat algrorithm for solving 0-1 knapsack problem[J]. Computer Engineering and Applications, 2015, 51(19): 71-74.

吴聪聪，贺毅朝，陈嶷瑛，刘雪静，才秀凤. 求解0-1背包问题的二进制蝙蝠算法[J]. 计算机工程与应用, 2015, 51(19): 71-74.

[1]	SHI Chuntian, ZENG Yanyang, HOU Shouming. Summary of Application of Swarm Intelligence Algorithms in Image Segmentation [J]. Computer Engineering and Applications, 2021, 57(8): 36-47.
[2]	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.
[3]	WANG Keyin, SHI Zhen, YANG Zhengcai, YANG Yahui, WANG Sishan. Path Planning for Mobile Robot Using Improved Reinforcement Learning Algorithm [J]. Computer Engineering and Applications, 2021, 57(18): 270-274.
[4]	LI Miaomiao, WANG Qiuping, HUI Hui. Enhanced Bat Algorithm Based on Fractional-Order Strategy and Spiral with Lévy Flight [J]. Computer Engineering and Applications, 2021, 57(18): 75-81.
[5]	YANG Tong, QIN Jin. Adaptive ε-greedy Strategy Based on Average Episodic Cumulative Reward [J]. Computer Engineering and Applications, 2021, 57(11): 148-155.
[6]	XU Hanyu, FENG Xiang, YU Huiqun. Novel Optimization Algorithm Based on Universal Gravitational and Colon State Adaptation [J]. Computer Engineering and Applications, 2020, 56(9): 48-55.
[7]	QU Tuosi, CAO Haiyan, XU Fangmin, FANG Xin, WANG Xiumin. Research on Optimized Pilot Allocation Schemes in Massive MIMO System [J]. Computer Engineering and Applications, 2020, 56(8): 60-65.
[8]	LI Yali, WANG Shuqin, CHEN Qianru, WANG Xiaogang. Comparative Study of Several New Swarm Intelligence Optimization Algorithms [J]. Computer Engineering and Applications, 2020, 56(22): 1-12.
[9]	CHEN Yao, CHEN Si. Research on Application of Dynamic Weighted Bat Algorithm in Image Segmentation [J]. Computer Engineering and Applications, 2020, 56(14): 207-215.
[10]	GENG Yinfeng, ZHANG Xueying, LI Fenglian, HU Fengyun, JIA Wenhui, WANG Chao. Optimized Extreme Learning Machine and Its Application in Classification of Stroke TCD Data [J]. Computer Engineering and Applications, 2020, 56(10): 268-272.
[11]	YIN Jianjin1, ZHANG Beike1, GAO Dong1, XU Xin2. Improved Bat Algorithm for Solving Flexible Flow Shop Scheduling Problem and Its Application [J]. Computer Engineering and Applications, 2019, 55(9): 243-247.
[12]	CUI Fangyi1, JING Xiaoyuan2, DONG Xiwei2，3, WU Fei2, SUN Ying2. Fuzzy Clustering Based on Adaptive Bat Algorithm Optimization and Its Application [J]. Computer Engineering and Applications, 2019, 55(7): 16-22.
[13]	XU Degang, ZHAO Ping. Literature Survey on Research and Application of Bat Algorithm [J]. Computer Engineering and Applications, 2019, 55(15): 1-12.
[14]	GU Jing，HOU Yongping，ZHANG Xin. Dynamic CRE Bias Selection Based on Improved Bat Algorithm in Heterogeneous Networks [J]. Computer Engineering and Applications, 2019, 55(13): 93-99.
[15]	YU Xin, WU Lingzhen, WANG Yanlin. New Neural Network for Solving Nonsmooth Pseudoconvex Optimization Problems [J]. Computer Engineering and Applications, 2019, 55(12): 37-43.

Binary bat algrorithm for solving 0-1 knapsack problem

求解0-1背包问题的二进制蝙蝠算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics