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

• 作者: 李文斌 王熙照 贺毅朝 赵书良
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 动态规划 时间复杂度 差分演化 粒子群优化 修复方法
• 年，卷（期）: 2017,（2）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 185-202
• 页数: 18页
• 分类号: TP301
• 字数: 14273字
• 语种: 中文
• DOI: 10.13328/j.cnki.j0s.004937

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵书良	河北师范大学数学与信息科学学院	39	312	10.0	16.0
5	李文斌	河北地质大学信息工程学院	22	42	4.0	5.0
6	贺毅朝	河北地质大学信息工程学院	22	110	6.0	9.0
8	王熙照	深圳大学计算机与软件学院	7	104	5.0	7.0