计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (36): 32-34.DOI: 10.3778/j.issn.1002-8331.2009.36.010

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

求解背包问题的更贪心粒子群算法

赵新超1,杨婷婷2   

  1. 1.北京邮电大学 理学院 数学系,北京 100876
    2.北京邮电大学 信息光子学与光通信研究院,北京 100876
  • 收稿日期:2009-01-05 修回日期:2009-03-13 出版日期:2009-12-21 发布日期:2009-12-21
  • 通讯作者: 赵新超

Very greedy particle swarm optimization algorithm for knapsack problem

ZHAO Xin-chao1,YANG Ting-ting2   

  1. 1.Department of Mathematics,School of Science,Beijing University of Posts and Telecommunications,Beijing 100876,China
    2.Institute of Information Photonics and Optical Communications,Beijing University of Posts and Telecommunications,Beijing 100876,China
  • Received:2009-01-05 Revised:2009-03-13 Online:2009-12-21 Published:2009-12-21
  • Contact: ZHAO Xin-chao

摘要: 将粒子群算法与贪心思想相融合,提出一种用于求解0/1背包问题的更贪心混合粒子群算法。对超过背包重量约束的粒子的处理措施是去掉已经装进去且性价比最差的物品,直至满足重量约束为止,这种思想在改善粒子质量的同时避免了通常罚函数方法中敏感的参数选择问题;对当前可行粒子的处理措施是将还未装入背包且性价比最好的物品装进背包,直至不能装为止。通过与文献中基于经典算例的计算结果比较表明,更贪心粒子群算法无论在寻优能力、计算速度和稳定性方面都超过了文献中提到的混合遗传算法(HGA)、贪心遗传算法(GGA)和混合粒子群算法(GBPSOA)。

Abstract: Combining particle swarm optimization algorithm and greedy idea,a Very Greedy Particle Swarm Optimization algorithm(VGPSO) is proposed for Knapsack Problem(KP).The strategy of dealing the overweight particle is to take out the enclosed and the worst goods in ratio between value and weight,until to satisfy the weight constraint.Simultaneously,the question of sensitive parameter’s choice is avoided under this measure.The strategy of managing the feasible particle is to enclose the goods which is out of knapsack and best in ratio between value and weight,until none goods can be put into.Based on the classic instances in the reference numerical experiments are made and compared with other algorithms.The VGPSO is better than Hybrid Genetic Algorithm(HGA),Greedy Genetic Algorithm(GGA) and Greedy Binary Particle Swarm Optimization Algorithm(GBPSOA) in the ability of finding optimal solution,the efficiency and the robustness.

中图分类号: