| 本文已被：浏览 4879次 下载 6844次 |
码上扫一扫！ |
|
|
| 求解随机时变背包问题的精确算法与进化算法 |
|
贺毅朝1,2, 王熙照3, 李文斌1, 赵书良4,2
|
|
1.河北地质大学 信息工程学院, 河北 石家庄 050031;2.河北师范大学 软件学院, 河北 石家庄 050024;3.深圳大学 计算机与软件学院, 广东 深圳 518060;4.河北师范大学 数学与信息科学学院, 河北 石家庄 050024
|
|
| 摘要: |
| 随机时变背包问题（randomized time-varying knapsack problem，简称RTVKP）是一种动态背包问题，也是一种动态组合优化问题，目前其求解算法主要是动态规划的精确算法、近似算法和遗传算法.首先，利用动态规划提出了一种求解RTVKP问题的精确算法，对算法时间复杂度的比较结果表明，它比已有的精确算法更适于求解背包载重较大的一类RTVKP实例.然后，分别基于差分演化和粒子群优化与贪心修正策略相结合，提出了求解RTVKP问题的两种进化算法.对5个RTVKP实例的数值计算结果比较表明，精确算法一般不宜求解大规模的RTVKP实例，而基于差分演化、粒子群优化和遗传算法与贪心修正策略相结合的进化算法却不受实例规模与数据大小的影响，对于振荡频率大且具有较大数据的大规模RTVKP实例均能求得一个极好的近似解. |
| 关键词: 动态规划 时间复杂度 差分演化 粒子群优化 修复方法 |
| DOI：10.13328/j.cnki.jos.004937 |
| 分类号: |
| 基金项目:国家自然科学基金（71371063，61170040） |
|
| Exact Algorithms and Evolutionary Algorithms for Randomized Time-Varying Knapsack Problem |
|
HE Yi-Chao1,2, WANG Xi-Zhao3, LI Wen-Bin1, ZHAO Shu-Liang4,2
|
|
1.College of Information and Engineering, Hebei GEO University, Shijiazhuang 050031, China;2.Software College, Hebei Normal University, Shijiazhuang 050024, China;3.College of Computer Science and Software Engineering, Shenzhen University, Shenzhen 518060, China;4.College of Mathematics and Information Science, Hebei Normal University, Shijiazhuang 050024, China
|
| 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. |
| Key words: dynamic programming time complexity differential evolution particle swarm optimization repair approach |
