期刊文献+

求解多限制0-1背包问题的混合遗传算法 被引量:7

Hybrid Genetic Algorithm for Multiconstraint 0-1 Knapsack Problem
下载PDF
导出
摘要 为求解多限制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
  • 相关文献

参考文献3

二级参考文献13

  • 1M Sasaki, M Gen. Methods for the Solution of the Multl-Dimensiioal 0/1 Knapsack Problem[C]. Conference Paper of the Twenty-Ninth Annual Meeting of the Operations Research Society of America in Santa Monica,California, 1966.
  • 2Richard Loulou, Eleftherios Michaelides. New Greedy-like Heuristics for the Multidimensional 0-1 Knapsack Problem[ J ]. Operations Research, 1979, 27(6) : 1101--1114.
  • 3Jochen Thiel , Stefan Voss. Some Experiences on Solving Multiconstraint Zero-one Knapsack Problems with Genetic Algorithms[ J ]. Infor, 1994, 32 (4) : 226--238.
  • 4Goldberg D E, Alleles L R, Loci.The Traveling Salesman Problem.In:Proceedings of an International Conference on Genetic Algorithms and Their Applications, 1985:154-159
  • 5Grefenstette J J, Gopal R, Rosmaita B, et al.Genetic Algorithms for Traveling Salesman Problem.In: Proceedings of an International Conference on Genetic Algorithms and Their Applications, 1985: 160-168
  • 6Davis L.Job Shop Scheduling with Genetic Algorithms.In: Proceedings of International Conference on Genetic Algorithms and Their Applications, 1985:136-140
  • 7Holland J H. Adaptation in Natural and Artifical Systems: An Introductory Analysis with Applications to Biology[M]. [S. l.]: University of Michigan Press, 1975.
  • 8李娟,方平,周明.一种求解背包问题的混合遗传算法[J].南昌航空工业学院学报,1998,12(3):31-35. 被引量:32
  • 9张彤,王宏伟,王子才.变尺度混沌优化方法及其应用[J].控制与决策,1999,14(3):285-288. 被引量:225
  • 10梁艳春,冯大鹏,周春光.遗传算法求解旅行商问题时的基因片段保序[J].系统工程理论与实践,2000,20(4):7-12. 被引量:37

共引文献23

同被引文献65

引证文献7

二级引证文献32

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部