文献类型：期刊文章

作　　者：贺毅朝[1] 王熙照[2] 李文斌[3] 张新禄[4] 陈嶷瑛[1]

HE Yi-Chao;WANG Xi-Zhao;LI Wen-Bin;ZHANG Xin-Lu;CHEN Yi-Ying(College of Information Engineering,Shijiazhuang University of Economics,Shijiazhuang 050031;College of Computer Science and Software Engineering,Shenzhen University,Shenzhen,Guangdong 518060;Laboratory of Network and Information Security.Shijiazhuang University of Economics,Shijiazhuang 050031;College of Mathematics and Information Science,Hebei Normal University,Shijiazhuang 050024)

机构地区：[1]石家庄经济学院信息工程学院,石家庄050031 [2]深圳大学计算机与软件学院,广东深圳518060 [3]石家庄经济学院网络与信息安全实验室,石家庄050031 [4]河北师范大学数学与信息科学学院,石家庄050024

出　　处：《计算机学报》

基　　金：国家自然科学基金(71371063);深圳市科技计划项目(JCYJ2015032414-0036825);河北省高等学校科研基金(ZD2016005;Z2013110)资助

年　　份：2016

卷　　号：39

期　　号：12

起止页码：2614-2630

语　　种：中文

收录情况：BDHX、BDHX2014、CSA、CSA-PROQEUST、CSCD、CSCD2015_2016、EI(收录号：20165203163178)、IC、JST、MR、RCCSE、SCOPUS、ZGKJHX、核心刊

摘　　要：目前,求解折扣{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]