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

简介：
本文探讨了一种改进的修复策略遗传算法，旨在有效解决具有折扣机制的{0-1}背包问题，通过优化搜索过程提高解的质量和效率。 在求解折扣{0-1}背包问题（D{0-1}KP）过程中，第一遗传算法（FirEGA）未能有效利用物品的折扣关系来修复非正常编码，这影响了修复效果并导致结果不理想。为解决这一问题，对FirEGA中的贪心修复与优化算法（GROA）进行了修正：传统方法依据价值密度选取项，在出现同一集合内两个项均被选中时，不再选择价值密度较高的项而是选择总价值更高的项。由此得到新的处理非正常编码个体的贪心修复优化算法（NGROA）。在FirEGA中引入了NGROA后形成了求解D{0-1}KP的新一代第一遗传算法（NFirEGA）。通过利用NFirEGA解决四类大规模D{0-1}KP问题，结果显示NFirEGA在求解精度上显著优于原有的FirEGA。