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

摘要

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