一種求解簡單網(wǎng)絡(luò)路由問題的混合蟻群算法

摘 要: 蟻群算法是一種新型的模擬進(jìn)化算法，為求解復(fù)雜的組合優(yōu)化問題提供了一種新的思路。該文提出了一種求解網(wǎng)絡(luò)路由問題的混合蟻群算法，該算法根據(jù)概率取值的不同選取三種不同的狀態(tài)轉(zhuǎn)移規(guī)則，通過仿真實(shí)驗(yàn)，獲得了較好的效果，并與禁忌搜索算法進(jìn)行了對(duì)比，結(jié)果表明，混合蟻群算法比禁忌搜索算法運(yùn)行的時(shí)間更短，具有更好的求解性能。

關(guān)鍵詞: 網(wǎng)絡(luò)路由問題 混合蟻群算法 計(jì)算機(jī)仿真

1.引言

在網(wǎng)絡(luò)設(shè)計(jì)中，我們經(jīng)常會(huì)遇到這樣一類問題:在由多個(gè)路由器組成的網(wǎng)絡(luò)中，路由器之間的各個(gè)直接鏈路都具有各自的傳輸時(shí)延，求解從某一個(gè)路由器出發(fā)，到達(dá)另一個(gè)路由器的最短時(shí)延，這就是路由選擇問題。從數(shù)學(xué)的角度可簡化為:在由多個(gè)節(jié)點(diǎn)組成的網(wǎng)絡(luò)中，節(jié)點(diǎn)與節(jié)點(diǎn)之間的鏈路具有各自的距離，求解一條從某一節(jié)點(diǎn)到達(dá)另一節(jié)點(diǎn)的最短距離的路徑[1]。

利用傳統(tǒng)的方法(如Dijkstra算法)來解決該問題往往會(huì)隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的增加，收斂速度明顯變慢，為此人們不斷地研究出了一些新的算法。文獻(xiàn)[2]提出利用拉格朗日松馳因子法與次梯度尋優(yōu)法來找到最優(yōu)解的范圍和可行解，但算法復(fù)雜，計(jì)算和編程工作量大。文獻(xiàn)[3]將其近似為一個(gè)二次型優(yōu)化問題，利用一種具有全局收斂性質(zhì)的神經(jīng)網(wǎng)絡(luò)給予解決。文獻(xiàn)[4，5]分別利用遺傳算法、禁忌搜索算法解決這一問題。

本文提出了一種建立在蟻群算法基礎(chǔ)上的新的路由擇算法——根據(jù)概率取值的不同選取不同的狀態(tài)轉(zhuǎn)移規(guī)則，通過適當(dāng)調(diào)整參數(shù)得出滿足要求的解。仿真結(jié)果表明，這是一種有效地求解網(wǎng)絡(luò)路由問題的算法。

2.基本蟻群算法

Dorigo首先提出了蟻群算法。蟻群算法是模仿真實(shí)的蟻群行為而提出的一種模擬進(jìn)化算法。螞蟻個(gè)體之間是通過一種稱之為信息素(Pheromone)的物質(zhì)進(jìn)行信息傳遞，從而相互協(xié)作、完成復(fù)雜任務(wù)的。螞蟻在運(yùn)動(dòng)過程中，能夠在它所經(jīng)過的路徑上留下信息素，其他螞蟻在運(yùn)動(dòng)過程中能夠感知這種物質(zhì)的存在及其強(qiáng)度，并以此指導(dǎo)自己的運(yùn)動(dòng)方向，螞蟻傾向于朝著該物質(zhì)強(qiáng)度高的方向移動(dòng)。因此，由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象:某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。螞蟻個(gè)體之間就是通過這種信息素的交流，搜索到一條從蟻巢到食物源的可能的較短路徑。

蟻群算法的步驟可簡要地表述為:步驟1:設(shè)置所有參數(shù)，信息素痕跡初始化;步驟2:每只螞蟻根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則建立一個(gè)完整的解，狀態(tài)轉(zhuǎn)移規(guī)則主要取決于信息素和啟發(fā)式信息;步驟3:更新信息素。這三個(gè)過程不斷重復(fù)，直到滿足終止條件。

實(shí)際上，蟻群算法目前已成功地應(yīng)用到不同的連續(xù)和組合優(yōu)化問題，比如旅行商問題(Traveling Salesman Problem， TSP)[6]、連續(xù)函數(shù)優(yōu)化[7]、網(wǎng)格分割問題[8]等。

3.混合蟻群算法求解網(wǎng)絡(luò)路由問題

開始時(shí)，所有的個(gè)螞蟻都集中在起點(diǎn)S處。螞蟻i從S點(diǎn)出發(fā)，按照選擇策略，從和S相關(guān)聯(lián)的邊的集合中，選擇一條邊;然后從這條邊的另一節(jié)點(diǎn)a開始，從和a相關(guān)聯(lián)的邊的集合中，選擇另一條邊。以此類推，直到搜索到終點(diǎn)D，于是，螞蟻i得到一個(gè)從S到D的解。每當(dāng)螞蟻選擇完一條邊后，就馬上更新邊上的信息量(局部更新)。螞蟻i搜索完后，螞蟻j從S出發(fā)，按照和螞蟻i相同的方法，搜索出一條從S到D的路徑，得到一個(gè)解。直到所有的m個(gè)螞蟻都進(jìn)行完搜索，得到m個(gè)解(包括重復(fù)的)。以m個(gè)解為基礎(chǔ)，采用局部搜索算法，進(jìn)行局部搜索，得到局部最優(yōu)解。根據(jù)局部最優(yōu)解全局計(jì)算信息增量(全局更新)，全局更新后，繼續(xù)迭代直到滿足停止條件，停止條件為最大迭代次數(shù)。在所求得的所有局部最優(yōu)解中，值最小的解為所求的全局最優(yōu)解，即最短路徑的距離值。用基本的蟻群算法求解最短路徑問題的主要實(shí)現(xiàn)步驟如下。

(1)信息初始化:算法開始運(yùn)行時(shí)，賦予每條邊上相等數(shù)量的信息量。

(2)選擇策略:位于第i個(gè)節(jié)點(diǎn)的螞蟻k，根據(jù)概率q(0

規(guī)則1:螞蟻k依據(jù)啟發(fā)式信息以貪婪方式選擇邊(i，j)，即:

規(guī)則2:螞蟻k依據(jù)信息素和啟發(fā)式信息以貪婪方式選擇邊(i，j)，即:

規(guī)則3:螞蟻k依據(jù)輪盤賭策略選擇邊(i，j)，位于節(jié)點(diǎn)i的螞蟻選擇節(jié)點(diǎn)j的概率根據(jù)式(3)計(jì)算。

蟻在運(yùn)行過程中所積累的信息素和啟發(fā)式信息在螞蟻選擇節(jié)點(diǎn)時(shí)的相對(duì)重要性。

α為信息啟發(fā)式因子， 表示軌跡的相對(duì)重要性，反映了螞蟻在運(yùn)動(dòng)過程中所積累的信息在螞蟻運(yùn)動(dòng)時(shí)所起的作用， 其值越大， 螞蟻越容易選擇其他螞蟻?zhàn)哌^的路徑;β為期望啟發(fā)式因子， 表示啟發(fā)式信息的相對(duì)重要性，反映了螞蟻在運(yùn)動(dòng)過程中啟發(fā)信息在螞蟻選擇路徑中的受重視程度， 其值越大， 則該狀態(tài)轉(zhuǎn)移概率越接近于貪心規(guī)則。

(3)信息素更新:混合蟻群算法局部信息更新規(guī)則。螞蟻從節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j后，路徑( i， j) 上的信息量按公式(4)進(jìn)行更新:

蟻群系統(tǒng)全局信息更新規(guī)則:全局更新在所有螞蟻都完成它們的路徑之后執(zhí)行，針對(duì)全局最優(yōu)解或本次循環(huán)的最優(yōu)解(迭代最優(yōu)解)所屬的邊按公式(5)進(jìn)行信息更新:

求解網(wǎng)絡(luò)路由問題的混合蟻群算法的基本步驟是:

步驟2:將源頂點(diǎn)置于當(dāng)前解集中，對(duì)位于節(jié)點(diǎn)i的每只螞蟻k=1，2，…，m，按狀態(tài)轉(zhuǎn)移規(guī)則移至下一個(gè)節(jié)點(diǎn)j;將節(jié)點(diǎn)j置于當(dāng)前解集;

步驟3:根據(jù)式(4)對(duì)邊(i，j)進(jìn)行信息素局部更新;

步驟8:輸出目前最好解。

4.計(jì)算機(jī)仿真

我們通過文獻(xiàn)[5]中的兩個(gè)例子來說明混合蟻群算法的有效性，并與禁忌搜索算法的求解結(jié)果進(jìn)行了對(duì)比。

本文實(shí)驗(yàn)的運(yùn)行環(huán)境是:操作系統(tǒng)為Windows XP，512MB內(nèi)存，CPU 2.4GHz，程序設(shè)計(jì)語言為Java。初始參數(shù)設(shè)運(yùn)用混合蟻群算法求解例1得到的結(jié)果是(B C G J)，最短路徑長度為13;求解例2得到的結(jié)果是(2 7 8 14 15)，最短路徑長度是1.27。將計(jì)算結(jié)果與禁忌搜索算法的仿真結(jié)果進(jìn)行對(duì)比，比較結(jié)果如表1所示。

分析表1的比較結(jié)果，可以看出混合蟻群算法求得的最短路徑長度與禁忌搜索算法求得的最短路徑長度一致，但混合蟻群算法的迭代次數(shù)明顯少于禁忌搜索算法，算法用時(shí)也較短。

5.結(jié)語

通過仿真實(shí)驗(yàn)與比較分析，我們證明本文提出的混合蟻群算法可以在較短的時(shí)間內(nèi)獲得較理想的結(jié)果，可以有效地解決網(wǎng)絡(luò)路由問題。蟻群算法是一種新型的進(jìn)化算法，其研究剛剛起步，有許多問題有待解決。從理論上對(duì)該算法進(jìn)行更深刻的研究將是進(jìn)一步研究的內(nèi)容。

參考文獻(xiàn):

[1]Tanenbaum A S著.熊桂喜，王小虎譯.計(jì)算機(jī)網(wǎng)絡(luò)(第三版).北京:清華大學(xué)出版社，1998.

[2]Gavish B，Hantler S L.An algorithm for optimal route selection In SNA networks.IEEE Trans.on Communications，1983，31，(10):1154-1167.

[3]張順頤，邵艾青，沈蘇彬，吳新余.一種基于神經(jīng)網(wǎng)絡(luò)模型的計(jì)算機(jī)通信網(wǎng)絡(luò)遲延和流量分配新算法.通信學(xué)報(bào)，1995，16，(6):1-8.

[4]Leung Y，LI G，Xu Z B.A genetic algorithm for the multiple destination routing problems.IEEE Trans.on Evolutionary Computation，1998，2，(4).

[5]王東平，李紹榮.禁忌搜索算法用于解決網(wǎng)絡(luò)路由問題.計(jì)算機(jī)科學(xué)，2003，30，(6):55-56.

[6]T.Kaji.Approach by ant tabu agents for traveling salesman problem[J].Proceedings of the IEEE International Conference on Systems，2001，5:3429-3434.

[7]魏平，熊偉清.用于一般函數(shù)優(yōu)化的蟻群算法[J].寧波大學(xué)學(xué)報(bào)，2001，14，(4):52-55.

[8]P.Korosec，J.Silc.Solving the mesh-partitioning problem with an ant-colony algorithm[J].Parallel Computing，2004，30，(5-6):785-801.