基于改進(jìn)蟻群算法的有線網(wǎng)絡(luò)路由QoS研究.pdf

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

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

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

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