• 先进计算 •

变异蝙蝠算法求解折扣{0-1}背包问题

1. 河北地质大学 信息工程学院, 石家庄 050031
• 收稿日期:2016-10-24 修回日期:2016-12-08 出版日期:2017-05-10 发布日期:2017-05-16
• 通讯作者: 吴聪聪
• 作者简介:吴聪聪(1975-),女,河北唐山人,讲师,硕士,主要研究方向:智能计算、信息检索、机器学习;贺毅朝(1969-),男,河北晋州人,教授,CCF高级会员,主要研究方向:进化算法理论与应用、算法设计与分析、计算复杂性理论与群测试理论;陈嶷瑛(1971-),女,湖南宁远人,教授,博士,主要研究方向:机器学习、地理信息系统;刘雪静(1980-),女,河北定州人,讲师,硕士,主要研究方向:智能计算、机器学习;才秀凤(1979-),女,河北丰润人,讲师,硕士,主要研究方向:智能计算、机器学习。
• 基金资助:
河北省高等学校科学研究计划项目（ZD2016005）；河北省自然科学基金资助项目（F2016403055）。

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

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).

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.