一种求解子集问题的基于图的蚂蚁系统

被引：18

作者：

曹建军 ^{[1
,2
]}

张培林 ^{[1
,3
]}

王艳霞 ^{[4
]}

任国全 ^{[1
]}

傅建平 ^{[1
]}

机构：

[1] 军械工程学院火炮工程系

[2] 总参第研究所

[3] 南京理工大学机械工程学院

[4] 南京理工大学自动化学院

来源：

系统仿真学报 | 2008年 / 22期

关键词：

蚁群算法; 基于图的蚂蚁系统; 子集问题; 背包问题; 变异;

D O I：

10.16182/j.cnki.joss.2008.22.040

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

提出了一种求解子集问题的基于图的蚂蚁系统。针对子集问题,定义了构造图和等效路径,提出了基于等效路径增强的信息素更新策略,将问题的无序信息转化为对蚂蚁的有序影响,增加蚂蚁搜索路径的信息量。引入路径变异机制,通过路径的改良调节信息素分布,防止算法陷入停滞状态。将信息素更新分为三种情况:本次迭代最优更新、变异更新和本次迭代不更新,兼顾算法的收敛速度和搜索能力。对算法进行了描述并分析了算法复杂度。以多维背包问题为例,对该蚂蚁系统的性能进行了测试,验证了系统的有效性和优越性。

引用

页码：6146 / 6150

页数：5

共 5 条

[1]

蚁群算法原理及其应用.[M].段海滨; 著.科学出版社.2005,

[2]

现代优化计算方法.[M].邢文训;谢金星编著;.清华大学出版社.2005,

[3] 一种求解0-1背包问题的快速蚁群算法 [J].

王会颖 ;

贾瑞玉 ;

章义刚 ;

齐平 .

计算机技术与发展, 2007, (01) :104-107

[4] 基于蚁群优化算法的0-1背包问题求解 [J].

胡小兵 ;

黄席樾 .

系统工程学报, 2005, (05) :76-79+85

[5]

A Graph-based Ant System and its convergence.[J].Walter J. Gutjahr.Future Generation Computer Systems.2000, 8

← 1 →