基于子集模擬的預制構件生產目標均衡優(yōu)化算法研究

王 家,金艷琪，陳雅含

(湖南大學 土木工程學院，湖南 長沙 410082)

0 引言

預制構件生產是裝配式建造推廣的重要環(huán)節(jié)之一，在預制構件生產過程中，涉及到人力、材料、機械等多方面。隨著我國建造領域工業(yè)化的不斷推進[1]，對預制構件的需求量不斷增長，對預制構件的質量要求也不斷上升[2]。而目前我國預制構件生產加工廠普遍存在技術管理人員專業(yè)化技術和產業(yè)化實施能力不足的問題[3]，這一現(xiàn)狀使得預制構件呈現(xiàn)出總體生產成本較高，總體環(huán)境效益不顯著的弊端。預制構件生產目標均衡的目的在于為預制構件的生產工序選擇合適的生產執(zhí)行模式組合，科學合理地根據構件生產需求制定生產方案，提高預制構件生產效率，降低預制構件生產成本，增強預制構件的環(huán)境效益，從而促進裝配式建筑行業(yè)的高質量發(fā)展。

預制構件生產過程中的目標均衡優(yōu)化問題有著復雜的含義。從目標考慮，可以分為成本優(yōu)化問題[4-5]、效率優(yōu)化問題[6-7]、碳排放優(yōu)化問題[8-9]和庫存優(yōu)化問題[10]等,以及不同類型優(yōu)化目標的組合優(yōu)化問題。從算法考慮，可以分為精確算法求解問題和啟發(fā)式算法求解問題。精確算法主要基于動態(tài)規(guī)劃、整數規(guī)劃、分支界定等方法[11]，而啟發(fā)式算法主要基于遺傳算法[12-13]、蟻群算法[14]、粒子群算法[15-16]、共生生物搜索算法[17]等算法。預制構件生產目標均衡問題的復雜程度隨著工序數量的增加而急劇上升，因此，針對工序數量較多的預制構件生產目標均衡問題，精確算法并不適用，只能采用啟發(fā)式算法。但是，現(xiàn)有啟發(fā)式算法具有隨機性，在最優(yōu)解獲取穩(wěn)定性上仍有較大的改進空間。

為此，本文針對預制構件生產目標均衡優(yōu)化問題，提出一種基于子集模擬的啟發(fā)式優(yōu)化算法。利用聚集函數法，將生產時間、成本和生產過程中產生的碳排放納入優(yōu)化目標，構建多模式下預制構件生產目標均衡優(yōu)化模型。同時為了增強子集模擬在全局范圍的搜索能力，采取均勻間隔取點的馬爾科夫鏈方法，增加樣本點的多樣性。通過實際案例的驗證，與改進的遺傳算法相比，本文提出的優(yōu)化算法在最優(yōu)解獲取的穩(wěn)定性上有較好改進。

1 預制構件生產目標均衡優(yōu)化模型

考慮包含n道工序，每道工序i(i=1,2,…,n)涉及mi種生產執(zhí)行模式的預制構件生產項目。該項目中第i道工序的第j(i=1,2,…,mi)種執(zhí)行模式的持續(xù)時間、耗費成本和產生的碳排放分別表示為tij,cij和eij。預制構件生產目標均衡優(yōu)化模型中，一般通過指示變量Xij表示工序i所選擇的執(zhí)行模式，如工序i選擇第j種執(zhí)行模式，則Xij=1。因各工序僅能選擇一種執(zhí)行模式，指示變量需滿足如下約束條件：

(1)

項目的調度方案，可表示為包含所有指示變量的矩陣X={Xij,i=1,…,n,j=1,mi}。例如，表1為某生產項目目標均衡方案的矩陣表示，該項目包含5道工序，每道工序對應的執(zhí)行模式總數分別為4、2、4、4和3。由指示變量Xij的含義可知，該項目調度方案中，工序1～5所選擇的執(zhí)行模式分別為第2、第1、第3、第3和第2。

表1 典型目標均衡方案的矩陣表示Table 1 Matrix representation of typical resource schedu-ling scheme工序i執(zhí)行模式j123410100210——30010400105010—

在給定項目調度方案X={Xij,i=1,…,n,j=1,mi}下，生產項目的工期T(X)可通過調度方案X中各工序執(zhí)行模式的生產時間累加得出，如式(2)所示：

(2)

式中:L表示關鍵路徑上工序的集合。同理，可以求出生產項目的總制造成本C(X)和總碳排放量E(X)：

(3)

(4)

預制構件生產均衡優(yōu)化的目標, 是通過對工序執(zhí)行模式的合理組合，盡可能實現(xiàn)項目工期、成本和碳排放量的最小化.為綜合考慮工期、成本和碳排放量3項子目標，本文將各子目標無量綱化，并分配反映重要性程度的權重系數，進而建立如下的優(yōu)化模型：

(5)

s.t.

T(X)≤T*,C(X)≤C*,E(X)≤E*

其中,Tmin，Cmin，Emin為各子目標的下限值；Tmax，Cmax，Emax為各子目標的上限值;w1,w2,w3為各子目標在模型中的權重系數；本文采用層次分析法確定，T″，C″，E″分別為各子目標的最大容許值。

生產項目的調度方案，也可采用向量的表示形式θ=(θ1,θ2,…,θn)。此時,向量θ中的元素θi,i=1,…,n代表工序i的執(zhí)行模式，為[1,mi]內的自然數。由項目調度方案的矩陣表示X與向量表示θ的含義可知,X與θ間存在一一對應關系.例如，表1的矩陣表示X，對應工序1～5分別選擇第2、第1、第3、第3和第2執(zhí)行模式的調度方案, 其向量表示為θ=(2,1,3,3,2)。利用X與θ間的一一對應關系X=X(θ)，可得調度方案向量表示下的優(yōu)化模型：

(6)

s.t.

T(θ)≤T*,C(θ)≤C*,E(θ)≤E*

式(4)的優(yōu)化模型為離散型優(yōu)化模型，某些情形下針對其等價的連續(xù)性優(yōu)化模型進行求解更為方便.式(4)的優(yōu)化模型中，決策變量θi,i=1,…,n為[1,mi]內的自然數, 可針對其引入(0,1]間取值的連續(xù)性決策變量ui,i=1,…,n, 并建立兩者間的函數關系如下：

θi=ceil(ui×mi),0

(7)

式中:函數ceil()為向右取整函數。此時，預制構件生產調度優(yōu)化模型可以表示為連續(xù)型決策變量U=(u1,u2,…,un)下的優(yōu)化模型：

(8)

s.t.

T(θ(U))≤T*,C(θ(U))≤C*,E(θ(U))≤E*0

2 基于子集模擬的生產調度優(yōu)化算法

子集模擬法(Subset Simulation)是 Au 和 Beck 提出的，針對結構可靠度問題的高效數值模擬算法[18]。其思想是通過引入一系列中間失效事件，將偶發(fā)事件的小概率表示為一系列較大的條件概率乘積, 進而將小概率估計問題轉化為一組較大的條件概率的估計問題[19]，以提高數值模擬算法的計算效率。通過利用可靠度問題和優(yōu)化問題的內在聯(lián)系，子集模擬方法在優(yōu)化設計問題中也取得了較好的應用[20]。

2.1 基于子集模擬的生產目標均衡優(yōu)化算法框架

考慮如下優(yōu)化問題：

minf(U)

(9)

s.t.

0

T(U)≤T*,C(U)≤C*,E(U)≤E*

為利用子集模擬法求解上述優(yōu)化問題，人為設定變量U為隨機變量，服從可行域Ω0={U∶0f2>…,fJ，可在可行域Ω0內定義一系列逐漸收縮的區(qū)域Ωj={U∶U∈Ω0,f(U)≤fj},j=1,…,J。 此時，所考察的區(qū)域間存在子集關系，Ω0?Ω1?Ω2…?ΩJ，這也是子集模擬法名稱的由來。通過依次在可行域Ω2與逐漸收縮區(qū)域Ωj(j=1,…J)內按均勻分布進行隨機取樣，子集模擬法可逐漸縮窄搜索區(qū)域，最終在最優(yōu)解附近的較小區(qū)域內進行搜索，以得到問題的最優(yōu)解。

2.2 可行域Ω0內均勻分布樣本點的產生

a.在區(qū)域Ω={U∶0

考慮到預制構件生產優(yōu)化問題中變量U的維數(對應項目中的工序數量)較大，本文采用改進Metropolis-Hasting方法[17]，以完成上述馬爾科夫鏈中的迭代操作。具體而言，方法采用一維均勻分布的概率密度分布函數p*(ξ/u)作為建議概率密度分布函數。該函數以u為中心，以d為寬度(即u-d/2≤ξ≤u+d/2)(d一般取0.2～0.4)，可自動滿足對稱性的要求。馬爾可夫鏈中Uk=(uk,1,uk,2,…,uk,n)到Uk+1=(uk+1,1,uk+1,2,…,uk+1,n)的迭代操作如下：

2.3 收縮區(qū)域Ωj={U∶U∈Ω0,f(U)≤fj}內均勻分布樣本點的產生

如2.1節(jié)所述，基于子集模擬的優(yōu)化算法中，需根據在收縮區(qū)域Ωj內的少量樣本點，利用MCMCS方法產生要求數量的樣本點。方法中具體的馬爾科夫鏈迭代操作與2.2節(jié)類似，但需額外考慮收縮區(qū)域的邊界限制f(U)≤fj，因此，需將2.2節(jié)馬爾科夫鏈迭代操作中的步驟修改如下：

在實際運算過程中，為了避免MCMCS產生的樣本點陷入局部最優(yōu)，采用均勻間隔取點的方式，每間隔e個狀態(tài)點選擇一點作為樣本點。如圖1所示。以p0=0.1,M=100,e=3為例，當Uk作為一條鏈條的起點時，如果采取連續(xù)取點的方法，那么需要通過MCMCS方法產生(1/p0-1)=9個狀態(tài)點，這些點全部作為樣本點。此時，馬爾科夫鏈長度為10。如果間隔取點，則需要產生[1/p0×(e+1)-1]=39個狀態(tài)點，此時，馬爾科夫鏈長度為40。取第5,9,13,…,37個點作為樣本點。通過間隔取點的方法，產生的樣本點更具有多樣性。

(a) 連續(xù)取點的馬爾科夫鏈

2.4 基于子集模擬的預制構件生產目標均衡優(yōu)化算法總結

針對以上預制構件生產目標均衡優(yōu)化模型，本文基于子集模擬法，建議的優(yōu)化算法步驟總結如下：a.確定子集模擬算法中的參數，即在指定區(qū)域中抽樣的樣本數量M、條件概率參數p0、改進Metropolis-Hasting方法中定義一維均勻概率分布的寬度d和MCMCS中均勻間隔取點數e。

e.算法采用的迭代終止原則為達到預先設定的迭代次數J。如不滿足迭代終止條件，即j>J，令j=j+1，重復步驟4。

3 案例分析

以文獻[21]中某預制構件廠一預制構件生產線為例，該生產線包含21道生產工序，如圖2所示。每道工序對應節(jié)約、正常、趕工3種執(zhí)行模式，每種執(zhí)行模式下對應的生產時間、花費成本和產生的碳排放量如表2所示。受到外界資源限制，最大生產時間閾值T*=540 min，最高生產成本閾值C*=2 600元，最大生產碳排放閾值E*=800 kg(碳排放指二氧化碳當量，全文同)。

圖2 某預制構件生產流程圖

需要注意的是，工序7、12、13為非關鍵工序，不計入生產總時間。根據表2，可以計算出僅考慮單個資源消耗的理想值Tmax=640 min,Cmax=2 769元，Emax=818.37 kg;Tmax=509 min,Cmax=2 556元，Emax=790.03 kg。利用層次分析法，通過專家打分，各資源的相對權重確定為[w1,w2,w3]=[0.2,0.2,0.6]。

表2 各工序時間成本碳排放量匯總Table 2 Summary of carbon emissions of each process time cost序號工序節(jié)約模式正常模式趕工模式時間/min成本/元碳排放/kg時間/min成本/元碳排放/kg時間/min成本/元碳排放/kg1清理模板、預埋件、臺車面25973.10201052.51171112.162模具檢驗7190.025220.03———3劃線———5130.25———4邊模組裝12320.0710440.098350.075復核尺寸7190.025220.03———6涂脫模油7150.065150.05———7工裝與材料準備(非關鍵工序)25583307.8420604307.8815607307.98布筋、綁扎、固定251520.76201550.78181700.819布置脫模吊釘、吊具201220.18151170.18131230.210布筋檢驗10270.035220.03———11布置預埋件204680.12154710.14124730.1112混凝土攪拌(非關鍵工序)———10443452.278460460.1413混凝土輸送(非關鍵工序)———5130.61———14混凝土布料、振搗20376.7215405.0410443.3715表面檢查、清理8150.015180.02———16趕平、抹光12222.4110272.028351.6417養(yǎng)護42042003603605.64———18構件反向、落平、轉移———154010.410446.9619表面磨光12220.210270.347310.4720脫模15407.6410445.128494.1221吊裝入庫———102711.688289.36

為檢驗基于子集模擬的目標均衡優(yōu)化算法的性能，每代隨機抽樣樣本取M=1 000，條件概率參數取p0=0.1，篩選產生初始樣本點數量取t=10，改進Metropolis-Hasting方法中一維均勻概率分布的寬度取d=0.30，MCMCS中均勻間隔取點數取e=3。圖3描述了基于子集模擬的建議優(yōu)化算法一次典型求解過程中，最優(yōu)目標函數值隨迭代階段的變化。由圖3可知，算法經過4次迭代后收斂到最優(yōu)解，對應最優(yōu)目標函數值0.212 9。該最優(yōu)解對應的各工序執(zhí)行模式的選擇如表3所示，對應生產時間T=534 min，花費成本元C=2 598元，產生的碳排放量E=796.42 kg。

圖3 建議優(yōu)化算法典型求解過程中最優(yōu)目標函數值隨迭代階段的變化

為檢驗基于子集模擬的建議優(yōu)化算法的穩(wěn)定性，設計了改進的遺傳算法( Improved Genetic Algorithm,IGA)進行對比。經過試驗，傳統(tǒng)的GA無法在相對有限的時間內，隨機產生足夠數量滿足約束條件的初始樣本點。因此，運用2.2節(jié)中的方法對初始種群的產生方法進行處理，得到改進后的遺傳算法(IGA)。考慮到交叉概率參數pc和變異概率參數pc對 IGA 算法求解的影響，本文進行了大量pc和pm組合取值，檢驗發(fā)現(xiàn)，交叉概率pc=0.9和變異概率pm=0.05下，IGA 算法求解本案例目標均衡問題的性能最優(yōu)，因此表4給出的是這組交叉概率和變異概率下IGA 算法的對比結果。同時，考慮到計算資源對2種優(yōu)化算法的影響，結合兩種算法的特點，在子集模擬算法中，每代樣本點取1 000，迭代終止條件為最優(yōu)解連續(xù)3次迭代保持不變，再將子集模擬實際的運算量作為IGA的迭代終止條件。

表3 典型最優(yōu)解對應的各工序執(zhí)行模式選擇與各資源消耗量Table 3 Selection of the execution mode of each process corresponding to the typical optimal solution and the consumption of each resource工序執(zhí)行模式工序執(zhí)行模式工序執(zhí)行模式12(正常)82(正常)151(節(jié)約)21(節(jié)約)92(正常)162(正常)31(正常)102(正常)172(正常)41(節(jié)約)113(趕工)182(趕工)51(節(jié)約)121(正常)191(節(jié)約)62(正常)131(正常)203(趕工)71(節(jié)約)143(趕工)212(趕工)

表4提供了2種算法1 000次獨立運行求解獲得的最優(yōu)目標函數值的統(tǒng)計結果(最小值、平均值、最大值和標準差)。對比可知，基于子集模擬的優(yōu)化算法獲得最優(yōu)目標函數值的平均值為0.213 0，小于基于 IGA 的優(yōu)化算法的相應數值(0.213 5)，且最優(yōu)目標函數值的標準差值更小。此外，圖4給出了2種算法 1 000 次獨立運行獲得的最優(yōu)目標函數值的分布情況。由圖4可見，基于子集模擬的優(yōu)化算法性能更優(yōu)，其獲得的最優(yōu)目標函數值分布更為集中，有96.2%的最優(yōu)目標函數值集中在(0.212 0，0.213 0]區(qū)間，表明基于子集模擬的建議優(yōu)化算法獲取最優(yōu)解的穩(wěn)定性更高。

表4 基于子集模擬的優(yōu)化算法與 IGA 算法獨立運行 1 000 次獲得的最優(yōu)目標函數值的統(tǒng)計結果Table 4 The statistical results of the optimal objective function value obtained by the optimization algorithm based on the subset simulation and the IGA algorithm independently run 1 000 times算法最優(yōu)解的目標函數值統(tǒng)計最小值平均值最大值標準差基于子集模擬的優(yōu)化算法0.212 90.213 00.215 82.682 7E-04基于IGA的優(yōu)化算法0.212 90.213 50.225 20.001 3

圖4 兩種優(yōu)化算法獨立運行 1 000 次獲得的最優(yōu)目標函數值的分布

4 結論

本文針對預制構件生產項目的目標均衡優(yōu)化問題，基于子集模擬法進行啟發(fā)式優(yōu)化算法的研究，主要研究結論如下：

a.在構建預制構件生產目標均衡優(yōu)化模型時，引入權重系數，對多個優(yōu)化目標進行處理，并通過映射條件，將離散型變量問題轉化為連續(xù)型變量求解問題。

b.針對預制構件生產目標均衡優(yōu)化模型，提出基于子集模擬的建議優(yōu)化算法，并給出算法框架和具體操作步驟。

c.為產生滿足約束條件的初始種群，采用隨機產生和MCMCS相結合的方法，先篩選少量滿足約束的初始樣本點，再以MCMCS的方法擴充至整個初始種群，提高計算效率。

d.為避免收縮區(qū)域內樣本點產生陷入局部最優(yōu)，采取均勻間隔取點的馬爾科夫鏈方法，增強子集模擬在全局范圍的搜索能力，豐富種群的多樣性。

e.通過算例驗證，與改進的遺傳算法相比，基于子集模擬的建議優(yōu)化算法在最優(yōu)解的獲取穩(wěn)定性上有較大改進。