一种求解动态背包问题的离散粒子群优化算法

摘要

动态背包问题(DKP)是一类经典的动态优化问题,可以用来描述许多实际的问题.迄今为止,针对动态背包问题的研究主要集中在遗传算法上,而对粒子群优化算法的研究较少.在离散粒子群优化模型的基础上,引入环境变化的探测以及环境变化后的响应机制,提出一种求解动态背包问题的离散粒子群优化算法(DSDPSO).将该算法和现有经典的自适应原对偶遗传算法(APDGA)在两个动态背包问题上进行了对比实验,结果表明,DSDPSO算法在环境变化后能迅速地找到最优解并稳定下来,更适合于求解动态背包问题.%Dynamic knapsack problem (DKP) is a kind of classic dynamic optimization problems , which can be used to describe many practical issues. So far the study of dynamic knapsack problem has mainly focused on genetic algorithm, and particle swarm optimization algorithm is of rare application. This paper proposed a discrete particle swarm optimization algorithm based on discrete particle swarm optimization model for solving dynamic knapsack problem (DSDPSO), and introduced environment change detection and post-change response mechanism. Our algorithm was compared with the existing classical adaptive primal-dual genetic algorithm(APDGA) into two dynamic knapsack problems , and the results show that the DSDPSO algorithm can rapidly find the optimal solution and remains stable after environment variation* Consequently, this algorithm is more suitable to solve dynamic knapsack problem.