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

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

Very greedy particle swarm optimization algorithm for knapsack problem

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.