蚁群算法求解直径约束最小生成树问题

石 磊，冯祖针，杨建强

（红河学院 数学学院，云南 蒙自661100）

蚁群算法求解直径约束最小生成树问题

石 磊，冯祖针，杨建强

（红河学院 数学学院，云南 蒙自661100）

给定无向赋权图G和直径约束值D，直径约束最小生成树问题是查找一个直径不超过D最小权重的生成树.当时，其是NP-hard问题.用蚁群算法对其进行求解，设计了一种新的当前节点选择规则.分析和实验表明，基于新的节点选择规则的蚁群算法对直径约束最小生成树问题有较好的求解效果.

蚁群算法；直径约束最小生成树；直径约束

0 引言

直径约束最小生成(Bounded Diameter Minimum Spanning Tree，简记BDMST)问题是一个经典网络优化问题，在现实生活中有着广泛的应用，如路由优化、数据分发、分布式系统等[1,2].

BDMST问题描述为[3]：给定无向网络，任意节点，且；任意边且；任意边对应一个非负权值，称为长度或代价，.给定正整数D.设是一棵树，中节点的离心率定义为从到树中其它节点的最大距离.这里的距离是两个节点间边的数目.树的直径定义为节点的最大离心率.因此BDMST模型为：

文献[3]证明了直径约束值时的BDMST问题为NP-完全问题，因此BDMST问题不存在多项式时间算法，只能用启发式算法或人工智能算法求解.文献[4]提出一次性构造生成树算法(OTTC)，OTTC算法是基于Prim算法基础上的贪婪启发式算法，在不违背直径约束的条件每次选择距离最近的节点加入当前树中，直到当前树含有网络的所有节点，但其性能较差.Raidl和Julstrom[5-6]提出了随机贪婪启发算法(RGH)和基于边集编码的遗传算法(RJ-ESEA)，随后又提出了序列编码的遗传算法(JR-PEA)，JR-PEA算法取得良好的实验结果.文献[7]用蚁群算法(ACO)对BDMST问题进行了求解，也取得良好的效果.本文在文献[7]ACO算法求解的基础上，针对BDMST问题设计了新的当前节点选择规则取得比文献[7]ACO算法更好的求解效果.

1 ACO算法简介

蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法.意大利学者Dorigo等于1991年在巴黎最早提出蚁群算法的模型[8]，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为.

蚁群算法(人工蚁群算法)是受到对真实蚁群行为研究的启发而提出来的.蚂蚁个体通过信息素进行信息传递，蚂蚁在经过的路径上留下信息素，蚂蚁会感受到此路径上的信息量并指导自己选择这条路径.由大量蚂蚁组成的蚁群的集体行为表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大[9].蚁群算法已被成功应用于网络优化问题，如旅行商问题、背包问题、装箱问题等.

2 ACO算法设计

文献[7]ACO算法求解BDMST问题每次迭代的具体步骤为：(1)初始化，每只蚂蚁随机放到节点上；(2)在当前生成树中选择满足直径约束的节点组成当前节点集，然后根据当前节点选择规则选择当前节点；(3)根据状态转移规则选择下一个节点；(4)局部信息素更新；(5)重复(2)～(4)步直到找到条边或查找失败；(5)全局信息素更新.

文献[7]ACO算法求解BDMST问题关键是根据当前节点选择规则选择当前节点、状态转移规则选择下一个节点、局部信息素更新和全局信息素更新.下面将详细叙述这些规则的设计：

(3)局部信息素更新规则和全局信息素更新规则可参见ACO算法中信息素更新规则，见文献[10].

本文对文献[7]ACO算法中当前节点选择规则进行了改进，记改进后的算法为本ACO算法，其更快地收敛到全局最优解，而不易陷于局部最优解，取得了更好的求解效果.

3 数值实验

本ACO算法参数的设计和文献[7]ACO算法参数的设置都一样，迭代停止的条件为20次迭代未获得更好的解便停止.用MatLab语言编程实现本ACO算法，大量数值实验表明此算法有较高的效率.算例都采用Beasley’s OR-library(链接为http://www.people.brunel.ac.uk)提供的例子.Beasley’s OR-library给出不同规模的度量施泰纳树问题的很多例子，每个规模提供15个例子.

例1 Beasley’s OR-library中节点规模为50的第1个例子，直径约束.

解：用本ACO算法连续10次求得的结果分别为：7.612，7.671，7.600，7.783，7.695，7.709，7.843，7.817，7.783，7.793 .其均值为7.730，比文献[7]ACO算法的均值结果7.871要好，比JR-PEA算法7.930也好.本ACO算法每次迭代总次数的为50左右，文献[7]ACO算法每次迭代总次数为70左右，JR-PEA算法每次迭代总次数为190左右。

例2 同样选用Beasley’s OR-library不同规模的例子，对每个例子连续运算10次与文献[7]ACO算法比较的结果如表1

表1 本ACO算法与文献[7]ACO算法连续10次计算获得的最优值、平均值及方差的比较

4 结语

BDMST问题是异常困难的组合优化问题，本文在对文献[7]ACO算法中的当前节点选择规则进行了改进获得更好求解效果.DMST问题有着广泛的实际应用，其它更好的方法有待进一步研究.

[1] Cho J, Breen J.Analysis of the performance of dynamic multicast routing algorithms[J].Computer Communications, 1999, 22(7):667-674..

[2] Flajolet P, Gao Z, Odlyzko A.The distribution of heights of binary trees and other simple trees[J].Probability and Computing, 1992,42: 243-248.

[3] M.R.Garey, D.S.Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness[M].New York: W.H.Freeman, 1979: 206-218.

[4] Narsingh Deo, Ayman Abdalla.Computing a Diameter-Constrained Minimum Spanning Tree in Parallel[J].Lecture Notes in Computer Science, 2000,1767: 17-31.

[5] Raidl G.R, Julstrom B.A.Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem[C].Florida: Proceedings of the 2003 ACM Symposium on Applied Computing, 2003.

[6] Julstrom B.A, Raidl G.R.A permutation-coded evolutionary algorithm for the bounded-diameter minimum spanning tree problem[C].Chicago: Genetic and Evolutionary Computation Conference’s Workshops Proceedings, 2003.

[7] Gunther Raidl, Ulrich Pferschy.Exact and Heuristic Approaches for Solving the Bounded Diameter Minimum Spanning Tree Problem[M].Vienna: Institute of Computer Graphics and Algorithms, 2009.

[8] Colorni A, Dorigo M, Maniezzo V.Distributed optimization by ant colonies[C].Paris: Proceedings of the 1st European Conference on Artificial Life,1991:134-142.

[9] 王宏生,孟国艳.人工智能及其应用[M].北京:国防工业出版社,2009.

[10] 李士勇, 陈永强,李研.蚁群算法及应用[M].哈尔滨工业大学出版社,2004:19.

Ant Colony Algorithm for Bounded Diameter Minimum Spanning Tree Problem

SHI Lei, FENG Zu-zhen, YANG Jian-qiang
(Department of Mathematics, Honghe University, Mengzi 661100, China)

Given a connected, weighted, undirected graph G and a bound D, the bounded diameter minimum spanning tree problem sought a spanning tree on G of minimum weight among the trees in which no path between two vertices contains more than D edges.This problem was NP-hard for 4≤D ≤|V|-1.Ant colony algorithm was designed for the bounded diameter minimum spanning tree problem,which based on new node-selection strategy.The algorithm was proved to be effective by analysis and experiments..

ant colony algorithm; bounded diameter minimum spanning tree; bounded diameter

O157.6

A

1008-9128（2012）04-0016-03

2012-03-11

石磊（1984—），男，湖南衡阳人，硕士.研究方向：网络安全.

[责任编辑 张灿邦]