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

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

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.