求解背包问题的基因属性保留遗传算法  

Attribute Gene-Reserved Genetic Algorithm for Solving Knapsack Problem

作　　者：马丰宁[1] 谢龙[1] 郑重[1] 

机构地区：[1]天津大学管理学院,天津300072

出　　处：《天津大学学报》2010年第11期1020-1024,共5页Journal of Tianjin University(Science and Technology)

基　　金：国家自然科学基金资助项目(70571057)

摘　　要：遗传算法是解决大规模背包问题的有效方法,在研究几种有效的遗传算法求解背包问题基础上,注意到遗传算法的进化代数对求解结果的影响大于群体规模,保持基因位数据的有效性,对进化效率有重大影响.提出了基因属性保留遗传算法(attribute gene-reserved genetic algorithm,AGGA),将每一位基因的属性差异,在不同代遗传中加以保留,结合精英保留方法,很好地解决了提前收敛、GA欺骗问题,从很少的群体出发,就可以达到好的结果,实证了AGGA对背包问题的高效性,得到好于参考文献的结果,并构造了150个物体的背包问题实例.The genetic algorithm is an effective means to solve the large-scale knapsack problem.By studying several effective genetic algorithms,we find that the evolutional algebra of genetic algorithm has much more impact on optimal results than population size does.In addition,maintaining the effectiveness of gene-bit data also has a significant impact on the efficiency of evolution.In this paper,we propose the attribute genereserved genetic algorithm（AGGA）,which,combined with the genetic algorithm of elitist strategy,can reserve the difference of each gene-bit data attribute in genetics of different generations,and easily solve the early convergence and GA deceptive problem.Just from a very small number of groups,we can finally achieve good results,justify the high efficiency of improved algorithm and gain a calculation result better than the ones in relevant references.Then we construct a calculation example which contains 150 backpacks.

关 键 词：遗传算法 简单群体 基因属性保留 精英保留策略 背包问题 

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