Journal of South China University of Technology (Natural Science Edition) ›› 2010, Vol. 38 ›› Issue (4): 141-146.doi: 10.3969/j.issn.1000-565X.2010.04.026

• Computer Science & Technology • Previous Articles     Next Articles

Discrete Particle Swarm Optimization Model for Set-Based Combinatorial Optimization Problems

Chen Zi-yu  He Zhong-shi  He Jing-yuan   

  1. College of Computer Science,Chongqing University,Chongqing 400030,China
  • Received:2009-02-12 Revised:2009-10-15 Online:2010-04-25 Published:2010-04-25
  • Contact: 陈自郁（1976-），女，博士，讲师，主要从事计算智能、机器学习研究． E-mail:chenziyu@cqu．edu．cn
  • About author:陈自郁（1976-），女，博士，讲师，主要从事计算智能、机器学习研究．
  • Supported by:

    国家自然科学基金资助项目（30771446）; 国家“863”计划项目（2007AA01Z423）; 国家重大专项项目（2008ZX07315-001）; 重庆市自然科学基金资助项目（2007BB2134）

PDF

838

Abstract:

Proposed in this paper is a discrete particle swarm optimization model to solve set-based combinatorial optimization problems.The model introduces set concepts and operations in the particle swarm optimization,defines a search space of variable set and redefines the velocity and location of particles as well as the operators working in the defined search space.Thus,it possesses the characteristics of both particle swarm optimization and set-based combinatorial optimization.Finally,the proposed model is applied to the knapsack problem,a typical set-based combinatorial optimization problem,and it is compared with the binary particle swarm optimization（BPSO）.The results indicate that the proposed model is of stronger searching ability and higher stability.

Key words: set, combinatorial optimization, discrete particle swarm optimization, knapsack problem