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

石 磊，馮祖針，楊建強

（紅河學院 數學學院，云南 蒙自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—），男，湖南衡陽人，碩士.研究方向：網絡安全.

[責任編輯 張燦邦]