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

• 作者: 杨洋 潘大志 贺毅朝
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 折扣{0-1}背包问题 非正常编码个体 遗传算法 贪心策略 修复与优化
• 年，卷（期）: 2018,（21）
• 所属期刊栏目: 理论与研发
• 页码范围: 37-42,132
• 页数: 7页
• 分类号: TP18
• 字数: 5063字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1711-0255

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	潘大志	西华师范大学数学与信息学院	50	194	9.0	11.0
2	杨洋	西华师范大学数学与信息学院	19	32	4.0	5.0
3	贺毅朝	河北地质大学信息工程学院	22	110	6.0	9.0