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

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

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

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

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

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