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

发布时间：2018-03-10 21:14

本文选题：动态规划　切入点：时间复杂度　出处：《软件学报》2017年02期 　论文类型：期刊论文

【摘要】：随机时变背包问题(randomized time-varying knapsack problem,简称RTVKP)是一种动态背包问题,也是一种动态组合优化问题,目前其求解算法主要是动态规划的精确算法、近似算法和遗传算法.首先,利用动态规划提出了一种求解RTVKP问题的精确算法,对算法时间复杂度的比较结果表明,它比已有的精确算法更适于求解背包载重较大的一类RTVKP实例.然后,分别基于差分演化和粒子群优化与贪心修正策略相结合,提出了求解RTVKP问题的两种进化算法.对5个RTVKP实例的数值计算结果比较表明,精确算法一般不宜求解大规模的RTVKP实例,而基于差分演化、粒子群优化和遗传算法与贪心修正策略相结合的进化算法却不受实例规模与数据大小的影响,对于振荡频率大且具有较大数据的大规模RTVKP实例均能求得一个极好的近似解.
[Abstract]:Random time-varying knapsack problem (RTVKP) is a dynamic knapsack problem and a dynamic combinatorial optimization problem. At present, its solving algorithms are mainly precise algorithm of dynamic programming, approximate algorithm and genetic algorithm. In this paper, an exact algorithm for solving RTVKP problem is proposed by using dynamic programming. The comparison of the time complexity of the algorithm shows that it is more suitable for solving a class of RTVKP cases with large backpack load than the existing exact algorithm. Based on the combination of differential evolution and particle swarm optimization (PSO) and greedy correction strategy, two evolutionary algorithms for solving RTVKP problem are proposed. The numerical results of five RTVKP examples show that the exact algorithm is generally not suitable for solving large-scale RTVKP cases. However, based on differential evolution, the evolutionary algorithm based on particle swarm optimization and genetic algorithm combined with greedy correction strategy is not affected by the size of the instance and the size of the data. An excellent approximate solution can be obtained for large scale RTVKP examples with large oscillation frequency and large data.
【作者单位】：河北地质大学信息工程学院;河北师范大学软件学院;深圳大学计算机与软件学院;河北师范大学数学与信息科学学院;
【基金】：国家自然科学基金(71371063,61170040)~~
【分类号】：TP301.6

【相似文献】