混合粒子群算法求解多维背包问题  

Solving multidimensional 0-1 knapsack problem by hybrid particle swarm optimization algorithm

作　　者：王志刚[1] 郝志峰[1] 黄翰[2] 

机构地区：[1]华南理工大学数学科学学院,广州510640 [2]华南理工大学计算机科学与工程学院,广州510640

出　　处：《哈尔滨商业大学学报（自然科学版）》2008年第2期250-253,共4页Journal of Harbin University of Commerce：Natural Sciences Edition

摘　　要：提出了一种求解多维0-1背包问题的混合粒子群算法,算法使用了两个主要的思想策略,即依据物品单位容积价值的高低选择物品的贪婪策略和基于二进制编码的粒子群算法.用提出的算法,对55个测试算例进行了测试,得到了全部算例的最优解.测试结果表明,提出的混合粒子群算法求解多维0-1背包问题,计算结果的优度高,时间短,是求解此问题的有效算法.Proposes a hybrid particle swarm optimization algorithm to solve multidimensional 0 -1 knapsack problem. The algorithm utilizes two important strategies, how to select the item based on its average value and the binary particle swarm optimization algorithm,55 multidimensional 0 -1 knapsack test instances are tested by the produced algorithm, all instances achieve optimum solutions. The integrated performance of the produced algorithm is rather satisfied, and the runtime is short. Experimental results demonstrate the hybrid particle swarm optimization algorithm is rather efficient for solving multidimensional 0 - 1 knapsack problem.

关 键 词：背包问题 粒子群算法 贪婪法 二进制 拟人算法 

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