基于改進蟻群算法的有線網絡路由QoS研究.pdf

1、隨著計算機網絡應用多元化的發(fā)展，傳統(tǒng)的盡力而為服務模型已不能滿足網絡中大量多媒體傳輸?shù)男枨螅非笥嬎銠C網絡服務質量(QoS)已成為網絡發(fā)展的趨勢。QoS路由選擇問題是在網絡中搜索路徑，該路徑各屬性滿足各種約束條件。已有學者證明，滿足多約束條件下的路由選擇是NPC問題，傳統(tǒng)算法無法在有效的多項式時間內求解最優(yōu)。
　　蟻群算法作為一種群智能搜索算法，能夠有效的解決NPC問題。蟻群算法具有并行性、魯棒性、易與其他算法相融合的優(yōu)點，但同時

2、也有收斂慢，易停滯的缺點。本論文第二，三章分別介紹計算機網絡服務質量(QoS)的基本概念，蟻群算法原理及一些改進方式。第四章介紹了基于新鮮度的分工蟻群算法，即將蟻群按照搜索狀況自動分成兩個不同分工的種群，其中一種分工的蟻群以一定的概率按照邊的新鮮度進行狀態(tài)轉移，以減弱過強的正反饋性，降低算法陷入停滯狀態(tài)的概率；另一種分工的蟻群則按照邊上的信息素進行狀態(tài)轉移，加強蟻群中搜索經驗的交流。各邊上信息素更新時，對組成較優(yōu)解的邊上信息素進行強化，

3、使螞蟻在接下來的搜索循環(huán)中趨向于優(yōu)質解。
　　第五章介紹了基于自主行為的蟻群算法，每只螞蟻將保存自己搜索到的最優(yōu)解與最差解。螞蟻在進行狀態(tài)轉移時，將按上次循環(huán)搜索的結果與自身搜索的最優(yōu)解與最差解相比較，自主地決定本次搜索循環(huán)螞蟻轉移的策略。上次循環(huán)搜索得到的解優(yōu)于最優(yōu)解的螞蟻將在本次及接下來一定次數(shù)的搜索循環(huán)內在該最優(yōu)解附近搜索，力圖獲取更優(yōu)質的解；上次循環(huán)搜索的解差于最差解的螞蟻在本次循環(huán)搜索進行狀態(tài)轉移時，將避免選擇組成最差解

4、的邊，以改善解的質量；處于最優(yōu)解與最差解之間的螞蟻在本次搜索循環(huán)時按照基本蟻群算法的方式進行狀態(tài)轉移，即依概率的方式進行選擇。按照最大-最小螞蟻系統(tǒng)的方式，將各邊的信息素量置于上下限之內，并且該上下限能夠隨著搜索狀況動態(tài)改變，以防止算法陷入停滯狀態(tài)。
　　以上兩種改進的蟻群算法均已應用于有線網絡QoS路由計算之中。采用Salam網絡隨機生成算法產生隨機網絡作為數(shù)據(jù)進行仿真實驗。仿真實驗表明，解決QoS路由選擇問題時，基于新鮮度的分