石 磊，馮祖針，楊建強(qiáng)

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

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

石 磊，馮祖針，楊建強(qiáng)

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

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

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

0 引言

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

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

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

1 ACO算法簡介

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

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

2 ACO算法設(shè)計(jì)

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

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

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

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

3 數(shù)值實(shí)驗(yàn)

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

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

解：用本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，比文獻(xiàn)[7]ACO算法的均值結(jié)果7.871要好，比JR-PEA算法7.930也好.本ACO算法每次迭代總次數(shù)的為50左右，文獻(xiàn)[7]ACO算法每次迭代總次數(shù)為70左右，JR-PEA算法每次迭代總次數(shù)為190左右。

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

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

4 結(jié)語

BDMST問題是異常困難的組合優(yōu)化問題，本文在對(duì)文獻(xiàn)[7]ACO算法中的當(dāng)前節(jié)點(diǎn)選擇規(guī)則進(jìn)行了改進(jìn)獲得更好求解效果.DMST問題有著廣泛的實(shí)際應(yīng)用，其它更好的方法有待進(jìn)一步研究.

[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] 王宏生,孟國艷.人工智能及其應(yīng)用[M].北京:國防工業(yè)出版社,2009.

[10] 李士勇, 陳永強(qiáng),李研.蟻群算法及應(yīng)用[M].哈爾濱工業(yè)大學(xué)出版社,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)絡(luò)安全.

[責(zé)任編輯 張燦邦]