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

摘要：

目前,求解折扣{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}背包问题、遗传算法、非正常编码个体、贪心策略、修复与优化

所属期刊栏目：39

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

资助基金：国家自然科学基金71371063;深圳市科技计划项目JCYJ2015032414-0036825;河北省高等学校科研基金ZD2016005,Z2013110资助.The authors of this paper have conducted the research in evolutionary algorithms and NP-hard problems direction from 2004,and have been supported by the National Natural Science Foundation of China71371063;the Basic Research Project of Knowledge Innovation Program in ShenzhenJCYJ20150324140036825;the University Scientific Research Fund of Hebei ProvinceZD2016005,Z2013110

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

页数：共17页

页码：2614-2630