期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

蚁群算法求解多维0/1背包问题 被引量：1

The Ant Colony Algorithm for Solving the Multidimensional 0/1 Knapsack Problem
在线阅读 下载PDF
导出
摘要 0/1背包问题是一类典型的组合优化问题,并且是NP-完全的问题,研究它具有很重要的意义。本文针对多维0/1背包问题的特点,设计了二进制编码的有向图,使得蚁群算法可以应用到背包问题上。仿真结果表明,该蚁群算法在求解多维0/1背包问题上的是相当出色的。 The 0/1 Knapsack Problem is of a class of typical combinatorial optimization problems and is NP-complete. It has important meanings to study it. Aiming at the characteristics of the multidimensional 0/1 knapsack problem, a binary coding directed graph is designed, which makes the ant colony algorithm suitable for the Knapsack Problem. The simulation results show that the Ant Colony Algorithm is very excellent in solving the multidimensional 0/1 knapsack problem.
作者 熊伟清 魏平 王小权
机构地区 宁波大学计算机科学与技术研究所
出处 《计算机工程与科学》 CSCD 2006年第10期78-79,86,共3页 Computer Engineering & Science
基金 国家自然科学基金资助项目(60472099)
关键词 蚁群算法 NP-完全问题 整数规划 背包问题 ant colony algorithrn NP-complete integer programming knapsack problem
分类号 TP311 [自动化与计算机技术—计算机软件与理论]
  • 相关文献

参考文献7

  • 1玄光男 程润伟.遗传算法与工程优化[M].北京:清华大学出版社,2004..
  • 2M Dorigo, G D Caro. Ant Colony Optimization: A New Meta-Heuristic[A]. Proc of the 1999 Congress on Evolutionary Cornputation[C]. 1999.1470-1477.
  • 3M Dorigo,I. M Gambardella. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem[J]. IEEE Trans on Evolutionary Computation, 1997,1(1): 53-66.
  • 4李庆华,李肯立,蒋盛益,张薇.背包问题的最优并行算法[J].软件学报,2003,14(5):891-896. 被引量：16
  • 5熊伟清,余舜浩,赵杰煜.具有分工的蚁群算法及应用[J].模式识别与人工智能,2003,16(3):328-333. 被引量：14
  • 6T Stutzle, H Hoos. MAX-MIN Ant System[J]. Journal of Future General Computer System, 2001,16(8) : 889-914.
  • 7http:.//nrich. maths. org/public, 2004-06.

二级参考文献16

  • 1Chor B,Rivest RL.A knapsack—type public key cryptosystem based on arithmetic in finite fields.IEEE Transactions on Information Theory,1988,34(5):901-909.
  • 2Laih C—S,Lee J-Y,Ham L,Su Y—K.Linearly shift knapsack public—key cryptosystem.IEEE Journal of Selected Areas Communication,1989,7(4):534-539.
  • 3Dantchev S.Improved sorting—based procedure for integer programming.Mathematical Programming,Serial A,2002,92:297-300.
  • 4Schroeppel R,Shamir A.A T=O(2^n/2),S=O(2^n/4)algorithm for certain NP—complete problems.SIAM Journal of Computing,1981,10(3):456-464.
  • 5Ferreira AG.A parallel time／hardware tradeoff T.H=O(2^n/2)for the knapsack problem.IEEE Transactions on Computing,1991,40(2):221-225.
  • 6Lou DC,Chang CC.A parallel two—list algorithm for the knapsack problem.Parallel Computing,1997,22:1985-1996.
  • 7Chang HK—C,Chen JJ-R,Shyu S-J.A parallel algorithm for the knapsack problem using a generation and searching technique.Parallel Computing,1994,20(2):233-243.
  • 8Ferreira AG.Efficient parallel algorithms for the knapsack problem.In:Cosnard M,Ba-on MH,Vanneschi M,ed.Proceedings of the IFIP WG 10.3 Working Conference on Parallel Processing.North—Holland:Elsevier Science Publishers,1988.169～179.
  • 9Cheng GL.The Design and Analysis of Parallel Algorithms.Bering:Higher Education Press,1994.35-37(in Chinese).
  • 10Colorni A, Dorigo M, Maniezzo V. Distributed Optimization by Ant Colonies. In: Proc of the 1st European Conference on Artificial Life, Pans, Elsevier, 1991, 134- 142.

共引文献423

同被引文献5

引证文献1

二级引证文献3

计算机工程与科学
2006年 第10期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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