遗传变异蝙蝠算法在0-1背包问题上的应用

计算机工程与应用 ›› 2014, Vol. 50 ›› Issue (11): 49-52.

遗传变异蝙蝠算法在0-1背包问题上的应用

李枝勇，马良，张惠珍

上海理工大学管理学院，上海 200093

出版日期:2014-06-01 发布日期:2015-04-08

Genetic mutation bat algorithm for 0-1 knapsack problem

LI Zhiyong, MA Liang, ZHANG Huizhen

School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China

Online:2014-06-01 Published:2015-04-08

摘要/Abstract

摘要： 0-1背包问题是经典组合优化NP难题。在蝙蝠算法的基础上结合遗传变异的思想，引入主动进化算子、无效蝙蝠和当前最优位置蝙蝠集聚的处理规则，提出了遗传变异蝙蝠算法，并将其用于求解0-1背包问题。仿真结果表明：该算法在收敛速度和精度上优于基本蝙蝠算法，并且能够有效地求解0-1背包问题。

关键词: 蝙蝠算法, 0-1背包问题, 遗传变异

Abstract: 0-1 knapsack problem is a typical NP-hard combinatorial optimization problem. A new hybrid intelligent algorithm for solving the 0-1 knapsack problem, is presented in this paper by combining genetic mutation with bat algorithm. Moreover, the active evolutionary operators and the methods of converting invalid bats into valid ones as well as avoiding bat gathering are introduced into the new hybrid algorithm for maintaining the diversified bat population and improving the convergence performance. Simulation results show that the new hybrid algorithm can solve the 0-1 knapsack problem effectively, and has better convergence rate and higher computation precision than the bat algorithm.

Key words: bat algorithm, 0-1 knapsack problem, genetic mutation

李枝勇，马良，张惠珍. 遗传变异蝙蝠算法在0-1背包问题上的应用[J]. 计算机工程与应用, 2014, 50(11): 49-52.

LI Zhiyong, MA Liang, ZHANG Huizhen. Genetic mutation bat algorithm for 0-1 knapsack problem[J]. Computer Engineering and Applications, 2014, 50(11): 49-52.

[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，吴聪聪1，李靓2. 求解0-1背包问题的混沌二进制乌鸦算法[J]. 计算机工程与应用, 2018, 54(10): 173-179.
[13]	张文鹏，王兴. 改进型蝙蝠算法在作业车间调度问题中的应用[J]. 计算机工程与应用, 2017, 53(8): 137-140.
[14]	裴文杰，汪沨，谭阳红，尹健，蒋勤稷. 基于蝙蝠算法的电力恢复机组选择多目标优化[J]. 计算机工程与应用, 2017, 53(2): 225-230.
[15]	裴文杰，谭阳红，汪沨，蒋勤稷，梁芳蔚. 蝙蝠算法在含DG配电网故障定位中的应用[J]. 计算机工程与应用, 2016, 52(22): 218-221.