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

1、關(guān)于不確定條件下的最短路徑問題的研究摘 要：在利用最短路模型解決問題時(shí)，由于天氣、運(yùn)輸條件以及時(shí)間段等原因，網(wǎng)絡(luò)中弧的權(quán)值經(jīng)常很難給出確切的值。對(duì)傳統(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í)不確定條件下的最短路徑問題的解決方法，開拓了思路，對(duì)自己運(yùn)用系統(tǒng)思維解決自己研究方向的問題有很大的啟發(fā)。關(guān)鍵字：網(wǎng)絡(luò)優(yōu)化；不確定最短路徑問題；系統(tǒng)思維一、引言最短路徑問題是指在網(wǎng)絡(luò)中尋找節(jié)

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

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

4、的最大、最小值算子和Zadeh擴(kuò)展原理，來求模糊最短路的長度，但由于模糊運(yùn)算的特點(diǎn)，經(jīng)過多次運(yùn)算得到的模糊長度有時(shí)候并不能和某條路徑對(duì)應(yīng)上。有的學(xué)者根據(jù)多準(zhǔn)則決策理論求非被支配解路徑集合，但當(dāng)網(wǎng)絡(luò)較大時(shí)，該集合就會(huì)很大，對(duì)于決策者從中選擇滿意的方案就會(huì)很困難。因此，在不確定條件下建立模型給出算法，為決策者提供有價(jià)值的方案，具有重要的意義。二、問題描述為了對(duì)最短路問題進(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代表弧集,每個(gè)弧使用節(jié)點(diǎn)的有序?qū)肀硎?，其中，并假設(shè)從節(jié)點(diǎn)i到節(jié)點(diǎn)j

5、之間只有一條有向弧。代表弧的權(quán)集。這里我們考慮和每條弧關(guān)聯(lián)著兩個(gè)權(quán)值（也可以關(guān)聯(lián)著多個(gè))，對(duì)圖G中的每一條邊，相應(yīng)的權(quán)向量。在實(shí)際問題中分量有相應(yīng)的物理量對(duì)應(yīng)，如Qos路由問題中每條鏈路可以給出帶寬、時(shí)延、代價(jià)，丟包率等，交通問題中每條弧對(duì)應(yīng)著運(yùn)行的時(shí)間和費(fèi)用等。在實(shí)際應(yīng)用中，由于各種原因，權(quán)向量的每個(gè)分量并不是確定的，可能部分不確定或都不確定。我們令權(quán)向量,分量為隨機(jī)變量,勺為確定的量。實(shí)際上這樣的網(wǎng)絡(luò)是存在的，如交通網(wǎng)絡(luò)中兩地的運(yùn)輸費(fèi)用是確定的但運(yùn)行時(shí)間可能不確定;網(wǎng)絡(luò)路由中的丟包率是隨機(jī)的但是其他的量可能是確定的。在有些情況下，隨機(jī)變量可能服從某種分布函數(shù)，可以為正態(tài)分布、均勻分布等等。

6、如當(dāng)服從正態(tài)分布時(shí)，可以記為;在另外一些情況下，隨機(jī)變量可能無法獲得它的準(zhǔn)確分布函數(shù)，只能根據(jù)先前經(jīng)驗(yàn)獲得或估計(jì)其概率。由于在無圈網(wǎng)絡(luò)G（V，A）中，對(duì)于所有的，所有的節(jié)點(diǎn)能夠重新編號(hào)使得i<j,這樣我令1和n分別表示路徑的起點(diǎn)和終點(diǎn)，則從節(jié)點(diǎn)1到n的一條路P的權(quán)向量定義為P中所有邊的權(quán)向量之和，記為有約束的最短路問題就是對(duì)于給定的約束C，要在所有從1到n的所有路徑中，求一條路徑使得最小且，設(shè)決策變量為，用下面的方法來表示一條路徑其中表示弧包含在該路徑中，表示弧不包含在該路徑中，容易證明在有向無圈圖中是一條從節(jié)點(diǎn)1到節(jié)點(diǎn)n的路，當(dāng)且僅當(dāng)記，那么路長度（目標(biāo)函數(shù)）就可以寫成為優(yōu)化的目標(biāo)是使

7、最小。如果為確定的數(shù)，則求的最小值是有定義的，但是隨機(jī)變量時(shí)，導(dǎo)致目標(biāo)函數(shù)也為隨機(jī)變量，這樣求的最小值也就失去了意義。因此，我們有必要根據(jù)隨機(jī)理論知識(shí)，對(duì)隨機(jī)條件下的最短路徑進(jìn)行定義，建立相關(guān)的數(shù)學(xué)模型。三、有約束的期望最短路徑模型的建立定義1：設(shè)為圖G中從源節(jié)點(diǎn)1到目標(biāo)節(jié)點(diǎn)n的不同路徑，若有,則稱期望條件下路比路短，其中稱為的期望路長。在實(shí)際應(yīng)用中境下的期望值模型決策者根據(jù)路徑長度的期望值來做決策，則考慮不確定環(huán)期望值模型是指在期望約束下，使目標(biāo)函數(shù)的期望值達(dá)到最優(yōu)。為了尋找期望的最短路徑，建立了最短路徑的期望值模型。 （3.1） （3.2） （3.3）其中,式(3.1)為優(yōu)化目標(biāo)，即路的期

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

9、定函數(shù). 隨機(jī)模擬(也稱Monte Carlo模擬)是隨機(jī)系統(tǒng)建模中刻畫抽樣試驗(yàn)的一門技術(shù),它主要依據(jù)概率分布對(duì)隨機(jī)變量進(jìn)行抽樣。雖然模擬技術(shù)只給出統(tǒng)計(jì)估計(jì)而非精確結(jié)果,且應(yīng)用其研究問題需花費(fèi)大量的計(jì)算時(shí)間,但對(duì)那些無法得到解析結(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)分布對(duì)隨機(jī)變量進(jìn)行抽樣，它的理論基礎(chǔ)是大數(shù)定理。下面介紹計(jì)算最短路徑中不確定

10、函數(shù)的隨機(jī)模擬步驟：模擬不確定函數(shù):首先根據(jù)隨機(jī)向量各分量的分布函數(shù)從樣本空間產(chǎn)生樣本，由強(qiáng)大數(shù)定律可知，當(dāng)時(shí) 因此只要N充分大，就可以用來作為的估計(jì)值。這樣設(shè)計(jì)求的隨機(jī)模擬方法如下：步驟1.設(shè)L0步驟2.根據(jù)各條弧上的隨機(jī)變量的分布函數(shù)產(chǎn)生樣本步驟3.步驟4.重復(fù)步驟2和3共N次步驟5.4.2 遺傳算法遺傳算法是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法。在解決復(fù)雜的全局優(yōu)化問題方面，過去30年中,遺傳算法在解決復(fù)雜的全局優(yōu)化問題方面得到了成功的應(yīng)用,并受到了人們的廣泛關(guān)注。在優(yōu)化問題中，如果目標(biāo)函數(shù)是多峰的，或者搜索空間不規(guī)則，很容易在局部最優(yōu)解附近徘徊。這就要求所使用的算法必須具有高度的魯

11、棒性，以避免在局部最優(yōu)解附近徘徊,而遺傳算法的優(yōu)點(diǎn)恰好在于全局搜索。其主要特點(diǎn)是群體搜索策略和群體中個(gè)體之間的信息交換,搜索過程對(duì)系統(tǒng)模型的依賴較少尤其適用于處理傳統(tǒng)搜索方法難以解決的復(fù)雜的和非線性問題。另外,遺傳算法本身并不要求對(duì)優(yōu)化問題的性質(zhì)作一些深入的數(shù)學(xué)分析,從而對(duì)那些不太熟悉數(shù)學(xué)理論和算法的使用者來說,無疑是方便的。自Holland3用遺傳算法來解決組合問題以來，由于該算法的隨機(jī)搜索方法，己經(jīng)被應(yīng)用到通訊、工業(yè)工程等很多領(lǐng)域，得到了各界學(xué)者的廣泛研究4，5。為了求解不確定環(huán)境下的最短路問題模型，我們利用遺傳算法來求各種準(zhǔn)則下的最優(yōu)路徑，采用如下的路徑的表示方法、初始化過程和遺傳算子。

12、4.2.1遺傳表示選擇所求解問題解的一種合適的表示形式是用遺傳算法解決問題的基礎(chǔ)。因此對(duì)于特定的問題實(shí)例,需要對(duì)問題進(jìn)行仔細(xì)分析,才能準(zhǔn)確表示問題的實(shí)質(zhì)和設(shè)計(jì)該問題的遺傳算子。根據(jù)網(wǎng)絡(luò)圖中最短路的特點(diǎn)和遺傳算法的編碼原則,本文介紹的遺傳表示方法是利用向量作為染色體表示圖G從節(jié)點(diǎn)1到節(jié)點(diǎn)n的一條路徑。因?yàn)椴煌穆窂桨ú煌墓?jié)點(diǎn)和弧，所以染色體的長度是不固定的。如果表示從節(jié)點(diǎn)1到節(jié)點(diǎn)n的路徑，則有。我們給出下面的定義，對(duì)于所有的。很容易驗(yàn)證按照這種方式獲得的從節(jié)點(diǎn)1到節(jié)點(diǎn)n的一條路徑，我們可以按照下面的過程獲得一條染色體。4.2.2 染色體的初始化初始群體的創(chuàng)建有兩種方式:隨機(jī)初始化和啟發(fā)式初始

13、化。為了獲得一條可行的染色體，本文介紹采用啟發(fā)式染色體初始化的步驟:步驟1.設(shè)l=0，步驟2.隨機(jī)產(chǎn)生m使得。步驟3.。步驟4.重復(fù)步驟2和步驟3直到:。步驟5.獲得一條染色體。4.2.3 遺傳算子 在遺傳算法中，遺傳算子模擬生物的遺傳過程產(chǎn)生新的后代，在遺傳算法中起著重要的作用5。在我們的算法中，交叉算子、變異操作以及選擇過程設(shè)計(jì)如下。4.2.4 染色體的交叉交叉操作是由一對(duì)父代染色體通過交換其部分基因,從而形成兩個(gè)新的個(gè)體,交叉算子扮演著在當(dāng)前搜索區(qū)域內(nèi)尋找性能更佳的個(gè)體這樣一個(gè)角色。交叉方法一般有單點(diǎn)交叉、多點(diǎn)交叉、均勻交叉和算術(shù)交叉等方法.針對(duì)節(jié)點(diǎn)序列編碼及網(wǎng)絡(luò)路徑的特點(diǎn),本文介紹單點(diǎn)

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

15、塊變異.具體方法如下:設(shè)為一條染色體，我們?cè)O(shè)計(jì)如下的變異操作過程。從中隨機(jī)地產(chǎn)生一個(gè)整數(shù)，記為i。則我們利用染色體初始化的方法從節(jié)點(diǎn)到n產(chǎn)生一條路徑，則可以產(chǎn)生一條新的染色體。4.2.6 選擇過程一般而言，選擇的過程是一種基于適應(yīng)度的優(yōu)勝劣汰的過程，當(dāng)前群體中適應(yīng)度高的個(gè)體具有更高的機(jī)會(huì)進(jìn)入下一代群體。選擇壓力是指最佳個(gè)體選中的概率與平均選中概率的比值，選擇壓力過高或過低對(duì)算法的性能都有較大的影響。本文介紹使用輪盤賭選擇方法來選擇染色體。每次選擇一條染色體，直到獲得條染色體為止。4.3 混合智能算法結(jié)合隨機(jī)模擬方法和遺傳算法相結(jié)合的混合智能算法6一般步驟：步驟1.隨機(jī)產(chǎn)生條染色體，。步驟2.利

16、用我們所設(shè)計(jì)的隨機(jī)模擬或模糊模擬對(duì)每一條染色體計(jì)算其目標(biāo)函數(shù)值。步驟3.計(jì)算每一條染色體適應(yīng)值。我們利用基于序的評(píng)價(jià)函數(shù)為其中，假設(shè)染色體己經(jīng)根據(jù)他們的目標(biāo)函數(shù)值從好到壞排列好，為遺傳算法中的參數(shù)。步驟4.選擇染色體。步驟5.利用上面提到的交叉和變異操作更新染色體，。步驟6.重復(fù)步驟2到步驟5直到滿足結(jié)束條件。步驟7.返回最好的染色體。五、小結(jié)本文介紹了一種不確定條件下最短路徑問題解決方法，對(duì)不確定條件下最短路徑問題，根據(jù)不同的決策要求，建立有約束的期望最短路徑模型，由于模型中包括不確定參數(shù)，因此，不能利用傳統(tǒng)的方法來求解，本文介紹一種結(jié)合隨機(jī)模擬方法和遺傳算法的混合智能算法來進(jìn)行求解，該算法

17、利用隨機(jī)模擬方法計(jì)算最短路徑問題的不確定函數(shù)，將期望最短路徑模型轉(zhuǎn)化為等價(jià)的確定性優(yōu)化模型，然后利用遺傳算法搜索滿足約束條件的最優(yōu)路徑。參考文獻(xiàn)1 Dubois D, Prade H. Fuzzy Sets and Systems: Theory and Applications. New York: Academic Press, 19802 Dubois D, Prade H. Systems of linear fuzzy constraints. Fuzzy Sets and Systems 1980, 3: 37-83 Holland J. Adaptatin in Natural and Artificial System. University of Michigan Press, Ann Arbor, MI, 19754 Gen M, Cheng R. Genetic Algorithms and Engineer Optimization. New York: John Wiley and Sons, 20005 Hsinghua C, Premkumar G, Chu C. Genetic algorith