網(wǎng)絡(luò)流理論是圖論的一個重要分支,是研究網(wǎng)絡(luò)上相關(guān)優(yōu)化問題的理論和方法。1956年,L.R.福特和D.R.富爾克森等人給出了解決在給定的網(wǎng)絡(luò)上尋求兩點間最大運輸量這類問題的算法,從而奠定了網(wǎng)絡(luò)流理論的基礎(chǔ)。網(wǎng)絡(luò)流理論發(fā)展至今,已普遍應(yīng)用于通訊、運輸、電力、工程規(guī)劃、任務(wù)分派等眾多領(lǐng)域。為了更好的解決現(xiàn)實中的問題,網(wǎng)絡(luò)流理論也在不斷發(fā)展中,先后出現(xiàn)了具有增益的流、分派與匹配、網(wǎng)絡(luò)優(yōu)化的拉格朗日松弛法、多商品流、網(wǎng)絡(luò)流的分解與合并等新的理論和方法。但以上研究都是在網(wǎng)絡(luò)參數(shù)和拓撲結(jié)構(gòu)固定的網(wǎng)絡(luò)上進行的優(yōu)化,而實際環(huán)境中的網(wǎng)絡(luò)系統(tǒng)受多種因素影響往往會表現(xiàn)出隨機性,所以傳統(tǒng)網(wǎng)絡(luò)流理論在具體應(yīng)用時與實際情況會有一定的偏差,如果能在隨機環(huán)境下對網(wǎng)絡(luò)流進行優(yōu)化,對提高網(wǎng)絡(luò)流理論的實用性和針對性均有重要意義,這個問題已越來越引起關(guān)注。 目前主要從3個方面將隨機因素引入網(wǎng)絡(luò)流理論:1.令網(wǎng)絡(luò)的權(quán)值為隨機變量;2.假設(shè)網(wǎng)絡(luò)的拓撲結(jié)構(gòu)為隨機的;3.假設(shè)網(wǎng)絡(luò)中各邊的容量為隨機變量,提出了隨機型流量網(wǎng)絡(luò)(Stochastic Flow Network)的概念。隨機型流量網(wǎng)絡(luò)上的網(wǎng)絡(luò)流理論的研究目前處于起步階段,研究主要集中在:設(shè)計算法尋找網(wǎng)絡(luò)流在網(wǎng)絡(luò)容量狀態(tài)X下的最大流V(X)能滿足接收端需求d的網(wǎng)絡(luò)容量狀態(tài)的臨界點d-MCs或d-MPs,并根據(jù)這些點計算隨機型流量網(wǎng)絡(luò)的可靠性。但當(dāng)隨機型流量網(wǎng)絡(luò)的容量處于非臨界狀態(tài)時,對網(wǎng)絡(luò)流進行分配優(yōu)化的研究還較少見,論文中將針對不同問題選取特定優(yōu)化目標(biāo),研究網(wǎng)絡(luò)流不處于最大流狀態(tài)V(X)時的優(yōu)化問題。論文主要研究了以下幾方面的內(nèi)容: 1.以目前使用較多的兩種隨機型流量網(wǎng)絡(luò)模型(網(wǎng)絡(luò)節(jié)點可靠,單商品流,多發(fā)送端,多接收端的網(wǎng)絡(luò)模型和網(wǎng)絡(luò)節(jié)點不可靠,多商品流,多發(fā)送端,多接收端的網(wǎng)絡(luò)模型)為基礎(chǔ),研究當(dāng)網(wǎng)絡(luò)流不處于最大流狀態(tài)V(X)時如何對網(wǎng)絡(luò)流流量進行分配優(yōu)化。選定滿足接收端需求的網(wǎng)絡(luò)流可靠性為目標(biāo),建立整數(shù)隨機規(guī)劃模型。針對模型的特點,設(shè)計相應(yīng)的算子,采用遺傳算法對優(yōu)化模型進行求解,并與使用Lingo軟件方法求解得到的結(jié)果進行比較,分析兩種求解方法的優(yōu)缺點及其適用的問題。 2.文中將網(wǎng)絡(luò)流傳輸時間和成本從約束條件轉(zhuǎn)化為整體優(yōu)化目標(biāo),并結(jié)合網(wǎng)絡(luò)流可靠性這一主要目標(biāo),研究隨機型流量網(wǎng)絡(luò)上網(wǎng)絡(luò)流的多目標(biāo)優(yōu)化問題。為求解建立的多目標(biāo)優(yōu)化模型,對NSGA-II方法做出如下改進:改進2-聯(lián)賽選擇算子的比較規(guī)則,將模擬2進制交叉算子改進為單點復(fù)合交叉算子,改進精英保留策略,使用改進后的算法對模型進行求解,經(jīng)過測試,得到的結(jié)果從多方面優(yōu)于原NSGA-II算法。 3.已有的隨機型流量網(wǎng)絡(luò)可靠性的算法,由于涉及到最大流最小割原理和Ford-Fulkerson算法等傳統(tǒng)網(wǎng)絡(luò)流理論,故不得不假設(shè)隨機型流量網(wǎng)絡(luò)中的所有變量為離散型變量。本文中由于采用了單目標(biāo)/多目標(biāo)遺傳算法對網(wǎng)絡(luò)流進行優(yōu)化,故不受上面的限制。因此文中擴展隨機型流量網(wǎng)絡(luò)的容量為連續(xù)型隨機變量,各條邊上分配的網(wǎng)絡(luò)流量為連續(xù)實數(shù),建立連續(xù)型的多目標(biāo)網(wǎng)絡(luò)流優(yōu)化模型,為了處理包含連續(xù)型變量的等式約束,對等式約束增加逼近參數(shù),將等式約束分解為兩條不等式約束以逼近方式處理。采用改進后的NSGA-II對處理后的優(yōu)化模型進行求解。通過測試,可快速求出連續(xù)型多目標(biāo)優(yōu)化模型的Pareto前沿。 4.論文對網(wǎng)絡(luò)中各節(jié)點包含隨機需求的網(wǎng)絡(luò)流多目標(biāo)優(yōu)化問題進行了研究。針對這種復(fù)雜隨機情況下的網(wǎng)絡(luò)流優(yōu)化問題建立了機會約束多目標(biāo)隨機規(guī)劃模型。對建立的隨機規(guī)劃模型進行預(yù)處理,將部分以置信度表示的約束條件轉(zhuǎn)化為對應(yīng)的確定性等價約束。采用隨機模擬方法對優(yōu)化模型的其余部分進行處理。結(jié)合前面提到的改進后的多目標(biāo)遺傳算法,提出一個基于隨機模擬的多目標(biāo)遺傳算法對機會約束隨機規(guī)劃模型進行求解。通過算例測試,可以求得優(yōu)化問題的Pareto解集。
【學(xué)位單位】：山東師范大學(xué)
【學(xué)位級別】：博士
【學(xué)位年份】：2008
【中圖分類】：N945.15
【部分圖文】：

圖 2.1.1 節(jié)點可靠的隨機型流量網(wǎng)絡(luò)通過一個實際的例子來測試提出的遺傳算法，假設(shè)有如圖節(jié)點可靠的隨機型流量網(wǎng)絡(luò)，有兩個發(fā)點 s1、s2，兩個接收運輸一種資源到接收點并要求滿足接收點的需求。網(wǎng)絡(luò)中各概率分布可以通過一些統(tǒng)計方法得到，本例中假設(shè)其概率分最大容量向量 M = (6,5,5,7,3,5,7,6,8,3,4,4,6,8)。假設(shè)發(fā)點2 分別服從均勻分布 U(5,25)、U(5,29)，收點的資源需求量d分布 N(8,0.72)、N(11,1.52)。本例中的 MPs 共 11 條，如下 5 , a},1,1,2 2 7 9MPs = {a , a , a},1,1,3 1 6 MPs = {a , a , a 6 14 , a , a},1,2,2 2 7 14MPs = {a , a , a},2,1,1 3 7 MPs = {a , a 4 8 13 9 , a , a , a},2,2,1 3 7 14MPs = {a , a , a},2,2,2 4 8 1MPs = {a , a , a

2.1.2 遺傳算法進化 500 代時的 3 次進化過程（從第 6 代到 450 代7 小結(jié)節(jié)以一個跨國公司物流運輸調(diào)度問題為例，研究了在多個收點、節(jié)點可靠的隨機型流量網(wǎng)絡(luò)上的網(wǎng)絡(luò)流優(yōu)化問題。采用了最小路集，使模型的復(fù)雜度降低，并將原始問題轉(zhuǎn)化為在各條最小路上進行并提出一個遺傳算法求解建立的優(yōu)化模型。相關(guān)決策者可以利用本立模型并求解，然后根據(jù)情況來指導(dǎo)物流運輸?shù)恼{(diào)度。

圖 2.2.1 兩個發(fā)點兩個收點的隨機型流量網(wǎng)絡(luò).1 所示的一個隨機型流量網(wǎng)絡(luò)，按要求從兩個發(fā)到接收點 t1、t2,并滿足接收點的需求。網(wǎng)絡(luò)中各布可以通過一些統(tǒng)計方法得到，本例中為便于eCp 取最大值eM 的概率為 0.9，取其它值的概率均M=(12,10,10,14,8,10,14,12,16,8,10,10,12,16,14,1源供給量1,1r 、1,2r 、2,1r 、2,2r 服從均勻分布 U(10,2，收點的資源需求量1,1d 、1,2d 、2,1d 、2,2d 分別服、N(8,1)、N(8,2.5)。本例中的 MPs 共 11 條，5a},1,1,2 1 15 6 18 9MPs = {a , a , a , a , a},1,1,3 2 MPs = {a , 6 18 14a , a , a},1,2,2 2 16 7 18MPs = {a , a , a , a a , a , a},MPs = {a , a , a , a , a ,

【參考文獻】

相關(guān)期刊論文 前6條

1 王芳,侯朝楨;用蒙特卡羅和Petri網(wǎng)方法估計隨機流網(wǎng)絡(luò)的可靠性[J];北京理工大學(xué)學(xué)報;2004年07期

2 孫偉平;周敬利;余勝生;;一類允許節(jié)點失效的多信息流隨機流量網(wǎng)絡(luò)的可靠度研究[J];計算機科學(xué);2003年11期

3 孫偉平;周敬利;余勝生;;計算隨機流量網(wǎng)絡(luò)可靠度的算法綜述[J];計算機科學(xué);2004年01期

4 孫偉平;周敬利;余勝生;;一類節(jié)點與弧的容量均有限制的隨機流量網(wǎng)絡(luò)可靠度的計算[J];計算機科學(xué);2004年02期

5 王芳,侯朝楨;一種計算隨機流網(wǎng)絡(luò)可靠性的新算法[J];通信學(xué)報;2004年01期

6 王芳,侯朝楨;一個估計隨機流網(wǎng)絡(luò)可靠性的新方法[J];小型微型計算機系統(tǒng);2005年05期

相關(guān)碩士學(xué)位論文 前2條

1 柳亞玲;隨機網(wǎng)絡(luò)的尋徑算法及應(yīng)用[D];大連理工大學(xué);2002年

2 崔曉婷;隨機網(wǎng)絡(luò)中國郵路問題算法研究[D];大連理工大學(xué);2006年

本文編號：2810335