基于遗传算法求解折扣{0-1}背包问题的研究

• 作者: 张新禄 李文斌 王熙照 贺毅朝 陈嶷瑛
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 折扣{0-1}背包问题 遗传算法 非正常编码个体 贪心策略 修复与优化
• 年，卷（期）: 2016,（12）
• 所属期刊栏目: 量子计算、计算机理论与算法
• 页码范围: 2614-2630
• 页数: 17页
• 分类号: TP18
• 字数: 13960字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2016.02614

摘要

目前,求解折扣{0-1}背包问题(D{0-1}KP)的主要算法是基于动态规划的具有伪多项式时间的确定性算法,当D{0-1}KP实例中各项的价值系数与重量系数在大范围内取值时缺乏实用性.文中基于杰出者保留策略遗传算法(EGA)求解D{0-1}KP,首先建立了D{0-1}KP的两个新的数学模型;然后,为了利用EGA和第一数学模型求解D{0-1}KP,提出了一种处理非正常编码个体的贪心修复与优化算法GROA,并将其与EGA相结合给出了求解D{0-1}KP的第一遗传算法FirEGA;紧接着,利用EGA和第二数学模型求解D{0-1}KP,提出了处理非正常编码个体的另一种有效算法NROA,并将其与EGA相结合给出了求解D{0-1}KP的第二遗传算法SecEGA;最后,利用四类大规模D{0-1}KP实例,确定了FirEGA和SecEGA的交叉概率与变异概率的合理取值,比较了两个算法的实际求解性能.对四类实例的计算结果表明:FirEGA和SecEGA都非常适于求解大规模的难D{0-1}KP实例,均能够得到一个近似比非常接近于1的近似解,并且FirEGA的平均求解性能比SecEGA的更优.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李文斌	石家庄经济学院网络与信息安全实验室	22	277	8.0	16.0
2	陈嶷瑛	石家庄经济学院信息工程学院	19	262	8.0	16.0
3	贺毅朝	石家庄经济学院信息工程学院	53	677	14.0	25.0
4	张新禄	河北师范大学数学与信息科学学院	14	108	5.0	10.0
5	王熙照	深圳大学计算机与软件学院	7	104	5.0	7.0