文献类型：期刊文章

作　　者：贺毅朝[1,2] 王熙照[3] 李文斌[1] 赵书良[4,2]

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

出　　处：《软件学报》

基　　金：国家自然科学基金(71371063;61170040)~~

年　　份：2017

卷　　号：28

期　　号：2

起止页码：185-202

语　　种：中文

收录情况：AJ、BDHX、BDHX2014、CSA、CSA-PROQEUST、CSCD、CSCD2017_2018、EI(收录号：20171003422173)、IC、INSPEC、JST、MR、RCCSE、SCOPUS、ZGKJHX、ZMATH、核心刊

摘　　要：随机时变背包问题(randomized time-varying knapsack problem,简称RTVKP)是一种动态背包问题,也是一种动态组合优化问题,目前其求解算法主要是动态规划的精确算法、近似算法和遗传算法.首先,利用动态规划提出了一种求解RTVKP问题的精确算法,对算法时间复杂度的比较结果表明,它比已有的精确算法更适于求解背包载重较大的一类RTVKP实例.然后,分别基于差分演化和粒子群优化与贪心修正策略相结合,提出了求解RTVKP问题的两种进化算法.对5个RTVKP实例的数值计算结果比较表明,精确算法一般不宜求解大规模的RTVKP实例,而基于差分演化、粒子群优化和遗传算法与贪心修正策略相结合的进化算法却不受实例规模与数据大小的影响,对于振荡频率大且具有较大数据的大规模RTVKP实例均能求得一个极好的近似解.

关 键 词：动态规划 时间复杂度 差分演化 粒子群优化 修复方法  

分 类 号：TP301]