变异蝙蝠算法求解折扣{0-1}背包问题
来源：计算机应用杂志2017年第5期北京时间：
作者：吴聪聪, 贺毅朝, 陈嶷瑛, 刘雪静, 才秀凤
单位：河北地质大学 信息工程学院, 石家庄 050031
摘要：针对确定性算法难于求解规模大、数据范围广的折扣{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飞行,贪心策略,非正常编码
基金资助：河北省高等学校科学研究计划项目（ZD2016005）；河北省自然科学基金资助项目（F2016403055）。
