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

doi:10.3696/j.issn.1672-6952.2015.04.012

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

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

王小彤,侯立刚,苏成利

( 辽宁石油化工大学信息与控制工程学院, 辽宁抚顺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

(School of Information and Control Engineering, Liaoning Shihua University, Fushun Liaoning 113001,China)

Published:2015-08-25 Online:2015-08-14

摘要/Abstract

摘要： 多维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.

[1]	王杨. 基于蚁群算法的粗糙集属性约简方法#br#[J]. 辽宁石油化工大学学报, 2009, 29(4): 74-77.
[2]	王艳玲,毕于深. 基于改进多蚁群算法的网络资源负载均衡与优化[J]. 辽宁石油化工大学学报, 2009, 29(2): 75-77.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics