论文研究 改进修复策略遗传算法求解折扣{0 1}背包问题.pdf

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