蟻群優(yōu)化算法及在網(wǎng)絡(luò)路由中的應(yīng)用研究.pdf

1、螞蟻具有找到蟻穴與食物源之間最短路徑的能力，受此啟發(fā)提出的蟻群算法最初用于解決旅行商問(wèn)題，具有自適應(yīng)性、魯棒性及本質(zhì)上的并行性等許多特點(diǎn)，廣泛適用于各種靜態(tài)和動(dòng)態(tài)的組合優(yōu)化問(wèn)題中，具有潛在的應(yīng)用前景。 由Dorigo等提出的蟻群算法的描述可知，在通用啟發(fā)式蟻群算法的起始階段，信息素值被初始化為統(tǒng)一的值，對(duì)解的搜索沒(méi)有指導(dǎo)意義，啟發(fā)值此時(shí)反而能夠提供有用的局部信息，有助于算法的快速收斂。隨著算法的進(jìn)行，根據(jù)搜索到的不同路徑而更新的

2、信息素值，存儲(chǔ)了解空間的全局最優(yōu)解信息，相對(duì)于啟發(fā)值而言，所起的作用不斷提高。因此設(shè)計(jì)了一種自適應(yīng)的啟發(fā)值因子，能夠隨著算法的進(jìn)行調(diào)整信息素值和啟發(fā)值之間的相對(duì)權(quán)重，加速算法的收斂速度。 網(wǎng)絡(luò)路由問(wèn)題所具有的一些特征，如內(nèi)部信息、分布計(jì)算、隨機(jī)動(dòng)態(tài)，以及異步的網(wǎng)絡(luò)狀態(tài)更新等，與蟻群優(yōu)化算法的特征匹配得很好，能很好地解決這一問(wèn)題。本論文的另一個(gè)主要研究成果就是在蟻群優(yōu)化的基礎(chǔ)上，提出了新的路由算法。這種算法具有本質(zhì)上的可擴(kuò)展性，能

3、有效解決大型通信網(wǎng)絡(luò)資源的分配問(wèn)題。整個(gè)算法應(yīng)用概率選擇數(shù)據(jù)包轉(zhuǎn)發(fā)的路徑，能夠充分利用多條可行路徑，從而提高網(wǎng)絡(luò)負(fù)載的均衡性、魯棒性、負(fù)載流量以及網(wǎng)絡(luò)的利用率。 本文以基于圖論的蟻群算法為基礎(chǔ)，給出了蟻群算法的一般性模型，討論了其收斂性及在靜態(tài)TSP和動(dòng)態(tài)網(wǎng)絡(luò)路由問(wèn)題中的應(yīng)用，主要工作內(nèi)容有： 第一章給出了蟻群算法的描述和在靜態(tài)、動(dòng)態(tài)情況下的各類(lèi)應(yīng)用，并指出蟻群算法所具有的分布式計(jì)算、魯棒性、應(yīng)用簡(jiǎn)單等特點(diǎn)，以及蟻群算法

4、潛在的廣泛應(yīng)用前景。 第二章分析了蟻群算法的基本原理，針對(duì)蟻群算法所能解決的問(wèn)題給出了一般性的描述。并定義了蟻群算法考慮節(jié)點(diǎn)模式信息素分布的解構(gòu)造圖，在此解構(gòu)造圖上，定義了一種隨機(jī)搜索機(jī)制的人工螞蟻，在此基礎(chǔ)上提出了蟻群算法的統(tǒng)一框架，并討論了幾種常見(jiàn)的改進(jìn)途徑。 第三章蟻群算法在解構(gòu)造圖上通過(guò)不斷地迭代過(guò)程來(lái)構(gòu)造解，把蟻群算法解的迭代過(guò)程理解為離散時(shí)間馬爾可夫過(guò)程，可以證明迭代所構(gòu)造的解將以接近于1的概率收斂于最優(yōu)解。

5、 第四章基于通用啟發(fā)式蟻群算法提出了一類(lèi)分布式組合優(yōu)化算法，并設(shè)計(jì)了一種倒指數(shù)關(guān)系曲線(xiàn)來(lái)描述啟發(fā)值的權(quán)重參數(shù)，以提高算法的收斂速度，在仿真試驗(yàn)中獲得了較好的結(jié)果。 第五章描述了所使用的網(wǎng)絡(luò)模型，特別定義了如何計(jì)算網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)之間的路由時(shí)間，也解釋了邊的權(quán)重是時(shí)間隨機(jī)函數(shù)的動(dòng)態(tài)圖。并在蟻群算法基礎(chǔ)上提出了一種完全分布式路由負(fù)載平衡算法，為當(dāng)前路由選擇問(wèn)題的解決提供了一種新途徑。 第六章利用蟻群算法與Q學(xué)習(xí)算法相結(jié)