区域分割粒子群算法及多维背包问题求解  

Partition particle swarm optimization algorithm for multi-dimensional knapsack problem

作　　者：钟培华[1] 吴志远[1] 缪建群[1] 

机构地区：[1]江西农业大学理学院

出　　处：《计算机工程与应用》2011年第36期73-75,85,共4页Computer Engineering and Applications

基　　金：江西农业大学青年基金(No.1574)

摘　　要：为克服离散粒子群算法早熟的缺陷,通过引入区域分割算法后,移除了解空间中一些无希望的点集,缩小了解的搜索空间,提高了找到最优解的概率,并通过贪心策略对产生的粒子进行了修复和改进,克服了离散粒子群算法收敛慢的缺点。对典型多维背包问题的仿真实验表明,区域分割粒子群算法寻优能力更强,收敛更快。In order to overcome the premature convergence of discrete particle swarm optimi-zation（BPSO）,a novel partition particle swarm optimization algorithm is proposed.With the partition method combined and some helpless points removed,the searching field of optimal solution is narrowed,and the probability of finding optimal solution enhances.To overcome the slow convergence of BPSO,the greedy method is used for a remedy to infeasible solutions and feasible solutions.Simulation results on benchmark problems show that the proposed algorithm is effective and has faster convergence speed and stronger global optimization ability.

关 键 词：多维背包问题 离散粒子群算法 分割 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]