一种求解集合组合问题的离散粒子群优化模型  

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

作　　者：陈自郁[1] 何中市[1] 何静媛[1] 

机构地区：[1]重庆大学计算机学院,重庆400030

出　　处：《华南理工大学学报（自然科学版）》2010年第4期141-146,共6页Journal of South China University of Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(30771446);国家"863"计划项目(2007AA01Z423);国家重大专项项目(2008ZX07315-001);重庆市自然科学基金资助项目(2007BB2134)

摘　　要：针对变长集合组合优化问题,提出了一种离散粒子群优化模型.该模型将集合的概念和运算引入粒子群优化中,定义了一个可变集合搜索空间,并重新定义了粒子的位置、速度及作用于此空间的运算规则,既保留了粒子群本身的优化特性,又体现了集合组合优化的特点.采用典型的变长集合组合优化问题——背包问题来验证此模型的性能,并与二进制粒子群优化(BPSO)算法进行了对比.结果表明,该模型具有较强的寻优能力和更高的稳定性.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.

关 键 词：集合 组合优化 离散粒子群优化 背包问题 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]