基于蟻群優(yōu)化算法的QoS路由算法的設(shè)計(jì)與仿真

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

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

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

0引言

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

1算法設(shè)計(jì)

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

3 算法仿真

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

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

4 算法評(píng)價(jià)

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

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

參考文獻(xiàn)

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

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