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

来源：软件学报杂志2017年第2期北京时间：

作者：贺毅朝,王熙照,李文斌,赵书良

单位：贺毅朝，河北地质大学 信息工程学院, 河北 石家庄 050031;河北师范大学 软件学院, 河北 石家庄 05002411,王熙照，深圳大学 计算机与软件学院, 广东 深圳 51806002,李文斌，河北地质大学 信息工程学院, 河北 石家庄 05003103,赵书良，河北师范大学 数学与信息科学学院, 河北 石家庄 050024;河北师范大学 软件学院, 河北 石家庄 05002404

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

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

基金资助：国家自然科学基金（71371063，61170040）