基于遗传算法求解折扣_0_1_背包问题的研究_贺毅朝精选.pdfVIP

网络出版时间：2015-11-18 13:32:16 网络出版地址：/kcms/detail/11.1826.TP1332.006.html 第38 卷 计 算 机 学 报 Vol.38 2015 论文在线出版号 No.133 CHINESE JOURNAL OF COMPUTERS Online Publishing No.133 基于遗传算法求解折扣{0-1}背包问题的研究 1) 2) 3) 4) 1) 贺毅朝 王熙照 李文斌 张新禄 陈嶷瑛 1)(石家庄经济学院 信息工程学院, 石家庄 050031) 2)(深圳大学 计算机与软件学院, 深圳 518060) 3)(石家庄经济学院 网络与信息安全实验室, 石家庄 050031) 4)(河北师范大学 数学与信息科学学院, 石家庄050024) 摘 要 目前，求解折扣{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 的更优。 关键词 折扣{0-1}背包问题；遗传算法；非正常编码个体；贪心策略；修复与优化 中图法分类号TP18 论文引用格式 贺毅朝，王熙照，李文斌，张新禄，陈嶷瑛，基于遗传算法求解折扣{0-1}背包问题的研究，2015 ，Vol.38 ：在线出版号No.133 HE Yi-Chao ,WANG Xi-Zhao ,LI Win-Bin , ZHANG Xin-Lu , CHEN Yi-Ying ，Research on Genetic Algorithms for the Discounted {0-1} Knapsack Problem, Chinese Journal of Computers,2015, Vol.38: Online Publishing No.133 Research on Genetic Algorithms for the Discounted {0-1} Knapsack Problem HE Yi-Chao1) WANG Xi-Zhao2) LI Win-Bin3) ZHANG Xin-Lu4) CHEN Yi