辽宁石油化工大学学报

辽宁石油化工大学学报 ›› 2015, Vol. 35 ›› Issue (4): 53-57.DOI: 10.3696/j.issn.1672-6952.2015.04.012

• 计算机与自动化 • 上一篇    下一篇

一种改进的蚁群算法求解多维背包问题

王小彤,侯立刚,苏成利   

  1. ( 辽宁石油化工大学信息与控制工程学院, 辽宁抚顺1 1 3 0 0 1)
  • 出版日期:2015-08-25 发布日期:2015-08-14
  • 通讯作者: 侯立刚( 1 9 6 3 - ) , 男, 硕士, 教授, 从事计算机控制系统、 人工智能与专家系统应用研究; E - m a i l : h o u l i g a n g 2 0 0 9@1 2 6. c o m。
  • 作者简介:王小彤( 1 9 9 0 - ) , 女, 硕士研究生, 从事控制理论与控制工程的研究; E - m a i l : Am y K i n g 2 0 0 9@1 6 3. c o m。

An Improved Ant Colony Algorithm Solving MultiDimension Knapsack Problem

Wang Xiaotong， Hou Ligang， Su Chengli   

  1. (School of Information and Control Engineering, Liaoning Shihua University, Fushun Liaoning 113001,China)
  • Published:2015-08-25 Online:2015-08-14

PDF

摘要：  多维0 - 1背包问题是经典的非确定多项式问题( N o n - D e t e r m i n i s t i cP o l y n o m i a l ,N P) , 针对蚁群算法求解该问题时易出现陷入局部最优、 收敛速度慢等问题, 提出了一种改进的蚁群算法。本文算法引入蛙跳算法的分群思想, 将蚂蚁分为拥有不同文化的两个群体, 提高了全局搜索能力; 采用贪心策略修改公式, 针对具体问题具体分析, 提高了算法的精确度; 融合轮盘赌算法简化了公式。仿真结果表明, 本文算法加强了全局搜索能力, 得到的结果更为精确。

关键词: 蛙跳算法, 贪心策略, 蚁群算法, 多维0 - 1背包问题, 轮盘赌算法

Abstract: Multidimension 01 knapsack problem is a typical NonDeterministic Polynomial problem. In view that ant colony algorithm solving often have local optimum and slow convergence speed problems, this article propose an improved ant colony algorithm. Based on the introduction of leap frog algorithm clustering thought, the ants have been developed into two groups with different culture, which improves the global search ability. The greedy strategy modified formula is applied in order to improve the accuracy of calculation. The formula is further simplified by roulette algorithm. Simulation results indicated that the modified algorithm improves the accuracy and global search ability.

Key words: Leap frog algorithm, Greedy strategy, Ant colony algorithm, Multidimension 01 knapsack problem, Roulette algorithm

引用本文

王小彤,侯立刚,苏成利. 一种改进的蚁群算法求解多维背包问题[J]. 辽宁石油化工大学学报, 2015, 35(4): 53-57.

Wang Xiaotong， Hou Ligang， Su Chengli. An Improved Ant Colony Algorithm Solving MultiDimension Knapsack Problem[J]. Journal of Liaoning Petrochemical University, 2015, 35(4): 53-57.

使用本文

0
    /   /   推荐

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://journal.lnpu.edu.cn/CN/10.3696/j.issn.1672-6952.2015.04.012

               http://journal.lnpu.edu.cn/CN/Y2015/V35/I4/53



网站版权 © 2021《辽宁石油化工大学学报》编辑部

本系统由北京玛格泰克科技发展有限公司设计开发