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

计算机工程与应用 ›› 2015, Vol. 51 ›› Issue (19): 71-74.

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

吴聪聪，贺毅朝，陈嶷瑛，刘雪静，才秀凤

石家庄经济学院信息工程学院，石家庄 050031

出版日期:2015-09-30 发布日期:2015-10-13

Binary bat algrorithm for solving 0-1 knapsack problem

WU Congcong, HE Yichao, CHEN Yiying, LIU Xuejing, CAI Xiufeng

School of Information Engineering, Shijiazhuang University of Economics, Shijiazhuang 050031, China

Online:2015-09-30 Published:2015-10-13

摘要/Abstract

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

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

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背包问题的二进制蝙蝠算法[J]. 计算机工程与应用, 2015, 51(19): 71-74.

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.

[1]	史春天，曾艳阳，侯守明. 群体智能算法在图像分割中的应用综述[J]. 计算机工程与应用, 2021, 57(8): 36-47.
[2]	陈瑶，陈思. 基于自适应多普勒及动态邻域的改进BA算法[J]. 计算机工程与应用, 2021, 57(22): 166-176.
[3]	李苗苗，王秋萍，惠蕙. 分数阶策略和带有Lévy飞行的螺旋蝙蝠算法[J]. 计算机工程与应用, 2021, 57(18): 75-81.
[4]	陈瑶，陈思. 动态权重的蝙蝠算法在图像分割中的应用研究[J]. 计算机工程与应用, 2020, 56(14): 207-215.
[5]	耿银凤，张雪英，李凤莲，胡风云，贾文辉，王超. 优化极限学习机及其在脑卒中TCD数据分类应用[J]. 计算机工程与应用, 2020, 56(10): 268-272.
[6]	尹建津1，张贝克1，高东1，许欣2. 改进蝙蝠算法解决FFSP问题及其应用研究[J]. 计算机工程与应用, 2019, 55(9): 243-247.
[7]	崔芳怡1，荆晓远2，董西伟2，3，吴飞2，孙莹2. 自适应蝙蝠算法优化的模糊聚类及其应用[J]. 计算机工程与应用, 2019, 55(7): 16-22.
[8]	许德刚，赵萍. 蝙蝠算法研究及应用综述[J]. 计算机工程与应用, 2019, 55(15): 1-12.
[9]	谷静，侯永平，张新. 异构网中基于改进蝙蝠算法的动态CRE偏置选择[J]. 计算机工程与应用, 2019, 55(13): 93-99.
[10]	刘春苗，张惠珍. 求解无容量设施选址问题的混合蝙蝠算法[J]. 计算机工程与应用, 2018, 54(22): 28-34.
[11]	李帆1，高东1，许欣2，张玉良2. 改进蝙蝠算法柔性作业车间调度问题研究[J]. 计算机工程与应用, 2018, 54(21): 265-270.
[12]	杨洋1，潘大志1，贺毅朝2. 改进修复策略遗传算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2018, 54(21): 37-42.
[13]	刘雪静，贺毅朝，吴聪聪，才秀凤. 基于细菌觅食算法求解折扣{0-1}背包问题的研究[J]. 计算机工程与应用, 2018, 54(2): 155-162.
[14]	刘雪静1，贺毅朝1，吴聪聪1，李靓2. 求解0-1背包问题的混沌二进制乌鸦算法[J]. 计算机工程与应用, 2018, 54(10): 173-179.
[15]	张文鹏，王兴. 改进型蝙蝠算法在作业车间调度问题中的应用[J]. 计算机工程与应用, 2017, 53(8): 137-140.