蟻群算法求解直徑約束最小生成樹問題

石 磊，馮祖針，楊建強

（紅河學院 數(shù)學學院，云南 蒙自661100）

蟻群算法求解直徑約束最小生成樹問題

石 磊，馮祖針，楊建強

（紅河學院 數(shù)學學院，云南 蒙自661100）

給定無向賦權(quán)圖G和直徑約束值D，直徑約束最小生成樹問題是查找一個直徑不超過D最小權(quán)重的生成樹.當時，其是NP-hard問題.用蟻群算法對其進行求解，設計了一種新的當前節(jié)點選擇規(guī)則.分析和實驗表明，基于新的節(jié)點選擇規(guī)則的蟻群算法對直徑約束最小生成樹問題有較好的求解效果.

蟻群算法；直徑約束最小生成樹；直徑約束

0 引言

直徑約束最小生成(Bounded Diameter Minimum Spanning Tree，簡記BDMST)問題是一個經(jīng)典網(wǎng)絡優(yōu)化問題，在現(xiàn)實生活中有著廣泛的應用，如路由優(yōu)化、數(shù)據(jù)分發(fā)、分布式系統(tǒng)等[1,2].

BDMST問題描述為[3]：給定無向網(wǎng)絡，任意節(jié)點，且；任意邊且；任意邊對應一個非負權(quán)值，稱為長度或代價，.給定正整數(shù)D.設是一棵樹，中節(jié)點的離心率定義為從到樹中其它節(jié)點的最大距離.這里的距離是兩個節(jié)點間邊的數(shù)目.樹的直徑定義為節(jié)點的最大離心率.因此BDMST模型為：

文獻[3]證明了直徑約束值時的BDMST問題為NP-完全問題，因此BDMST問題不存在多項式時間算法，只能用啟發(fā)式算法或人工智能算法求解.文獻[4]提出一次性構(gòu)造生成樹算法(OTTC)，OTTC算法是基于Prim算法基礎上的貪婪啟發(fā)式算法，在不違背直徑約束的條件每次選擇距離最近的節(jié)點加入當前樹中，直到當前樹含有網(wǎng)絡的所有節(jié)點，但其性能較差.Raidl和Julstrom[5-6]提出了隨機貪婪啟發(fā)算法(RGH)和基于邊集編碼的遺傳算法(RJ-ESEA)，隨后又提出了序列編碼的遺傳算法(JR-PEA)，JR-PEA算法取得良好的實驗結(jié)果.文獻[7]用蟻群算法(ACO)對BDMST問題進行了求解，也取得良好的效果.本文在文獻[7]ACO算法求解的基礎上，針對BDMST問題設計了新的當前節(jié)點選擇規(guī)則取得比文獻[7]ACO算法更好的求解效果.

1 ACO算法簡介

蟻群算法(ant colony optimization, ACO)，又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機率型算法.意大利學者Dorigo等于1991年在巴黎最早提出蟻群算法的模型[8]，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為.

蟻群算法(人工蟻群算法)是受到對真實蟻群行為研究的啟發(fā)而提出來的.螞蟻個體通過信息素進行信息傳遞，螞蟻在經(jīng)過的路徑上留下信息素，螞蟻會感受到此路徑上的信息量并指導自己選擇這條路徑.由大量螞蟻組成的蟻群的集體行為表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大[9].蟻群算法已被成功應用于網(wǎng)絡優(yōu)化問題，如旅行商問題、背包問題、裝箱問題等.

2 ACO算法設計

文獻[7]ACO算法求解BDMST問題每次迭代的具體步驟為：(1)初始化，每只螞蟻隨機放到節(jié)點上；(2)在當前生成樹中選擇滿足直徑約束的節(jié)點組成當前節(jié)點集，然后根據(jù)當前節(jié)點選擇規(guī)則選擇當前節(jié)點；(3)根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則選擇下一個節(jié)點；(4)局部信息素更新；(5)重復(2)～(4)步直到找到條邊或查找失敗；(5)全局信息素更新.

文獻[7]ACO算法求解BDMST問題關(guān)鍵是根據(jù)當前節(jié)點選擇規(guī)則選擇當前節(jié)點、狀態(tài)轉(zhuǎn)移規(guī)則選擇下一個節(jié)點、局部信息素更新和全局信息素更新.下面將詳細敘述這些規(guī)則的設計：

(3)局部信息素更新規(guī)則和全局信息素更新規(guī)則可參見ACO算法中信息素更新規(guī)則，見文獻[10].

本文對文獻[7]ACO算法中當前節(jié)點選擇規(guī)則進行了改進，記改進后的算法為本ACO算法，其更快地收斂到全局最優(yōu)解，而不易陷于局部最優(yōu)解，取得了更好的求解效果.

3 數(shù)值實驗

本ACO算法參數(shù)的設計和文獻[7]ACO算法參數(shù)的設置都一樣，迭代停止的條件為20次迭代未獲得更好的解便停止.用MatLab語言編程實現(xiàn)本ACO算法，大量數(shù)值實驗表明此算法有較高的效率.算例都采用Beasley’s OR-library(鏈接為http://www.people.brunel.ac.uk)提供的例子.Beasley’s OR-library給出不同規(guī)模的度量施泰納樹問題的很多例子，每個規(guī)模提供15個例子.

例1 Beasley’s OR-library中節(jié)點規(guī)模為50的第1個例子，直徑約束.

解：用本ACO算法連續(xù)10次求得的結(jié)果分別為：7.612，7.671，7.600，7.783，7.695，7.709，7.843，7.817，7.783，7.793 .其均值為7.730，比文獻[7]ACO算法的均值結(jié)果7.871要好，比JR-PEA算法7.930也好.本ACO算法每次迭代總次數(shù)的為50左右，文獻[7]ACO算法每次迭代總次數(shù)為70左右，JR-PEA算法每次迭代總次數(shù)為190左右。

例2 同樣選用Beasley’s OR-library不同規(guī)模的例子，對每個例子連續(xù)運算10次與文獻[7]ACO算法比較的結(jié)果如表1

表1 本ACO算法與文獻[7]ACO算法連續(xù)10次計算獲得的最優(yōu)值、平均值及方差的比較

4 結(jié)語

BDMST問題是異常困難的組合優(yōu)化問題，本文在對文獻[7]ACO算法中的當前節(jié)點選擇規(guī)則進行了改進獲得更好求解效果.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].北京:國防工業(yè)出版社,2009.

[10] 李士勇, 陳永強,李研.蟻群算法及應用[M].哈爾濱工業(yè)大學出版社,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—），男，湖南衡陽人，碩士.研究方向：網(wǎng)絡安全.

[責任編輯 張燦邦]