一種新穎的概率仿真優(yōu)化方法

蔡奎生

（蘇州經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院，江蘇 蘇州 215000）

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

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

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

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

這里，筆者采用以下方式來(lái)確定p的取值：

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

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

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

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

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

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

2 量化正交遺傳算法

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

2.1 初始種群的生成

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

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

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

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

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

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

2.2 量化的正交交叉算子

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

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

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

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

因?yàn)閤1,x2,…,xN可以被量化，我們?yōu)榈趇個(gè)因素定義如下Q2各水平：

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

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

3.1 目標(biāo)和邊界

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

3.2 實(shí)體

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

3.3 流程分析

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

3.4 仿真算法

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

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

4 實(shí)證分析

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

4.1 基本設(shè)置

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

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

4.2 實(shí)驗(yàn)結(jié)果

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

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

表2 各種訂貨策略下的費(fèi)用表

5 結(jié)束語(yǔ)

本文的主要?jiǎng)?chuàng)新點(diǎn)是：提出了一種將計(jì)算機(jī)仿真技術(shù)、遺傳算法和假設(shè)檢驗(yàn)等完美地結(jié)合的概率仿真優(yōu)化方法。在二級(jí)分銷網(wǎng)絡(luò)系統(tǒng)的實(shí)證研究表明，采用本文方法能獲得比較滿意的優(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].In Proceedings of the 1992 Winter Simulation Conference,1992.

[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[M].New York:McGraw-Hill,2000.