作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2006, Vol. 32 ›› Issue (18): 23-24,3. doi: 10.3969/j.issn.1000-3428.2006.18.009

• 博士论文 • 上一篇    下一篇

基于改进的微粒群优化算法的0-1背包问题求解

沈显君1,2,王伟武1,郑波尽1,李元香1   

  1. (1.武汉大学软件工程国家重点实验室,武汉 430072;2. 华中师范大学计算机科学系,武汉 430079)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2006-09-20 发布日期:2006-09-20

Modified Particle Swarm Optimization for 0-1 Knapsack Problems

SHEN Xianjun1,2, WANG Weiwu1, ZHENG Bojin1, LI Yuanxiang1   

  1. (1. State Key Laboratory of Software Engineering, Wuhan University, Wuhan 430072; 2. Department of Computer Science, Central China Normal University, Wuhan 430079)
  • Received:1900-01-01 Revised:1900-01-01 Online:2006-09-20 Published:2006-09-20

摘要: 在介绍微粒群优化算法及其搜索策略的基础上,根据组合约束优化问题的特点,定义了等值变换、异值变换以及变换序列等概念,有针对性地设计了一种适合求解0-1背包问题的特殊微粒群优化算法。实验证明,改进后的微粒群优化算法在求解0-1背包问题上具有可行性和高效性。

关键词: 微粒群优化, 0-1背包问题, 组合约束优化

Abstract: The algorithm and the search strategies of particle swarm optimization are introduced, on base of which concepts such as equivalent transformation, the difference value transformation and the transform serial sequence are defined according to characteristics of 0-1 knapsack problem, then a kind of special particle swarm optimization that is applicable to solve 0-1 knapsack problem is designed. The experimental results show the possibility and the efficiency of the modified particle swarm optimization on solving 0-1 knapsack problem.


Key words: Particle swarm optimization, 0-1 knapsack problem, Constrained combinatorial optimization