隨機型流量網(wǎng)絡中若干問題的模型及其算法的研究.pdf

1、網(wǎng)絡流理論是圖論的一個重要分支，是研究網(wǎng)絡上相關優(yōu)化問題的理論和方法。1956年，L．R．福特和 D．R．富爾克森等人給出了解決在給定的網(wǎng)絡上尋求兩點間最大運輸量這類問題的算法，從而奠定了網(wǎng)絡流理論的基礎。網(wǎng)絡流理論發(fā)展至今，已普遍應用于通訊、運輸、電力、工程規(guī)劃、任務分派等眾多領域。為了更好的解決現(xiàn)實中的問題，網(wǎng)絡流理論也在不斷發(fā)展中，先后出現(xiàn)了具有增益的流、分派與匹配、網(wǎng)絡優(yōu)化的拉格朗日松弛法、多商品流、網(wǎng)絡流的分解與合并等新的理論

2、和方法。但以上研究都是在網(wǎng)絡參數(shù)和拓撲結構固定的網(wǎng)絡上進行的優(yōu)化，而實際環(huán)境中的網(wǎng)絡系統(tǒng)受多種因素影響往往會表現(xiàn)出隨機性，所以傳統(tǒng)網(wǎng)絡流理論在具體應用時與實際情況會有一定的偏差，如果能在隨機環(huán)境下對網(wǎng)絡流進行優(yōu)化，對提高網(wǎng)絡流理論的實用性和針對性均有重要意義，這個問題已越來越引起關注。 目前主要從3個方面將隨機因素引入網(wǎng)絡流理論：1.令網(wǎng)絡的權值為隨機變量；2.假設網(wǎng)絡的拓撲結構為隨機的；3.假設網(wǎng)絡中各邊的容量為隨機變量，提出

3、了隨機型流量網(wǎng)絡(Stochastic Flow Network)的概念。隨機型流量網(wǎng)絡上的網(wǎng)絡流理論的研究目前處于起步階段，研究主要集中在：設計算法尋找網(wǎng)絡流在網(wǎng)絡容量狀態(tài)X下的最大流V(X)能滿足接收端需求d的網(wǎng)絡容量狀態(tài)的臨界點d—MCs或d-MPs，并根據(jù)這些點計算隨機型流量網(wǎng)絡的可靠性。但當隨機型流量網(wǎng)絡的容量處于非臨界狀態(tài)時，對網(wǎng)絡流進行分配優(yōu)化的研究還較少見，論文中將針對不同問題選取特定優(yōu)化目標，研究網(wǎng)絡流不處于最大流狀態(tài)

4、V(X)時的優(yōu)化問題。論文主要研究了以下幾方面的內(nèi)容： 1.以目前使用較多的兩種隨機型流量網(wǎng)絡模型(網(wǎng)絡節(jié)點可靠，單商品流，多發(fā)送端，多接收端的網(wǎng)絡模型和網(wǎng)絡節(jié)點不可靠，多商品流，多發(fā)送端，多接收端的網(wǎng)絡模型)為基礎，研究當網(wǎng)絡流不處于最大流狀態(tài)V(X)時如何對網(wǎng)絡流流量進行分配優(yōu)化。選定滿足接收端需求的網(wǎng)絡流可靠性為目標，建立整數(shù)隨機規(guī)劃模型。針對模型的特點，設計相應的算子，采用遺傳算法對優(yōu)化模型進行求解，并與使用Lingo軟

5、件方法求解得到的結果進行比較，分析兩種求解方法的優(yōu)缺點及其適用的問題。 2.文中將網(wǎng)絡流傳輸時間和成本從約束條件轉(zhuǎn)化為整體優(yōu)化目標，并結合網(wǎng)絡流可靠性這一主要目標，研究隨機型流量網(wǎng)絡上網(wǎng)絡流的多目標優(yōu)化問題。為求解建立的多目標優(yōu)化模型，對NSGA-Ⅱ方法做出如下改進：改進2-聯(lián)賽選擇算子的比較規(guī)則，將模擬2進制交叉算子改進為單點復合交叉算子，改進精英保留策略，使用改進后的算法對模型進行求解，經(jīng)過測試，得到的結果從多方面優(yōu)于原NS

6、GA-Ⅱ算法。 3.已有的隨機型流量網(wǎng)絡可靠性的算法，由于涉及到最大流最小割原理和Ford-Fulkerson算法等傳統(tǒng)網(wǎng)絡流理論，故不得不假設隨機型流量網(wǎng)絡中的所有變量為離散型變量。本文中由于采用了單目標/多目標遺傳算法對網(wǎng)絡流進行優(yōu)化，故不受上面的限制。因此文中擴展隨機型流量網(wǎng)絡的容量為連續(xù)型隨機變量，各條邊上分配的網(wǎng)絡流量為連續(xù)實數(shù)，建立連續(xù)型的多目標網(wǎng)絡流優(yōu)化模型，為了處理包含連續(xù)型變量的等式約束，對等式約束增加逼近參數(shù)

7、，將等式約束分解為兩條不等式約束以逼近方式處理。采用改進后的NSGA-II對處理后的優(yōu)化模型進行求解。通過測試，可快速求出連續(xù)型多目標優(yōu)化模型的Pareto前沿。 4.論文對網(wǎng)絡中各節(jié)點包含隨機需求的網(wǎng)絡流多目標優(yōu)化問題進行了研究。針對這種復雜隨機情況下的網(wǎng)絡流優(yōu)化問題建立了機會約束多目標隨機規(guī)劃模型。對建立的隨機規(guī)劃模型進行預處理，將部分以置信度表示的約束條件轉(zhuǎn)化為對應的確定性等價約束。采用隨機模擬方法對優(yōu)化模型的其余部分進行