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

摘要：

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

关键词：背包问题、粒子群算法、更贪心思想

所属期刊栏目：45

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金the National Natural Science Foundation of China under Grant 10826048;中科院数学机械化重点实验室开放课题the Open Fund of KLMM0801from Chinese Academy of Sciences;中央高校基本科研业务费资助2009RC0701

在线出版日期：2010-03-02（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：32-34