求解多维背包问题的改进二进制粒子群算法  

Modified Binary Particle Swarm Optimization for Solving Multidimensional Knapsack Problem

作　　者：王志刚[1] 夏慧明[1] 王明刚[1] 郭广寒[2] 

机构地区：[1]南京师范大学泰州学院数学科学与应用学院,江苏泰州225300 [2]哈尔滨理工大学荣成学院,山东威海264300

出　　处：《数学的实践与认识》2013年第19期129-137,共9页Mathematics in Practice and Theory

基　　金：贵州省教育厅科研项目(黔教科2010093);泰州市社会发展计划项目(2011044);江苏省高等学校大学生实践创新训练计划项目(2012JSSPITP3029);南京师范大学泰州学院资助项目(Q201232)

摘　　要：针对二进制粒子群算法在求解大规模多维背包问题时存在迭代次数过多、精度不高的不足,提出一种改进的二进制粒子群算法,新算法利用种群个体极值的平均信息和粒子的个体极值决定粒子当前取值的概率,使粒子可以充分利用整个种群的信息,避免算法陷入局部极值,并利用贪婪算法对进化过程中的不可行解进行修复,对背包资源利用不足的可行解进行修正.通过对典型多维背包问题的仿真实验和与其它算法的比较,表明算法有良好的全局优化能力和较好的收敛速度.Binary particle swarm optimization takes too much time and solves imprecisely for large-scaled multidimensional knapsack problem, a modified binary particle swarm opti- mization is proposed in this paper to overcome this shortcoming. The new algorithm uses the values of the average individual best position and the individual best position depend on the probability of the position vector, makes each particle use the whole swarm information effectively to avoid local optima. During the evolution process, it uses the greedy algorithm repairs the infeasible solution and rectify knapsack resources with insufficient use. Simulated tests of multidimensional knapsack problem and comparisons with other algorithms show the algorithm has strong global optimization ability and a good speed of convergence.

关 键 词：粒子群算法 二进制 平均信息 多维背包问题 贪婪算法 

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