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

作者：吴聪聪; 贺毅朝; 陈嶷瑛; 刘雪静; 才秀凤

来源：计算机应用, 2017, 37(05): 1292-1299.

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

针对确定性算法难于求解规模大、数据范围广的折扣{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。

• 单位
  河北地质大学