求解多限制0-1背包问题的混合遗传算法  

Hybrid Genetic Algorithm for Multiconstraint 0-1 Knapsack Problem

作　　者：宋海生[1,2,3] 宋海洲[4] 傅仁毅[1] 徐瑞松[2] 

机构地区：[1]顺德职业技术学院计算机技术系,佛山528300 [2]中国科学院广州地球化学研究所,广州510640 [3]中国科学院研究生院,北京100049 [4]华侨大学数学科学学院,泉州362021

出　　处：《计算机工程》2009年第13期4-7,10,共5页Computer Engineering

基　　金：中国科学院知识创新工程重要方向基金资助项目(KZCX2-yw-203-2)

摘　　要：为求解多限制0-1背包问题,设计一种新的价值密度,提出一种基于贪心法的混合遗传算法,采用二进制编码对适应值进行升序排列,并运用轮盘赌选择方法对背包资源利用不足的可行解进行修正处理,对不可行解进行修复处理,并将其与传统遗传算法进行比较。实验结果表明,该算法能够有效提高问题求解的速度和精度,具有一定优越性。In order to solve multi-constraint 0-1 knapsack problem, a new profit-density is designed, on basis of which, a Hybrid Genetic Algorithm（HGA） based on greedy algorithm is proposed, which uses the binary code to amend the feasible solution, and applies roulette wheel selection method to rectify knapsack resources with insufficient use, and repairs the infeasible solution. The algorithm is compared with other traditional ones. Experimental results show this HGA can promote the speed and accuracy of solving relevant problems efficiently, and is superior.

关 键 词：背包问题 贪心法 遗传算法 不可行解 

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