格雷码混合遗传算法求解0-1背包问题  

Gray coded hybrid genetic algorithm for 0-1 knapsack problem

作　　者：王则林[1] 吴志健[2] 

机构地区：[1]南通大学计算机科学与技术学院,江苏南通226000 [2]武汉大学软件工程国家重点实验室,武汉4300072

出　　处：《计算机应用研究》2012年第8期2906-2908,共3页Application Research of Computers

基　　金：国家自然科学基金资助项目(61070008);国家教育部人文社科基金资助项目(11YJC870012);江西省教育厅科技项目(GJJ11106)

摘　　要：给出0-1背包问题的数学模型,修改传统二进制编码为格雷码混合遗传算法,使用贪心算法来解决约束问题,对每个个体使用价值密度来衡量,提高了算法搜索效率,同时使用精英保留机制来加速算法收敛的速度。最后通过数值实验证明了算法的有效性。This paper gave an athematic mode of 0-1 knapsack problem, and modified the binary coding to establish a gray coded hybrid genetic algorithm used greedy algorithm to handle with the constraint conditions, And this paper proposed a value density operator to the individual,which could improve the search effciency, used the elitism mechanism to accelerate the convergence process. The numerical experiment proves the affectivity of the algorithm.

关 键 词：遗传算法 背包问题 格雷码 贪心算法 精英保留机制 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]