Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (5): 1292-1299.DOI: 10.11772/j.issn.1001-9081.2017.05.1292

Previous Articles     Next Articles

Mutated bat algorithm for solving discounted {0-1} knapsack problem

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

  1. College of Information Engineering, Hebei GEO University, Shijiazhuang Hebei 050031, China
  • Received:2016-10-24 Revised:2016-12-08 Online:2017-05-10 Published:2017-05-16
  • Supported by:
    This work is partially supported by Scientific Research Project Program of Colleges and Universities in Hebei Province (ZD2016005), the Natural Science Foundation of Hebei Province (F2016403055).


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

  1. 河北地质大学 信息工程学院, 石家庄 050031
  • 通讯作者: 吴聪聪
  • 作者简介:吴聪聪(1975-),女,河北唐山人,讲师,硕士,主要研究方向:智能计算、信息检索、机器学习;贺毅朝(1969-),男,河北晋州人,教授,CCF高级会员,主要研究方向:进化算法理论与应用、算法设计与分析、计算复杂性理论与群测试理论;陈嶷瑛(1971-),女,湖南宁远人,教授,博士,主要研究方向:机器学习、地理信息系统;刘雪静(1980-),女,河北定州人,讲师,硕士,主要研究方向:智能计算、机器学习;才秀凤(1979-),女,河北丰润人,讲师,硕士,主要研究方向:智能计算、机器学习。
  • 基金资助:

Abstract: Since the deterministic algorithms are difficult to solve the Discounted {0-1} Knapsack Problem (D{0-1}KP) with large-scale and wide data range, a Mutated Double codes Binary Bat Algorithm (MDBBA) was proposed. Firstly, the coding problem of D{0-1} KP was solved by double coding. Secondly, the Greedy Repair and Optimization Algorithm (GROA) was applied to the individual fitness calculation of bats, and the algorithm was quickly and effectively solved. Then, the mutation strategy in Differential Evolution (DE) was selected to improve the global optimization ability. Finally, Lévy flight was carried out by the bat individual according to certain probability to enhance the ability of the algorithm to explore and jump out of local extrema. Simulation was tested on four large-scale instances. The result shows that MDBBA is very suitable for solving large-scale D {0-1} KP, which has better optimal value and mean value than FirEGA (First Genetic Algorithm) algorithm and Double Binary Bat Algorithm (DBBA), and MDBBA converges significantly faster than DBBA.

Key words: Discounted {0-1} Knapsack Problem (D{0-1}KP), Bat Algorithm (BA), differential evolution, Lévy flight, greedy strategy, non-normal coding

摘要: 针对确定性算法难于求解规模大、数据范围广的折扣{0-1}背包问题(D{0-1}KP),提出了基于蝙蝠算法的快速求解D{0-1}KP的变异蝙蝠算法(MDBBA)。首先,利用双重编码解决D{0-1}KP的编码问题;其次,将贪心修复与优化算法(GROA)应用于蝙蝠个体适应度计算中,使算法快速得到有效解;然后,选择使用差分演化(DE)的变异策略提高算法的全局寻优能力;最后,蝙蝠个体按一定概率进行Lévy飞行,增强算法探索能力和跳出局部极值的能力。对四类大规模实例的仿真计算表明:MDBBA非常适于求解大规模的D{0-1}KP,比第一遗传算法(FirEGA)和双重编码蝙蝠算法(DBBA)求得的最优值和平均值都更优,MDBBA收敛速度明显快于DBBA。

关键词: 折扣{0-1}背包问题, 蝙蝠算法, 差分演化, Lé, vy飞行, 贪心策略, 非正常编码

CLC Number: