改进离散粒子群优化算法求解广义指派问题  

Solving Generalized Assignment Problem Based on Improved Discrete Particle Swarm Optimization

作　　者：王一川[1] 单甘霖[1] 童俊[1] 

机构地区：[1]军械工程学院电子与光学工程系,石家庄050003

出　　处：《科技通报》2013年第8期130-132,共3页Bulletin of Science and Technology

基　　金：军内科研资助项目

摘　　要：广义指派问题是典型的NP-hard组合优化问题。对一类广义指派问题进行了建模,提出了一种基于连续空间的改进离散粒子群优化算法以求解该模型。算法针对问题设计了特定的粒子编码方案,引入了局部搜索以改进算法性能。数值仿真表明了所提离散粒子群优化算法求解广义指派问题的可行性。Generalized assignment problem is a typical NP-hard problem in combinatorial optimization. Model for a class of generalized assignment problem is build up, and an improved discrete particle swarm optimization algorithm based on continuous space is proposed to solve this model. The algorithm designs a specific particle coding scheme based on the problem, introduces local search to increase performance. The simulation shows that the proposed algorithm is feasible in solving generalized assignment problem.

关 键 词：广义指派问题 粒子群优化算法 粒子编码 局部搜索 

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