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

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

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

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

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

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