计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (36): 73-75.

• 研究、探讨 • 上一篇    下一篇

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

钟培华,吴志远,缪建群   

  1. 江西农业大学 理学院,南昌 330045
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-12-21 发布日期:2011-12-21

Partition particle swarm optimization algorithm for multi-dimensional knapsack problem

ZHONG Peihua,WU Zhiyuan,MIAO Jianqun   

  1. School of Science,Jiangxi Agricultural University,Nanchang 330045,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-12-21 Published:2011-12-21

摘要: 为克服离散粒子群算法早熟的缺陷,通过引入区域分割算法后,移除了解空间中一些无希望的点集,缩小了解的搜索空间,提高了找到最优解的概率,并通过贪心策略对产生的粒子进行了修复和改进,克服了离散粒子群算法收敛慢的缺点。对典型多维背包问题的仿真实验表明,区域分割粒子群算法寻优能力更强,收敛更快。

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

Abstract: 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.

Key words: multi-dimensional knapsack problem, discrete particle swarm optimization, partition