摘 要 傳統(tǒng)蟻群算法在解決QoS路由問題時往往會在非線性整數(shù)規(guī)劃模型的基礎(chǔ)上盲目地搜索，其仿生智能沒有與問題特征很好的結(jié)合，所得到的組播樹有可能包含冗余的環(huán)路。為了研制性能更高的QoS組播路由方法，本文提出了一種新的基于蟻群優(yōu)化算法的QoS組播路由新算法。新算法根據(jù)最大最小螞蟻思想，結(jié)合螞蟻-Q算法對原算法進(jìn)行了改進(jìn)，使得在實際應(yīng)用中，算法選路更合理有效。

關(guān)鍵字 蟻群優(yōu)化算法 QoS路由

中圖分類號：TP311.52 文獻(xiàn)標(biāo)識碼：A

0引言

縱觀目前學(xué)術(shù)界已經(jīng)提出的QoS組播路由算法，有相當(dāng)一部分是基于備選路徑集的方法，即首先使用蟻群算法創(chuàng)建源節(jié)點到各個目的節(jié)點的備選路徑集，把組播路由的數(shù)學(xué)模型轉(zhuǎn)化為一個非線性整數(shù)規(guī)劃模型，再使用神經(jīng)網(wǎng)絡(luò)等算法求解這個模型。雖然這些算法利用了生物進(jìn)化、群智能等仿生智能，但它們都是在非線性整數(shù)規(guī)劃模型的基礎(chǔ)上盲目地搜索，其仿生智能沒有與問題特征很好的結(jié)合，這限制了其優(yōu)化性能的充分發(fā)揮，而且所得到的組播樹有可能包含冗余的環(huán)路。為了研制性能更高的QoS組播路由方法，本文提出了一種新的基于蟻群優(yōu)化算法的QoS組播路由新算法。

1算法設(shè)計

傳統(tǒng)蟻群系統(tǒng)在解決復(fù)雜問題時會早熟停滯。當(dāng)螞蟻搜索太少并且迅速開發(fā)到信息素濃度較高的路徑時，就有可能發(fā)生停滯。Stutzle和Hoos研究出最大最小螞蟻系統(tǒng)用于避免早熟停滯的發(fā)生。最大最小蟻群系統(tǒng)與蟻群系統(tǒng)最大的不同在于其信息素濃度被限定在一個給定的區(qū)間內(nèi)。新算法根據(jù)最大最小螞蟻思想，結(jié)合螞蟻-Q算法對原算法進(jìn)行了改進(jìn)。

3 算法仿真

為了盡可能體現(xiàn)真實的網(wǎng)絡(luò)環(huán)境，驗證算法的可行性，在模擬仿真實驗中采用基于C-均值聚類的隨機(jī)網(wǎng)絡(luò)拓?fù)渖善?。仿真過程中，網(wǎng)絡(luò)拓?fù)淠Ｐ褪墙⒃?000km€？000km的正方形區(qū)域內(nèi)，由新算法隨機(jī)在該區(qū)域內(nèi)隨機(jī)生成25個節(jié)點，并建立連接。不斷調(diào)整組播樹，直到尋找到的包含所有目的節(jié)點的組播樹勢能不再減小，組播樹更新結(jié)束。

在100個不同的網(wǎng)絡(luò)拓?fù)淠Ｐ蜕线\(yùn)行新算法，驗證結(jié)果成功率為99%。

4 算法評價

針對傳統(tǒng)蟻群系統(tǒng)在解決復(fù)雜問題時存在的缺陷，本文提出了改進(jìn)的蟻群算法。原有蟻群系統(tǒng)算法中采用參數(shù)控制路徑上的信息素濃度揮發(fā)，在螞蟻尋路過程中，如果某一步選擇概率較大，會造成后續(xù)螞蟻在此路徑上堆積過多信息素，最終會引起早熟停滯的現(xiàn)象發(fā)生。在新算法中，本文加入了參數(shù)，用于控制新加入的邊（）的信息素濃度在規(guī)定范圍內(nèi)，這樣就可以避免單條路徑上信息素猛增的現(xiàn)象發(fā)生。同時，在信息素更新規(guī)則中，將原有信息素變量（）更改為價值變量（），這樣更有利于在實際問題中的應(yīng)用。在QoS路徑求解中，價值變量（）體現(xiàn)為路徑代價。

新算法在設(shè)計中保留了原有蟻群算法中隨機(jī)數(shù)調(diào)整轉(zhuǎn)移規(guī)則的技術(shù)，加入了邊界制約參數(shù)防止路徑中信息素濃度的過度增長，有效避免了早熟停滯的發(fā)生。引入了價值變量，使得在實際應(yīng)用中，選路更合理有效。

參考文獻(xiàn)

[1] 段海濱.蟻群算法原理及其應(yīng)用.科學(xué)出版社，2006（07）.

[2] 蔡慧，劉洪波，等.基于K均值聚類的隨機(jī)網(wǎng)絡(luò)拓?fù)淠Ｐ蚚J].計算機(jī)工程與設(shè)計，2009，30（5）：1089-1901.