| 基于离散微粒群算法求解背包问题研究 |
| |
| 引用本文： | 刘建芹,贺毅朝,顾茜茜.基于离散微粒群算法求解背包问题研究[J].计算机工程与设计,2007,28(13):3189-3191,3204. |
| |
| 作者姓名： | 刘建芹 贺毅朝 顾茜茜 |
| |
| 作者单位： | 1. 石家庄信息工程职业学院,河北,石家庄,050035
2. 石家庄经济学院,信息工程系,河北,石家庄,050031 |
| |
| 基金项目： | 河北省科技攻关项目
,
河北省教育厅科研项目 |
| |
| 摘 要： | 微粒群算法(PSO)是一种新的演化算法,主要用于求解数值优化问题.基于离散微粒群算法(DPSO)分别与处理约束问题的罚函数法和贪心变换方法相结合,提出了求解背包问题的两个算法:基于罚函数策略的离散微粒群算法(PFDPSO)和基于贪心变换策略的离散微粒群算法(GDPSO).通过将这两个算法与文献7]中的混合微粒群算法(Hybrid_PSO)进行数值计算比较发现:对于求解大规模的背包问题,GDPSO非常优秀,其求解能力优于Hybrid_PSO和PFDPSO,是求解背包问题的一种非常有效的方法.
|
| 关 键 词： | 微粒群算法 背包问题 贪心变换法 罚函数法 遗传算法 离散微粒群算法 求解 背包问题 研究 particle swarm optimization discrete based 变换方法 能力 大规模 发现 比较 数值计算 混合 文献 罚函数策略 结合 罚函数法 约束问题 处理 |
| 文章编号： | 1000-7024（2007）13-3189-03 |
| 修稿时间： | 2006-10-19 |
Solving knapsack problem based on discrete particle swarm optimization |
| |
| LIU Jian-qin,HE Yi-chao,GU Qian-qian.Solving knapsack problem based on discrete particle swarm optimization[J].Computer Engineering and Design,2007,28(13):3189-3191,3204. |
| |
| Authors: | LIU Jian-qin HE Yi-chao GU Qian-qian |
| |
| Affiliation: | 1, Shijiazhuang Information Engineering Vocational College, Shijiazhuang 050035, China; 2. Department of Information Project, Shijiazhuang University of Economics, Shijiazhuang 050031, China |
| |
| Abstract: | 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. |
| |
| Keywords: | particle swarm optimization knapsack problem greedy transform method penalty function method genetic algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
