改进修复策略遗传算法求解折扣{0-1}背包问题

来源：计算机工程与应用杂志2018年第21期北京时间：

作者：杨 洋1，潘大志1，贺毅朝2

单位：1.西华师范大学 数学与信息学院，四川 南充 637009；2.河北地质大学 信息工程学院，石家庄 050031

摘要：第一遗传算法（FirEGA）在求解折扣{0-1}背包问题（D{0-1}KP）过程中对非正常编码的修复未能较好运用物品折扣关系，影响修复效果，导致求解结果不理想。针对该问题，对FirEGA中的贪心修复与优化算法（GROA）进行修正：传统贪心修复按照价值密度对项进行选取，当出现同一项集中两个项均被选取时，文中不再选取价值密度较大项，而是选择价值较大项，得到处理非正常编码个体的新的贪心修复优化算法（NGROA）。在FirEGA中采用NGROA，构成求解D{0-1}KP新的第一遗传算法（NFirEGA）。最后，利用NFirEGA求解四类大规模D{0-1}KP问题，结果表明，NFirEGA在求解精度上明显优于FirEGA。

关键词：折扣{0-1}背包问题,非正常编码个体,遗传算法,贪心策略,修复与优化