求解随机时变背包问题的精确算法与进化算法

被引：15

作者：

贺毅朝 ^{[1
,2
]}

王熙照 ^{[3
]}

李文斌 ^{[1
]}

赵书良 ^{[4
,2
]}

机构：

[1] 河北地质大学信息工程学院

[2] 河北师范大学软件学院

[3] 深圳大学计算机与软件学院

[4] 河北师范大学数学与信息科学学院

来源：

软件学报 | 2017年 / 28卷 / 02期

关键词：

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

D O I：

10.13328/j.cnki.jos.004937

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

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

引用

页码：185 / 202

页数：18

共 28 条

[1] 自适应离散差分进化算法策略的选择 [J].