基于离散微粒群算法求解背包问题研究  

Solving knapsack problem based on discrete particle swarm optimization

作　　者：刘建芹[1] 贺毅朝[2] 顾茜茜[2] 

机构地区：[1]石家庄信息工程职业学院,河北石家庄050035 [2]石家庄经济学院信息工程系,河北石家庄050031

出　　处：《计算机工程与设计》2007年第13期3189-3191,3204,共4页Computer Engineering and Design

基　　金：河北省科技攻关基金项目(05213567);河北省教育厅科技基金项目(2005338)

摘　　要：微粒群算法(PSO)是一种新的演化算法,主要用于求解数值优化问题。基于离散微粒群算法(DPSO)分别与处理约束问题的罚函数法和贪心变换方法相结合,提出了求解背包问题的两个算法:基于罚函数策略的离散微粒群算法(PFDPSO)和基于贪心变换策略的离散微粒群算法(GDPSO)。通过将这两个算法与文献[7]中的混合微粒群算法(Hybrid_PSO)进行数值计算比较发现:对于求解大规模的背包问题,GDPSO非常优秀,其求解能力优于Hybrid_PSO和PFDPSO,是求解背包问题的一种非常有效的方法。Particle swarm optimization （PSO） is a new evolutionary algorithm. Numerical optimization is the primary field of PSO applications. Combining discrete particle swarm optimization （DPSO） with penalty function method and greedy transform method, two new algorithms is proposed for solving Knapsack problem （KP）： Discrete particle swarm optimization based on penalty function strategy （PFDPSO） and greedy discrete particle swarm optimization （GDPSO）. PFDPSO and GDPSO are compared with hybrid particle swarm optimization （Hybrid_PSO） in Ref. [7]. The numerical results show that GDPSO is most excellent for solving knapsack problem, The ability in solving KP of GDPSO exceeds Hybrid_PSO. But PFDPSO is more inefficient, These indicate that it is more efficient and practical method that DPSO combines with greedy transform method for solving knapsack problem.

关 键 词：微粒群算法 背包问题 贪心变换法 罚函数法 遗传算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]