###
Journal of Software:2017.28(2):185-202

求解随机时变背包问题的精确算法与进化算法
贺毅朝,王熙照,李文斌,赵书良
(河北地质大学 信息工程学院, 河北 石家庄 050031;河北师范大学 软件学院, 河北 石家庄 050024;深圳大学 计算机与软件学院, 广东 深圳 518060;河北师范大学 数学与信息科学学院, 河北 石家庄 050024;河北师范大学 软件学院, 河北 石家庄 050024)
Exact Algorithms and Evolutionary Algorithms for Randomized Time-Varying Knapsack Problem
HE Yi-Chao,WANG Xi-Zhao,LI Wen-Bin,ZHAO Shu-Liang
(College of Information and Engineering, Hebei GEO University, Shijiazhuang 050031, China;Software College, Hebei Normal University, Shijiazhuang 050024, China;College of Computer Science and Software Engineering, Shenzhen University, Shenzhen 518060, China;College of Mathematics and Information Science, Hebei Normal University, Shijiazhuang 050024, China;Software College, Hebei Normal University, Shijiazhuang 050024, China)
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 2690   Download 1675
Received:August 04, 2014    Revised:January 21, 2015
> 中文摘要: 随机时变背包问题(randomized time-varying knapsack problem,简称RTVKP)是一种动态背包问题,也是一种动态组合优化问题,目前其求解算法主要是动态规划的精确算法、近似算法和遗传算法.首先,利用动态规划提出了一种求解RTVKP问题的精确算法,对算法时间复杂度的比较结果表明,它比已有的精确算法更适于求解背包载重较大的一类RTVKP实例.然后,分别基于差分演化和粒子群优化与贪心修正策略相结合,提出了求解RTVKP问题的两种进化算法.对5个RTVKP实例的数值计算结果比较表明,精确算法一般不宜求解大规模的RTVKP实例,而基于差分演化、粒子群优化和遗传算法与贪心修正策略相结合的进化算法却不受实例规模与数据大小的影响,对于振荡频率大且具有较大数据的大规模RTVKP实例均能求得一个极好的近似解.
Abstract:The randomized time-varying knapsack problem (RTVKP) is both a kind of dynamic knapsack problem and a kind of dynamic combinational optimization problem. Currently, the leading algorithms for solving RTVKP include the exact algorithm base on dynamic programming, approximation algorithm base on greedy-choice strategy and evolutionary algorithm base on genetic algorithm. First, in this paper, an exact algorithm base on dynamic programming to solve RTVKP is presented, along with comparison of its time complexity with the existing exact algorithms. Results show that the proposed algorithm is more suitable to solve RTVKP whose profit is larger. Then, the greedy correction and optimization strategy is combined with differential evolution and particle swarm optimization respectively to solve RTVKP. The numerical results on 5 instances of RTVKP show that the evolutionary algorithms which combine the differential evolution, particle swarm optimization and genetic algorithm with Greedy correction and optimization strategy respectively are more suitable to solve the hard RTVKP whose scale and oscillation frequency are larger while having bigger data.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(71371063,61170040) 国家自然科学基金(71371063,61170040)
Foundation items:National Natural Science Foundation of China (71371063, 61170040)
Reference text:

贺毅朝,王熙照,李文斌,赵书良.求解随机时变背包问题的精确算法与进化算法.软件学报,2017,28(2):185-202

HE Yi-Chao,WANG Xi-Zhao,LI Wen-Bin,ZHAO Shu-Liang.Exact Algorithms and Evolutionary Algorithms for Randomized Time-Varying Knapsack Problem.Journal of Software,2017,28(2):185-202