求解多维0-1背包问题的一种改进的遗传算法

被引:15
作者
曾智
杨小帆
陈静
陈文斌
唐荣旺
机构
[1] 重庆大学计算机学院
关键词
多维0-1背包问题; 遗传算法; 中值杂交算子;
D O I
暂无
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
针对多维0-1背包问题,通过应用贪心法和二分搜索法的思想,本文提出了一种新的杂交算子———中值杂交,并且基于此算子提出了求解多维0-1背包问题的一种改进的遗传算法。最后本文通过一系列数值实验,把改进算法与传统的遗传算法以及其他最新的遗传算法进行比较,经过对求得近似解的精度及计算所需时间两方面的对比,验证了其有效性。
引用
收藏
页码:220 / 223
页数:4
相关论文
共 11 条
[1]  
Adaptationin Natural and Artificial SystemsCambridge. Holland J. .
[2]  
Genetic algorithms with double strings for0-1programming problems. Sakawa M,,Kato K. European Journal . 2003
[3]  
Adaptationin Natural and Artificial Systems. Holland J. . 1975
[4]  
The multidi mensional0-1knapsack problem:An o-verview. Freville A. European Journal of Operational Research . 2004
[5]  
Onthe solution of discrete programming problem. Manne A,,Markowitz H. Econometrica . 1957
[6]  
An interactive fuzzy satisficing method for multiobjective multidi mensional0-1knapsack prob-lems through genetic algorithms. Sakawa M,,Kato K,,Shibano T. Proceedings of1996IEEEIn-ternational Conference on Evolutionary Computation,Piscataway . 1996
[7]  
Pivot and Complement-a Heuristic for0-1Programming. Balas E,,Martin C. Management Science . 1980
[8]  
Three problemin capital rationing. Lorie J,,Savage L. Journal of Business . 1955
[9]  
I mproved Crossover Strategy of Genet-ic Algorithms and Analysis of Its Performance. Bian R,,Chen Z,,Yuan Z. Proceedings of the3th world congress on Intelligent Control and Automation . 2000
[10]  
Genetic Algorithmsin Search,Opti mization,and Ma-chine Learning. Goldberg D. . 1989