求解0-1背包问题的二进制蝙蝠算法-计算机工程与应用.pdf

Computer Engineering and Applications 计算机工程与应用 2015 ，51（19） 71 求解0-1 背包问题的二进制蝙蝠算法 吴聪聪，贺毅朝，陈嶷瑛，刘雪静，才秀凤 WU Congcong, HE Yichao, CHEN Yiying, LIU Xuejing, CAI Xiufeng 石家庄经济学院 信息工程学院，石家庄 050031 School of Information Engineering, Shijiazhuang University of Economics, Shijiazhuang 050031, China WU Congcong, HE Yichao, CHEN Yiying, et al. Binary bat algrorithm for solving 0-1 knapsack problem. Computer Engineering and Applications, 2015, 51 （19）：71-74. 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 背包问题；最优化问题；贪心策略 文献标志码：A 中图分类号：TP 18 doi ：10.3778/j.issn. 1002-8331.1501-0096 1 引言 重量在不超过背包载重的前提下总价值最高。 [1] 0- 1KP 的数学模型表示如下： 背包问题（Knapsack Problem ，KP ）是典型的组合 d 优化难题，具有较高的理论研究与实际应用价值，在投 max Z åv x （1） i i 资决策、预算控制、项目选择、资源分配和货物装载等方