基于概率仿真優(yōu)化方法的網(wǎng)絡(luò)分銷系統(tǒng)

黃健柏，黃 飛

(中南大學(xué) 商學(xué)院，長沙 410000)

仿真優(yōu)化就是在現(xiàn)代先進優(yōu)化理論的基礎(chǔ)上，采用計算機仿真技術(shù)來獲得待研究系統(tǒng)的一種較為優(yōu)化的決策[1]。仿真優(yōu)化已廣泛地應(yīng)用到各個領(lǐng)域：如自動控制、系統(tǒng)設(shè)計和仿真算法優(yōu)化等[2-4]。目前較為常用的仿真優(yōu)化方法有[5-8]：隨機優(yōu)化方法、基于梯度的方法、響應(yīng)曲面法及智能優(yōu)化方法。這些仿真優(yōu)化方法已被廣泛地應(yīng)用于諸多領(lǐng)域：如生產(chǎn)制造系統(tǒng)[9]、經(jīng)濟系統(tǒng)[10]。

1 概率仿真優(yōu)化方法

1.1 仿真重復(fù)次數(shù)的確定方法

對于大多數(shù)實際的仿真優(yōu)化問題來講，點xk處的響應(yīng)值不等同于它的適應(yīng)度值F(xk)，所以需要在點xk處進行多次仿真。在本文中，假設(shè)在點xk處進行p次仿真試驗，則多次仿真取平均值的計算方式如下：

這里，筆者采用以下方式來確定p的取值：

其中，pi表示在試驗點xi處需要進行重復(fù)仿真試驗的次數(shù)，m表示一個固定的參數(shù)，||·||表示計算向量的模，Xi表示第i個個體，X*表示當前種群中的最優(yōu)個體。

1.2 兩個個體的優(yōu)劣比較

在上述的公式(1)中，除非P的取值非常接近于正無窮，否則使用R(xk)來替代f(xk,w)都是不合適的。所以，很難采用一種精確的方法來比較R(xk)和R(xk+1)。筆者采用假設(shè)檢驗方法來嘗試構(gòu)造判斷兩個個體優(yōu)劣的方法。可構(gòu)造以下假設(shè)：

其中，R(xk)和R(x2)分別表示點x1和x2處所得到的平均響應(yīng)值，μ1和μ2分別表示點x1和x2處的實際適應(yīng)值。這樣就可在給定檢驗水平a下基于統(tǒng)計量R(x1)和R(x2)來對上述假設(shè)檢驗做出判斷。如果上述假設(shè)被拒絕，則，說明染色體以的置信水平水平優(yōu)于染色體。

1.3 多個個體的優(yōu)劣排序

設(shè)X1,X2,…，Xn分別表示當前種群中的n個個體，μ1,μ2,…，μn分別表示這 n 個個體的實際應(yīng)值，R(x1)，R(x2)，…，R(xn)分別表示這n個個體的平均適應(yīng)值。這里，可采用下面的思路來對n個個體的進行排序：先找出所有n個個體中實際適應(yīng)度值最大的那個個體(具體方法參見1.2節(jié))，從原隊列中去掉該個體，將該個體排在新隊列中的首位；依次類推，直到原來隊列中的個體數(shù)目為零時排序結(jié)束。

2 量化正交遺傳算法

本文定義染色體x=(x1,x2,…，xn)的成本為f(x)。全局優(yōu)化問題等價于找到成本最小的染色體。

2.1 初始種群的生成

在求解全局優(yōu)化問題前，我們不知道全局優(yōu)化點位于哪個區(qū)域。因而就希望優(yōu)化算法從一開始就在可行解空間中進行均勻地、離散地搜索，以至于算法可以均勻地搜索整個可行解空間。不難發(fā)現(xiàn)，正交表在所有可能的組合中指定了均勻離散分布的數(shù)量規(guī)模比較小的組合群。所以，正交設(shè)計方法是能產(chǎn)生一組比較好的初始種群的潛在的方法。定義第個自變量為，因而每個染色體有N個自變量。這些自變量都是連續(xù)的，但正交設(shè)計方法僅僅針對于處理那些離散的自變量。為了克服這個缺點，我們將每個自變量都量化成有限的值。本文將自變量xi的定義域[li,ui]量化成Q1個水平ai1,ai1，…，aiQ1，這里的Q1是奇數(shù)，具體的aij計算公式如下：

為方便起見，稱aij為第i個自變量的第j個水平，定義ai=(ai1,ai2,…，aiQ1)。完成自變量的量化操作以后，自變量xi擁有Q1個可能水平ai1,ai2,…，aiQ1，然后可行解空間包含個點。本文采用正交設(shè)計的方法在可行解空間中選擇一小群樣本點。

首先構(gòu)建了一個合適的正交表。如前所述，前面的構(gòu)造正交表的方法僅能構(gòu)造正交表此處的是滿足以下條件的正整數(shù)：

由于優(yōu)化問題的維數(shù)N是給定的，因而可能不存在滿足上式的Q1和J1。我們可以將上面的要求放寬一些，選擇滿足下列條件的最小的正整數(shù)：

當可行解空間比較大時，這種方法很可能生成收斂性比較好的初始點。然而，值的大小依賴于N和Q1的大小，不能任意地增大。為了解決這個問題，將可行解空間分解成S個部分，這里的S是一個設(shè)計參數(shù)。將s維區(qū)間[l,u]分解成為以下 S 個部分：[l(1)，μ(1)]，[l(2)，μ(2)]，…，[l(s)，μ(s)]這里

ls是諸如第s個元素為1其他元素為0的一個N維向量。我們應(yīng)用正交表LM1()在每一個部分都生成M1個染色體，這樣我們總共就得到了M1S個潛在的染色體。我們從中選擇個代價最小的初始種群染色體。

2.2 量化的正交交叉算子

量化正交交叉算法將父代個體定義的求解空間量化成有限數(shù)目點，然后應(yīng)用正交設(shè)計方法選擇一群有代表性的規(guī)模比較小的潛在子代個體。考慮以下兩個父代個體：

它們定義的求解空間[lparent,uparent]如下：

將每一個父代求解空間[lparent,uparent]量化成Q2份，這樣任意兩個連續(xù)水平之間的差異是相同的。尤其值得一提的是，我們將第 i維區(qū)間量化成 βi1，βi2，…，βiQ2其中：

我們定義 β=(βi1，βi2，…，βiQ2)。 由于種群的不斷進化和改進，種群成員之間越來越接近，兩個父代個體定義的求解空間也越來越小。由于Q2是定值，隨著量化點的逐步接近，我們就可以得到越來越精確的結(jié)果。

在完成求解空間[lparent,uparent]的量化后，我們應(yīng)用正交設(shè)計方法選擇一批數(shù)據(jù)規(guī)模比較小的富有代表性的樣本點作為潛在的子代，然后選擇一些代價最小的樣本點作為子代。為了避免在選擇過程中大規(guī)模的評價種群點，每一對父代盡可能不要產(chǎn)生太多的潛在子代點。基于這個目的，我們將變量x1,x2,…，xN分成F組，這里的F是一個很小的設(shè)計參數(shù)。每一組將會被看成一個因素。這樣，相應(yīng)正交表的組合數(shù)目將會減少，然后就產(chǎn)生一個規(guī)模比較小的初始種群。這里，我們隨機地生成F-1個整數(shù)k1,k2,…，kF-1，這里不妨假定1＜k1＜k2＜…＜kF-1＜N。 然后對于每個染色體 x=(x1,x2,…，xN)產(chǎn)生以下 F個因素。

因為x1,x2,…，xN可以被量化，我們?yōu)榈趥€因素定義如下Q2各水平：

3 二級分銷網(wǎng)絡(luò)系統(tǒng)仿真模型

對于一個確定了分銷中心的二級分銷網(wǎng)絡(luò)系統(tǒng)，可以把其看成是一個在分銷中心產(chǎn)生庫存的庫存系統(tǒng)。這個庫存系統(tǒng)以分銷中心為中心，集成考慮庫存和運輸。通過控制庫存可以實現(xiàn)對整個分銷網(wǎng)絡(luò)進行管理。離散事件系統(tǒng)仿真能夠準確記錄系統(tǒng)各個環(huán)節(jié)的狀態(tài)變化情況，并能根據(jù)這些記錄得到系統(tǒng)的各個評價指標的統(tǒng)計結(jié)果。

3.1 目標和邊界

應(yīng)用仿真技術(shù)研究二級分銷網(wǎng)絡(luò)系統(tǒng)的目的是通過各種庫存指標比較各種訂貨策略的優(yōu)劣，如在不同的需求情況下，何時訂貨、訂多少貨為宜，庫存安全量如何確定等。二級分銷網(wǎng)絡(luò)系統(tǒng)的優(yōu)劣常采用“費用(效益)”的高低來衡量，二級分銷網(wǎng)絡(luò)系統(tǒng)主要的費用有運輸費用、訂貨費用、倉儲費用和缺貨損失費等。在整個分銷系統(tǒng)的不斷變化中，引發(fā)事件是用戶需求的產(chǎn)生和滿足，因此把用戶需求的產(chǎn)生和滿足作為模型的邊界。

3.2 實體

二級分銷網(wǎng)絡(luò)系統(tǒng)的實體包括供貨方、分銷中心、用戶和貨物。其中，供貨方、分銷中心和用戶為永久實體，貨物為臨時實體。對于供貨方來說，必須滿足供應(yīng)量足夠，即不管訂貨需求何時到達，供貨方都能滿足分銷中心的訂貨需求；對于用戶來說，需求的產(chǎn)生是無條件的，只是在時間上符合某種規(guī)律，而與其它因素?zé)o關(guān)。

3.3 流程分析

在二級分銷網(wǎng)絡(luò)系統(tǒng)中，分銷中心庫存量的變化是由用戶需求和分銷中心訂貨兩個方面的因素引起的。由于用戶需求使得庫存量不斷減少，為了保證供應(yīng)，就需要訂貨來補充庫存量。隨著需求和訂貨的不斷發(fā)生，庫存量呈現(xiàn)動態(tài)分布。

3.4 仿真算法

本文采用事件調(diào)度法對二級分銷網(wǎng)絡(luò)系統(tǒng)進行仿真。事件是指狀態(tài)變化的瞬間。事件調(diào)度方法以事件為基礎(chǔ)，用事件的觀點來分析現(xiàn)實系統(tǒng)，它通過定義事件及每個事件的發(fā)生對系統(tǒng)狀態(tài)的影響，按時間順序確定并執(zhí)行每個事件發(fā)生時有關(guān)的邏輯、數(shù)學(xué)關(guān)系。基于事件調(diào)度的仿真模型用于描述各類離散事件的發(fā)生及相關(guān)聯(lián)的邏輯變換。

在用事件調(diào)度法建立模型時，全部事件都放在事件鏈表中。由時間控制模塊從事件鏈表中選擇具有最早發(fā)生時間的事件，并將仿真時鐘修改到該事件發(fā)生的時刻，再調(diào)用與該事件相應(yīng)的事件處理模塊和動畫圖像描繪模塊，這樣，事件的選擇與處理不斷地進行，直到仿真終止條件得到滿足或終止事件發(fā)生為止。

4 實證分析

某公司已經(jīng)對分銷網(wǎng)絡(luò)進行了設(shè)計，如圖1所示。本部分通過分析歷史數(shù)據(jù)得到用戶需求產(chǎn)生的時間分布的基礎(chǔ)上，通過系統(tǒng)仿真從而得到最優(yōu)的訂貨策略。

4.1 基本設(shè)置

筆者采用Arena軟件自帶的Input Analyzer功能對歷史數(shù)據(jù)進行分析，得到用戶的需求達到的時間間隔服從參數(shù)為λ(λ1=42，λ3=45,λ4=22,λ7=60,λ8=55,λ9=26,λ10=39)的泊松分布。通過分析，確定計算庫存相關(guān)費用所需的參數(shù)如表1所示。

采用定期定量訂貨方式，三個分銷中心分別采用每周訂貨1000件或5000件。仿真系統(tǒng)模擬所有的8種組合，從中選取最優(yōu)的訂貨策略。編號為2、5、6的分銷中心分別按照自己的訂貨策略發(fā)出自己的訂單，然后比較與編號為1、2、3、4的供貨方的距離，從中選擇距離最近的供貨方供貨。為了計算方便，這里假設(shè)供貨方的供應(yīng)量不受限制。記錄其中產(chǎn)生的訂貨費、運輸費和庫存量增加。 編號為 1、3、4、7、8、9、10 的用戶按照相應(yīng)的泊松分布產(chǎn)生自己的需求，分別把訂單發(fā)給相應(yīng)的分銷中心。若分銷中心可以滿足訂單所需貨量則發(fā)貨，否則產(chǎn)生缺貨。記錄其中發(fā)生的運輸費用、倉儲費用和缺貨損失費用。

4.2 實驗結(jié)果

仿真時間設(shè)為1年，仿真得到各種訂貨策略下的費用見表2。在表2中，用“1”表示采用每周訂貨1000件的訂貨策略，用“2”表示每月訂貨5000件的訂貨策略。例如：表中最后一行的訂貨策略為分銷中心2每月訂貨5000件，分銷中心5每周訂貨1000件，分銷中心6每月訂貨5000件。

通過比較，可以得到使這個二級分銷網(wǎng)絡(luò)系統(tǒng)總費用最少的訂貨策略為:分銷中心2每周訂貨1000件，分銷中心5每月訂貨5000件，分銷中心6每月訂貨5000件，其費用為27415436元。

表1 庫存相關(guān)費用計算所需的參數(shù)

5 結(jié)束語

本文提出了一種將計算機仿真技術(shù)、遺傳算法和假設(shè)檢驗等完美結(jié)合的概率仿真優(yōu)化方法。該方法在二級分銷網(wǎng)絡(luò)系統(tǒng)的實證研究表明，采用該方法處理網(wǎng)絡(luò)分銷優(yōu)化問題能夠獲得比較滿意的優(yōu)化結(jié)果，這也為處理類似問題提供了方法論借鑒。

[1]Cao X R,Ho X C.Estimation of Co-Join Time Sensitivity in Queuing Networks Using Perturbation Analysis[J].Journal of Optimization Theory and Applications,1997,44(3).

[2]Olsder G J.On The Characteristics Equation and Minimal Realizations for Discrete-Event Dynamic System[J].Analysis and Optimization of Systems,1998,83.

[3]Azadivar,F.A Tutorial on Simulation Optimization[C].Proceedings of the 1992 Winter Simulation Conference,1992，13～16.

[4]Fu,M.C.Optimization Via Simulation:a Review[J].Annals of Operational Research,1994,(53).

[5]Rosenblatt,M.J.,Roll,Y.，Zyse,V.A Combined Optimization and Simulation Approach for Designing Automated Storage/Retrieval Systems[J].IIE Transactions,1993,25(1).

[6]Kleijnen,J.P.C.Simulation and Optimization Production Planning:a Case Study[J].Research Memorandum,1988.

[7]G.V.Reklaitis,A.Ravindran，K.M.Ragsdell.Engineering Optimization:Methods and Applications[M].New York：John Wiley&Sons,1983.

[8]R.Fletcher.Practical Methods for Optimization,2ndEdition[M].New York：John Wiley&Sons,1987.

[9]P.E.Gill,W.Murray,M.H.Wright.Practical Optimization[M].London：Academic Press，1981.

[10]A.M.Law,W.D.Kelton.Simulation Modeling and Analysis（3rdEdition）[M].Singapore：McGraw-Hill,2000.