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

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

Exact Algorithms and Evolutionary Algorithms for Randomized Time-Varying Knapsack Problem

The randomized time-varying knapsack problem (RTVKP) is both a new kind of dynamic knapsack problem and a new kind of dynamic combinational optimization problem. Now the exact algorithm base on dynamic programming, approximation algorithms base on greedy-choice strategy and evolutionary algorithm base on genetic algorithm are the main algorithms to solve it. In this paper, we first give a novel exact algorithm base on dynamic programming to solve the RTVKP, and compare the time complexity to the existed exact algorithms. Results show that the algorithm we proposed is more suitable to solve the RTVKP whose profit is larger. Then we combine the Greedy correction and optimization strategy with differential evolution and particle swarm optimization respectively to solve RTVKP. The numerical results of the 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 and owning bigger data.