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

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

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

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

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

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

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

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