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

• 理论研究、研发设计 • 上一篇    下一篇

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

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

  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   

  1. School of Information Engineering, Shijiazhuang University of Economics, Shijiazhuang 050031, China
  • Online:2015-09-30 Published:2015-10-13

摘要: 为了求解离散空间中的最优化问题,提出了一种二进制蝙蝠算法,并引入时变惯性因子来提高算法的全局收敛速度;在此基础上,为提高求解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