| 变异蝙蝠算法求解折扣{0-1}背包问题 |
| |
| 引用本文： | 吴聪聪,贺毅朝,陈嶷瑛,刘雪静,才秀凤. 变异蝙蝠算法求解折扣{0-1}背包问题[J]. 计算机应用, 2017, 37(5): 1292-1299. DOI: 10.11772/j.issn.1001-9081.2017.05.1292 |
| |
| 作者姓名： | 吴聪聪 贺毅朝 陈嶷瑛 刘雪静 才秀凤 |
| |
| 作者单位： | 河北地质大学 信息工程学院, 石家庄 050031 |
| |
| 基金项目： | 河北省高等学校科学研究计划项目（ZD2016005）；河北省自然科学基金资助项目（F2016403055）。 |
| |
| 摘 要： | 针对确定性算法难于求解规模大、数据范围广的折扣{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飞行 贪心策略 非正常编码 |
| 收稿时间： | 2016-10-24 |
| 修稿时间： | 2016-12-08 |
Mutated bat algorithm for solving discounted {0-1} knapsack problem |
| |
| WU Congcong,HE Yichao,CHEN Yiying,LIU Xuejing,CAI Xiufeng. Mutated bat algorithm for solving discounted {0-1} knapsack problem[J]. Journal of Computer Applications, 2017, 37(5): 1292-1299. DOI: 10.11772/j.issn.1001-9081.2017.05.1292 |
| |
| Authors: | WU Congcong HE Yichao CHEN Yiying LIU Xuejing CAI Xiufeng |
| |
| Affiliation: | College of Information Engineering, Hebei GEO University, Shijiazhuang Hebei 050031, China |
| |
| 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. |
| |
| Keywords: | Discounted {0-1} Knapsack Problem (D{0-1}KP) Bat Algorithm (BA) differential evolution Lévy flight greedy strategy non-normal coding |
|
| 点击此处可从《计算机应用》浏览原始摘要信息 |
|
点击此处可从《计算机应用》下载全文 |
