摘要
为求解多限制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.
出处
《计算机工程》
CAS
CSCD
北大核心
2009年第13期4-7,10,共5页
Computer Engineering
基金
中国科学院知识创新工程重要方向基金资助项目(KZCX2-yw-203-2)
关键词
背包问题
贪心法
遗传算法
不可行解
knapsack problem
greedy algorithm
Genetic Algorithm(GA)
infeasible solution