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

摘要：

第一遗传算法(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}背包问题、非正常编码个体、遗传算法、贪心策略、修复与优化

所属期刊栏目：54

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金11371015;四川省教育厅自然科学基金18ZA0469;西华师范大学博士启动基金12B022;西华师范大学校级科研团队CXTD2015-4

在线出版日期：2018-11-28（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：37-42,132