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

Genetic mutation bat algorithm for 0-1 knapsack problem

作　　者：李枝勇[1] 马良[1] 张惠珍[1] 

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《计算机工程与应用》2014年第11期49-52,共4页Computer Engineering and Applications

基　　金：国家自然科学基金(No.70871081);上海市研究生创新基金项目(No.JWCXSL1202)

摘　　要：0-1背包问题是经典组合优化NP难题。在蝙蝠算法的基础上结合遗传变异的思想,引入主动进化算子、无效蝙蝠和当前最优位置蝙蝠集聚的处理规则,提出了遗传变异蝙蝠算法,并将其用于求解0-1背包问题。仿真结果表明:该算法在收敛速度和精度上优于基本蝙蝠算法,并且能够有效地求解0-1背包问题。0-1 knapsack problem is a typical NP-hard combinatorial optimization problem. A new hybrid intelligent algo-rithm 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.

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

分 类 号：O221.4[理学—运筹学与控制论]