復雜動態(tài)隨機網(wǎng)絡最短路徑問題研究.pdf

1、經(jīng)典的最短路徑問題是圖論、網(wǎng)絡優(yōu)化中一個重要的研究內(nèi)容，它不僅可用于解決生產(chǎn)實際中的許多問題，而且還常常作為一個基本工具用于解決其他優(yōu)化問題。然而，大量現(xiàn)實世界中的網(wǎng)絡都具有動態(tài)、隨機特性，這種網(wǎng)絡中兩節(jié)點間最短路徑的定義及其求解方法都不同于傳統(tǒng)最短路徑問題，對其進行研究具有廣泛的實際應用價值和理論研究價值．本文針對動態(tài)隨機網(wǎng)絡最短路徑問題進行了較為深入的系統(tǒng)研究．論文的研究內(nèi)容和創(chuàng)新點主要包括以下幾個方面：
　　 (1)．提出

2、了基于蟻群優(yōu)化(ACO)的賦時蟻群優(yōu)化(TACO)算法，用于解決動態(tài)隨機網(wǎng)絡先驗(a priori)最短路徑問題。首先闡明了在動態(tài)，隨機環(huán)境下對先驗最短路徑問題進行研究的重要意義。然后對當前復雜網(wǎng)絡搜索問題的研究情況及其方法進行了介紹，分析表明這些方法能夠用于解決動態(tài)隨機網(wǎng)絡最短路徑問題，然而，單獨應用這些方法又存在一些不可避免的缺陷?？紤]到復雜網(wǎng)絡搜索方法本身的特點，本文將其融合于賦時蟻群優(yōu)化的框架之中，既解決了單獨采用這些方法時帶來

3、的缺陷，又充分利用了這些搜索方法提供的網(wǎng)絡結構信息，從而提高了TACO算法的搜索質(zhì)量和效率．此外，本文提出的TACO算法并不是適合所有的網(wǎng)絡模型，而是主要針對現(xiàn)實世界中廣泛存在的無標度網(wǎng)絡模型，并希望籍此增強算法的針對性，從而進一步提高算法的有效性。
　　 (2)．動態(tài)隨機網(wǎng)絡最短路徑的求解需要考慮時間以及網(wǎng)絡的狀態(tài)，因此其問題規(guī)模相對經(jīng)典最短路徑問題顯著增加。而對于諸如動態(tài)隨機網(wǎng)絡實時最短路徑這類問題的求解，問題規(guī)模的擴大將使

4、下一節(jié)點的選擇計算量大增，這勢必影響算法的有效性。而事實上，對于給定的動態(tài)隨機網(wǎng)絡源．目標節(jié)點對以及源節(jié)點出發(fā)時刻，可能只有很少一部分節(jié)點、邊以及邊的狀態(tài)能真正最終構成實時最短路徑，即大量的網(wǎng)絡信息對于給定的最短路徑求解都是冗余的?；诖?，本文研究了用于動態(tài)隨機網(wǎng)絡實時最短路徑求解的網(wǎng)絡化簡問題，給出了網(wǎng)絡化簡的具體思路和方法，并對影響算法化簡結果的一些因素以及算法的復雜性進行了分析。
　　 (3)．動態(tài)隨機網(wǎng)絡中邊的通過耗費是

5、一個不確定量，因此在某些邊的通過耗費不具有周期性且難以預測的情況下，采用實時最短路徑往往比采用先驗最短路徑更為有效。這里，實時最短路徑由根據(jù)網(wǎng)絡當前狀態(tài)在線選擇的下一節(jié)點構成。本文根據(jù)已有的研究成果，進一步分析了實時最短路徑可能的度量方式，進而給出了采用負效用函數(shù)度量網(wǎng)絡最短路徑的定義．將CPA(Convolution—propagation approach)近似處理方法引入到動態(tài)隨機網(wǎng)絡實時最短路徑的求解中，并基于改進的遺傳算法設計