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

被引:12
作者
马丰宁
谢龙
郑重
机构
[1] 天津大学管理学院
关键词
遗传算法; 简单群体; 基因属性保留; 精英保留策略; 背包问题;
D O I
暂无
中图分类号
TP301.6 [算法理论];
学科分类号
摘要
遗传算法是解决大规模背包问题的有效方法,在研究几种有效的遗传算法求解背包问题基础上,注意到遗传算法的进化代数对求解结果的影响大于群体规模,保持基因位数据的有效性,对进化效率有重大影响.提出了基因属性保留遗传算法(attribute gene-reserved genetic algorithm,AGGA),将每一位基因的属性差异,在不同代遗传中加以保留,结合精英保留方法,很好地解决了提前收敛、GA欺骗问题,从很少的群体出发,就可以达到好的结果,实证了AGGA对背包问题的高效性,得到好于参考文献的结果,并构造了150个物体的背包问题实例.
引用
收藏
页码:1020 / 1024
页数:5
相关论文
共 14 条
[1]   求解大规模0-1背包问题的主动进化遗传算法 [J].
史亮 ;
董槐林 ;
王备战 ;
龙飞 .
计算机工程, 2007, (13) :31-33
[2]   求解背包问题的贪心遗传算法及其应用 [J].
贺毅朝 ;
刘坤起 ;
张翠军 ;
张巍 .
计算机工程与设计, 2007, (11) :2655-2657+2681
[3]   求解多维0-1背包问题的一种改进的遗传算法 [J].
曾智 ;
杨小帆 ;
陈静 ;
陈文斌 ;
唐荣旺 .
计算机科学, 2006, (07) :220-223
[4]   求解0-1背包问题的混合遗传算法 [J].
宋海洲 ;
魏旭真 .
华侨大学学报(自然科学版), 2006, (01) :16-19
[5]   0/1背包问题快速降价法及其应用 [J].
宁爱兵 ;
马良 .
系统工程理论方法应用, 2005, (04) :372-375
[6]   背包问题的二分网格算法 [J].
李庆华 ;
潘军 ;
李肯立 .
计算机科学, 2005, (06) :217-220
[7]   不可分离凸背包问题的拉格朗日分解和区域分割方法(英文) [J].
王粉兰 ;
孙小玲 .
运筹学学报, 2004, (04) :45-53
[8]   背包问题的遗传算法求解 [J].
刘西奎 ;
李艳 ;
许进 .
华中科技大学学报(自然科学版), 2002, (06) :89-90
[9]   佳点集遗传算法 [J].
张铃 ;
张钹 .
计算机学报, 2001, (09) :917-922
[10]   基于遗传算法的0/1背包问题求解 [J].
霍红卫,许进,保铮 .
西安电子科技大学学报, 1999, (04) :101-105