關(guān)于不確定條件下的最短路徑問題的研究

1、-關(guān)于不確定條件下的最短路徑問題的研究摘要：在利用最短路模型解決問題時(shí)，由于天氣、運(yùn)輸條件以及時(shí)間段等原因，網(wǎng)絡(luò)中弧的權(quán)值經(jīng)常很難給出確切的值。對傳統(tǒng)的最短路徑優(yōu)化模型提出了挑戰(zhàn)，也為最短路徑優(yōu)化模型的進(jìn)一步發(fā)展提供了新的機(jī)遇。本文主要就不確定條件下最短路徑問題進(jìn)行研究，介紹了一種不確定條件下最短路徑問題隨機(jī)優(yōu)化模型有約束的期望最短路徑模型，利用結(jié)合隨機(jī)模擬方法和遺傳算法的混合智能算法進(jìn)行求解。通過系統(tǒng)的學(xué)習(xí)不確定條件下的最短路徑問題的解決方法， 開拓了思路，對自己運(yùn)用系統(tǒng)思維解決自己研究方向的問題有很大的啟發(fā)。關(guān)鍵字：網(wǎng)絡(luò)優(yōu)化；不確定最短路徑問題；系統(tǒng)思維一、引言最短路徑問題是指在網(wǎng)絡(luò)中尋找

2、節(jié)點(diǎn)間具有最小長度( 或最小費(fèi)用 ) 的路徑，具有重要的理論和實(shí)際應(yīng)用意義。一方面，它可以直接應(yīng)用于許多實(shí)際問題，如各種管道的鋪設(shè)，線路安排等 ; 另一方面，它也常被利用為解決其他一些優(yōu)化問題的工具， 是網(wǎng)絡(luò)優(yōu)化中的一個(gè)基本而又重要的問題。 因此運(yùn)籌界、 工業(yè)界的學(xué)者對最短路徑及其變形問題就算法和應(yīng)用等方面進(jìn)行了廣泛的研究。然而在很多具體的應(yīng)用中， 我們遇到的信息， 存在著客觀的或者人為的不確定性， 這種不確定性的表現(xiàn)形式是多種多樣的， 例如隨機(jī)性、模糊性等。在利用最短路徑模型解決問題時(shí)，由于天氣、運(yùn)輸條件以及時(shí)間段等原因， 網(wǎng)絡(luò)中弧的權(quán)值經(jīng)常很難給出確切的估計(jì)， 這-樣只能根據(jù)歷史數(shù)據(jù)獲得其

3、概率分布情況，即這些數(shù)據(jù)是隨機(jī)的。但是隨機(jī)性只是不確定性的一個(gè)方面，對于一些情況，譬如缺少歷史數(shù)據(jù)、或者歷史數(shù)據(jù)不可靠時(shí)，這些數(shù)據(jù)只能由專家根據(jù)自己的經(jīng)驗(yàn)給出主觀的估計(jì)，譬如通過該條路徑的時(shí)間大概是 3 小時(shí)，流經(jīng)該線路需時(shí)40 分鐘左右，這樣表征弧上權(quán)值的量也因此而模糊起來，此時(shí)利用最短路徑模型解決實(shí)際問題必須考慮這種不確定性。雖然對于不確定條件下的最短路徑問題，學(xué)者們可通過研究動(dòng)態(tài)隨機(jī)網(wǎng)絡(luò)中路徑的分布函數(shù)以及期望值來研究網(wǎng)絡(luò)問題， 給出了分布函數(shù)為某一類型的求解方法，并沒有考慮不同的決策要求， 或者是分布函數(shù)為一般情況時(shí)的求解方法。至于模糊最短路徑問題，最早由Dubois 和 Prade

4、1 ，2 在 1980 年首次提出，他們根據(jù)模糊集理論中的最大、最小值算子和Zadeh擴(kuò)展原理，來求模糊最短路的長度，但由于模糊運(yùn)算的特點(diǎn)，經(jīng)過多次運(yùn)算得到的模糊長度有時(shí)候并不能和某條路徑對應(yīng)上。有的學(xué)者根據(jù)多準(zhǔn)則決策理論求非被支配解路徑集合，但當(dāng)網(wǎng)絡(luò)較大時(shí)，該集合就會(huì)很大，對于決策者從中選擇滿意的方案就會(huì)很困難。因此，在不確定條件下建立模型給出算法，為決策者提供有價(jià)值的方案，具有重要的意義。二、問題描述為了對最短路問題進(jìn)行建模，本文考慮無圈有向網(wǎng)絡(luò)圖，將網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)用圖論術(shù)語可以描述如下: 在有向圖G=(V,A,W) 中,V=l,2, ., n代表節(jié)點(diǎn)集( 設(shè)節(jié)點(diǎn)總數(shù)共計(jì)n 個(gè)),A代表弧

5、集, 每個(gè)弧使用節(jié)點(diǎn)的有序?qū), j來表示，其中i ,A ，并假設(shè)從節(jié)點(diǎn)i 到節(jié)點(diǎn)jj-之間只有一條有向弧。WW ij | i , jA 代表弧的權(quán)集。這里我們考慮和每條弧關(guān)聯(lián)著兩個(gè)權(quán)值（也可以關(guān)聯(lián)著多個(gè)) ，對圖 G 中的每一條邊 e i , j ，相應(yīng)的權(quán)向量 W ij (W ij1 ,Wij2 ) 。在實(shí)際問題中分量有相應(yīng)的物理量對應(yīng)，如 Qos 路由問題中每條鏈路可以給出帶寬、 時(shí)延、代價(jià)，丟包率等，交通問題中每條弧對應(yīng)著運(yùn)行的時(shí)間和費(fèi)用等。在實(shí)際應(yīng)用中，由于各種原因，權(quán)向量 Wij 的每個(gè)分量并不是確定的，可能部分不確定或都不確定。我們令權(quán)向量 Wij( ij ,c ij ) , 分

6、量ij 為隨機(jī)變量 , c ij 勺為確定的量。實(shí)際上這樣的網(wǎng)絡(luò)是存在的，如交通網(wǎng)絡(luò)中兩地的運(yùn)輸費(fèi)用是確定的但運(yùn)行時(shí)間可能不確定; 網(wǎng)絡(luò)路由中的丟包率是隨機(jī)的但是其他的量可能是確定的。在有些情況下，隨機(jī)變量ij 可能服從某種分布函數(shù)，可以為正態(tài)分布、均勻分布等等。如當(dāng)服從正態(tài)分布時(shí)，可以記為ij N ( ij ,2ij) ; 在另外一些情況下，隨機(jī)變量ij 可能無法獲得它的準(zhǔn)確分布函數(shù)，只能根據(jù)先前經(jīng)驗(yàn)獲得或估計(jì)其概率。由于在無圈網(wǎng)絡(luò)G （ V，A ）中，對于所有的i, jA ，所有的節(jié)點(diǎn)能夠重新編號使得i<j,這樣我令 1 和 n 分別表示路徑的起點(diǎn)和終點(diǎn)，則從節(jié)點(diǎn) 1 到 n 的一條

7、路 P 的權(quán)向量定義為P 中所有邊的權(quán)向量之和，記為W(P)Wij(ij ,c ij )(i,j)P(i,j) P(i,j)P有約束的最短路問題就是對于給定的約束C ，要在所有從 1 到 n 的所有路徑中，求一條路徑使得ij 最小且c ijC ，設(shè)決策變量為xij ，(i, j)P(i, j) P用下面的方法來表示一條路徑x xij | i, jE-其中 xij 1 表示弧 i , j 包含在該路徑中，xij0 表示弧 i, j 不包含在該 xij路徑中，容易證明在有向無圈圖中x |i , jA 是一條從節(jié)點(diǎn)1 到節(jié)點(diǎn) n 的路，當(dāng)且僅當(dāng)1i1xijx ji02 in 1(i, j) E( j

8、 ,i ) E1in記 ij | i , jA，那么路 x 長度（目標(biāo)函數(shù)）就可以寫成為f ( x, )ij xij(i, j) E優(yōu)化的目標(biāo)是使f ( x, ) 最小。如果ij 為確定的數(shù)，則求f (x,) 的最小值是有定義的，但i 是隨機(jī)變量時(shí)，導(dǎo)致目標(biāo)函數(shù)f ( x, ) 也為隨機(jī)變j量，這樣求f ( x, ) 的最小值也就失去了意義。因此，我們有必要根據(jù)隨機(jī)理論知識， 對隨機(jī)條件下的最短路徑進(jìn)行定義，建立相關(guān)的數(shù)學(xué)模型。三、有約束的期望最短路徑模型的建立定義 1：設(shè) x, x 為圖 G 中從源節(jié)點(diǎn) 1 到目標(biāo)節(jié)點(diǎn) n 的不同路徑，若有E ( f( x, ) ) E (f (x , ,

9、) 則 稱期望條 件下路 x 比路 x 短，其 中E( f ( x,)稱)為 x 的期望路長。在實(shí)際應(yīng)用中境下的期望值模型決策者根據(jù)路徑長度的期望值來做決策，則考慮不確定環(huán)期望值模型是指在期望約束下，使目標(biāo)函數(shù)的期望值達(dá)到最優(yōu)。為了尋找期望的最短路徑，建立了最短路徑的期望值模型。min E f (x,)E(ij xij ) （3.1 ）(i, j)ESt-cij xijC（3.2）(i, j)P-1i1xijxji0 2 in 1 （ 3.3 ）(i, j) E( j ,i )E1inxij0,1其中 , 式 (3.1)為優(yōu)化目標(biāo)，即路的期望權(quán)值最小，亦即期望最短路;式 (3.2)為約束條件，

10、表示路權(quán)的第二分量不超過C; 式 (3.3)保證x xij | i , jE 為有向圖中節(jié)點(diǎn)1 到節(jié)點(diǎn) n 的一條路。四、有約束的期望最短路徑模型的求解通常情況下，不確定規(guī)劃模型由于包含有不確定函數(shù)而變得很難用傳統(tǒng)的方法來求解。我們這里介紹一種結(jié)合隨機(jī)模擬方法和遺傳算法的混合智能算法來求解以上建立的模型。4.1計(jì)算不確定函數(shù)的隨機(jī)模擬方法對于隨機(jī)不確定優(yōu)化模型，將其轉(zhuǎn)化為等價(jià)的確定性優(yōu)化模型是非常困難的.只有在一些特殊情況下才能做到，對一些較復(fù)雜的問題通常很難做到這一點(diǎn)。為了在起點(diǎn) 1 與終點(diǎn) n 之間的眾多路徑中搜索出滿足約束條件的最優(yōu)路徑，我們采用隨機(jī)模擬方法來計(jì)算最短路問題中的不確定函數(shù)

11、. 隨機(jī)模擬 ( 也稱 Monte Carlo模擬 )是隨機(jī)系統(tǒng)建模中刻畫抽樣試驗(yàn)的一門技術(shù), 它主要依據(jù)概率分布對隨機(jī)變量進(jìn)行抽樣。雖然模擬技術(shù)只給出統(tǒng)計(jì)估計(jì)而非精確結(jié)果, 且應(yīng)用其研究問題需花費(fèi)大量的計(jì)算時(shí)間 , 但對那些無法得到解析結(jié)果的復(fù)雜問題來說 , 這種手段可能是惟一的有效的工具。隨機(jī)模擬的基本思想是根據(jù)問題建立一個(gè)概率模型， 通過某種用數(shù)字進(jìn)行的假象試驗(yàn)得到抽樣值，然后進(jìn)行統(tǒng)計(jì)處理， 將結(jié)果作為問題的解。 隨機(jī)模擬處理問題的基本-步驟是 : 構(gòu)造概率統(tǒng)計(jì)模型; 定義隨機(jī)變量; 通過模擬獲得子樣 ; 統(tǒng)計(jì)計(jì)算。隨機(jī)模擬主要依據(jù)分布函數(shù)或經(jīng)驗(yàn)分布對隨機(jī)變量進(jìn)行抽樣，它的理論基礎(chǔ)是大數(shù)

12、定理。 下面介紹計(jì)算最短路徑中不確定函數(shù)的隨機(jī)模擬步驟：模擬不確定函數(shù): U1 : xE f (x, )首先根據(jù)隨機(jī)向量各分量的分布函數(shù)從樣本空間產(chǎn)生樣本k , k 1, 2,.,N ，由強(qiáng)大數(shù)定律可知，當(dāng)n時(shí)Nf (x,k )k 1E f ( x,)NN因此只要 N 充分大， (f (x, k )N 就可以用來作為E f ( x, ) 的估計(jì)值。k 1這樣設(shè)計(jì)求 E f ( x, ) 的隨機(jī)模擬方法如下：步驟 1. 設(shè) L0步驟 2. 根據(jù)各條弧上的隨機(jī)變量的分布函數(shù)產(chǎn)生樣本( 1 , 2 ,., m )步驟 3. LL f( x, )步驟 4.重復(fù)步驟 2和3共N次步驟 5. E f (

13、x, )L/ N4.2遺傳算法遺傳算法是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法。在解決復(fù)雜的全局優(yōu)化問題方面，過去 30 年中 , 遺傳算法在解決復(fù)雜的全局優(yōu)化問題方面得到了成功的應(yīng)用, 并受到了人們的廣泛關(guān)注。在優(yōu)化問題中，如果目標(biāo)函數(shù)是多峰的，或者搜索空間不規(guī)則，很容易在-局部最優(yōu)解附近徘徊。這就要求所使用的算法必須具有高度的魯棒性，-以避免在局部最優(yōu)解附近徘徊, 而遺傳算法的優(yōu)點(diǎn)恰好在于全局搜索。其主要特點(diǎn)是群體搜索策略和群體中個(gè)體之間的信息交換, 搜索過程對系統(tǒng)模型的依賴較少尤其適用于處理傳統(tǒng)搜索方法難以解決的復(fù)雜的和非線性問題。另外, 遺傳算法本身并不要求對優(yōu)化問題的性質(zhì)作一些深入

14、的數(shù)學(xué)分析, 從而對那些不太熟悉數(shù)學(xué)理論和算法的使用者來說 , 無疑是方便的。自Holland3用遺傳算法來解決組合問題以來，由于該算法的隨機(jī)搜索方法，己經(jīng)被應(yīng)用到通訊、工業(yè)工程等很多領(lǐng)域，得到了各界學(xué)者的廣泛研究4 ，5 。為了求解不確定環(huán)境下的最短路問題模型，我們利用遺傳算法來求各種準(zhǔn)則下的最優(yōu)路徑，采用如下的路徑的表示方法、初始化過程和遺傳算子。4.2.1 遺傳表示選擇所求解問題解的一種合適的表示形式是用遺傳算法解決問題的基礎(chǔ)。因此對于特定的問題實(shí)例, 需要對問題進(jìn)行仔細(xì)分析, 才能準(zhǔn)確表示問題的實(shí)質(zhì)和設(shè)計(jì)該問題的遺傳算子。根據(jù)網(wǎng)絡(luò)圖中最短路的特點(diǎn)和遺傳算法的編碼原則, 本文介紹的遺傳表

15、示方法是利用向量P ( 1, 2 ,., k ) 作為染色體表示圖 G 從節(jié)點(diǎn) 1 到節(jié)點(diǎn) n 的一條路徑。因?yàn)椴煌穆窂桨ú煌墓?jié)點(diǎn)和弧，所以染色體的長度是不固定的。如果 ( 1, 2 ,., k ) 表示從節(jié)點(diǎn) 1 到節(jié)點(diǎn) n 的路徑，則有(1, 1 )A,( 1, 2 )A,.,(k 1 , k )A( k , n)A 。我們給出下面的定義，-1,如果 i 1, j11,如果存在 l 使得 i=l , jl1x ij1,如果 ik , jn0,其它對于所有的i, jA。很容易驗(yàn)證按照這種方式獲得的 xij | i , jA 從節(jié)點(diǎn) 1 到節(jié)點(diǎn) n 的一條路徑，我們可以按照下面的過程獲得

16、一條染色體。4.2.2染色體的初始化初始群體的創(chuàng)建有兩種方式: 隨機(jī)初始化和啟發(fā)式初始化。為了獲得一條可行的染色體，本文介紹采用啟發(fā)式染色體初始化的步驟:步驟 1. 設(shè) l=0 ， 0 1步驟 2.隨機(jī)產(chǎn)生 m 使得l，A 。（m）步驟 3.ll+1, lm 。步驟 4.重復(fù)步驟 2 和步驟 3 直到 : ln 。步驟 5.獲得一條染色體(1 , 2 ,., l 1 ) 。4.2.3遺傳算子在遺傳算法中，遺傳算子模擬生物的遺傳過程產(chǎn)生新的后代，在遺傳算法中起著重要的作用5 。在我們的算法中，交叉算子、變異操作以及選擇過程設(shè)計(jì)如下。4.2.4染色體的交叉交叉操作是由一對父代染色體通過交換其部分基

17、因, 從而形成兩個(gè)新的個(gè)體 , 交叉算子扮演著在當(dāng)前搜索區(qū)域內(nèi)尋找性能更佳的個(gè)體這樣一個(gè)角色。交叉方法一般有單點(diǎn)交叉、多點(diǎn)交叉、均勻交叉和算術(shù)交叉等方法 . 針對節(jié)點(diǎn)序列編碼及網(wǎng)絡(luò)路徑的特點(diǎn), 本文介紹單點(diǎn)-交叉。交叉方法如下：設(shè)P1( 1 , 2 ,., k ),P2( 1, 2 ,., k ) 為兩條染色體。 .在這兩條染色體中選擇一個(gè)相同的節(jié)點(diǎn)，如果在兩條染色體中有共同的節(jié)點(diǎn)，則隨機(jī)地選擇一個(gè)，譬如ii 。則我們可以得到下面的兩條新的染色體 :( 1, 2 ,., i , i 1,., k ),( 1 , 2 ,., i , i 1 ,., k )顯然這兩條新的染色體也是從節(jié)點(diǎn)1 到節(jié)點(diǎn)

18、二的一條可行路徑。如果兩條染色體沒有共同的節(jié)點(diǎn)，則不進(jìn)行交叉。4.2.5 染色體變異變異按照某個(gè)特定概率Pm 隨機(jī)改變?nèi)后w中個(gè)體的局部基因位,將算法引入新的解空間進(jìn)行搜索。它本身是一種局部隨機(jī)搜索技術(shù),與選擇、交叉結(jié)合在一起保證了遺傳算法的有效性, 使遺傳算法具有局部的隨機(jī)搜索能力, 同時(shí)使遺傳算法保持群體的多樣性。對于用路徑表示的染色體, 變異操作把連接節(jié)點(diǎn)組成的路徑塊作為基因塊，實(shí)現(xiàn)染色體中的基因塊變異. 具體方法如下 :設(shè) P( 1 , 2,., k ) 為一條染色體，我們設(shè)計(jì)如下的變異操作過程。從 1,2,.,k 中隨機(jī)地產(chǎn)生一個(gè)整數(shù)，記為i 。則我們利用染色體初始化的方法從節(jié)點(diǎn)i 到

19、 n 產(chǎn)生一條路徑( i 1,.,k ) ，則可以產(chǎn)生一條新的染色體( 12 ,.i , i 1 ,.,k ) 。, ., 4.2.6 選擇過程一般而言，選擇的過程是一種基于適應(yīng)度的優(yōu)勝劣汰的過程，當(dāng)前群體中適應(yīng)度高的個(gè)體具有更高的機(jī)會(huì)進(jìn)入下一代群體。選擇壓力是指最佳個(gè)體選中的概率與平均選中概率的比值，選擇壓力過高或過-低對算法的性能都有較大的影響。本文介紹使用輪盤賭選擇方法來選擇染色體。每次選擇一條染色體，直到獲得pop_size 條染色體為止。4.3混合智能算法結(jié)合隨機(jī)模擬方法和遺傳算法相結(jié)合的混合智能算法6 一般步驟：步驟 1. 隨機(jī)產(chǎn)生 pop_size 條染色體 Pk ， k1,2,

20、.,pop_size。步驟 2. 利用我們所設(shè)計(jì)的隨機(jī)模擬或模糊模擬對每一條染色體計(jì)算其目標(biāo)函數(shù)值。步驟3. 計(jì)算每一條染色體適應(yīng)值。我們利用基于序的評價(jià)函數(shù)為Eval(P) ia(1 a) i 1 ,i1,2,.,pop_size,其中，假設(shè)染色體己經(jīng)根據(jù)他們的目標(biāo)函數(shù)值從好到壞排列好，a(0,1) 為遺傳算法中的參數(shù)。步驟 4. 選擇染色體。步 驟5. 利 用 上 面 提 到 的 交 叉 和 變 異 操 作 更 新 染 色 體 Pk ，k1,2,.,pop_size。步驟 6. 重復(fù)步驟 2 到步驟 5 直到滿足結(jié)束條件。步驟 7. 返回最好的染色體P*( 1 , 2,., k ) 。五、小結(jié)本文介紹了一種不確定條件下最短路徑問題解決方法，對不確定條件下最短路徑問題，根據(jù)不同的決策要求，建立有約束的期望最短路徑模型，由于模型中包括不確定參數(shù)，因此，不能利用傳統(tǒng)的方法來求解，本文介紹一種結(jié)合隨機(jī)模擬方法和遺傳算法的混合智能算法來進(jìn)行求解，該算法利用隨機(jī)模擬方法計(jì)算最短路徑問題的不確定函-數(shù)，將期望最短路徑模型轉(zhuǎn)化為等價(jià)的確定性優(yōu)化模型，然后利用遺傳算法搜索滿足約束條件的最優(yōu)路徑。參考文獻(xiàn)1Dubois D, Prade H. Fuzzy Sets an