建設(shè)項目隨機離散型工期-成本優(yōu)化算法的改進

王家 ，唐敬奇 ，周忠寶 ，韓淙吉

（1.湖南大學(xué) 土木工程學(xué)院，湖南 長沙 410082；2.湖南大學(xué) 工商管理學(xué)院，湖南 長沙 410082）

作為建設(shè)項目計劃與管理的重要內(nèi)容，工期-成本優(yōu)化問題旨在合理分配建設(shè)項目實施所需的各種資源，以達到項目工期和成本的最佳權(quán)衡.工程實踐中，建設(shè)項目中各工序的資源分配往往呈現(xiàn)出離散化的特征，故其實施方式只能從有限個執(zhí)行模式中選取.因此，工序執(zhí)行模式作為決策變量的離散型工期-成本優(yōu)化問題（Discrete Time-Cost Trade-off Problem，DTCTP），受到學(xué)者的廣泛關(guān)注［1］.離散型工期-成本優(yōu)化問題的求解方法主要可分為精確算法和啟發(fā)式算法［2］.精確算法包括整數(shù)規(guī)劃、動態(tài)規(guī)劃等方法，適用于規(guī)模較小的問題［3-5］.當(dāng)問題的規(guī)模較大時，求解中主要采用啟發(fā)式算法，包括和聲搜索算法［6］、粒子群算法［7］、蟻群算法［8］、遺傳算法［9-10］等.同時，伊長生等［11］基于模糊規(guī)劃理論，構(gòu)建了工程項目在多模式環(huán)境下的工期-成本優(yōu)化模型，并提出了基于遺傳算法、模糊模擬和神經(jīng)網(wǎng)絡(luò)的混合智能算法.He 等［12］將BIM 技術(shù)與遺傳算法結(jié)合，構(gòu)建了針對離散型工期-成本優(yōu)化問題的五維BIM 決策平臺.

同時，建設(shè)項目所處的環(huán)境，易受生產(chǎn)效率波動、施工現(xiàn)場條件改變等不確定性因素的影響.鑒于此，研究人員采用PERT網(wǎng)絡(luò)來考慮不確定性因素對項目工期和項目成本的影響，開展了大量研究工作［13-14］.其中，為克服傳統(tǒng)PERT 方法的缺陷，Balles?teros 提出一種可紙上作業(yè)的項目工期估算技術(shù)M-PERT［15］.針對大型建設(shè)項目的項目工期風(fēng)險分析，Jun 等［16］基于多元正態(tài)積分法和圖論的遍歷方法，提出一種兼顧準(zhǔn)確度和計算效率的新型算法.

但是，在建設(shè)項目的離散型工期-成本優(yōu)化問題中，納入項目工期和項目成本的不確定性度量，進行隨機離散型工期-成本優(yōu)化的研究仍然偏少.Ke等［17］建立了兩種隨機離散型工期-成本優(yōu)化模型，并提出了遺傳算法為外循環(huán)、蒙特卡羅模擬方法（Monte Carlo simulation，MCS）為內(nèi)循環(huán)的雙層循環(huán)算法框架.然而，該研究并未過多考慮算法的計算效率，隨機離散型工期-成本優(yōu)化算法的計算效率提升，仍有較大的研究空間.因此，本文針對雙層循環(huán)算法中內(nèi)循環(huán)的按期完工概率約束條件檢驗，根據(jù)按期完工概率蒙特卡羅估計值的概率特性，提出一種計算資源的高效、動態(tài)分配策略，以提升現(xiàn)有優(yōu)化算法的計算效率.通過算例驗證，本文建議的改進優(yōu)化算法可高效、穩(wěn)定地求解建設(shè)項目隨機離散型工期-成本優(yōu)化問題.

1 建設(shè)項目的隨機離散型工期-成本優(yōu)化模型

考慮包含Na項工序、Np條路徑的某一建設(shè)項目.該項目中，任一工序i的執(zhí)行模式總數(shù)假設(shè)為Ki（i=1，2，…，Na），工序i在第k個執(zhí)行模式下的持續(xù)時間和成本分別表示為ti，k和ci，k.采用xi，k作為工序i執(zhí)行模式的指示變量，如工序i選擇第k個執(zhí)行模式，則xi，k=1，否則xi，k=0.工序i的工期ti和成本ci可分別表示為：

考慮到任一工序i只能選擇一個執(zhí)行模式，指示變量xi，k需滿足如下約束條件：

項目中任一路徑工期Tj（j=1，2，…，Np）可由該路徑上所有工序的工期求和得到，即：

式中：λji(j=1，2，…，Np；i=1，2，…，Na)為路徑j(luò)上工序的指示變量（可由進度網(wǎng)絡(luò)圖得到），如工序i在路徑j(luò)上，則λj，i=1，否則λj，i=0.項目的總工期T為所有路徑工期的最大值，可表示為：

項目的總成本C為所有工序的成本之和，可表示為：

如采用X={xi，k，i=1，2，…，Na；k=1，2，…，Ki}包含所有工序的執(zhí)行模式指示變量，由公式（5）和公式（6）可知，項目總工期和總成本為X的函數(shù)，可分別表示為T（X）和C（X）.

考慮到生產(chǎn)效率波動、現(xiàn)場條件改變等不確定性因素的影響，給定執(zhí)行模式下工序的持續(xù)時間ti，k和成本ci，k更適宜描述為服從一定概率分布的隨機變 量.例如，ti，k和ci，k可采用三點估計值基礎(chǔ)上的Beta分布來描述：

其中：ati，k、mti，k、bti，k分別為ti，k的最樂觀、最可能、最悲觀估計值；aci，k、mci，k、bci，k分別為ci，k的最樂觀、最可能、最悲觀估計值.表1 為某橋梁工程項目中大孔板梁安裝工序在不同執(zhí)行模式下的成本和工期估計值.

表1 大孔板梁安裝工序在不同執(zhí)行模式下的工期、成本估計值Tab.1 Estimates of the duration and the cost for the activity of installing plate beam（with large holes）at different execution modes

考慮不確定性因素影響下，項目的總工期T（X）和總成本C（X）為隨機變量，此時項目的隨機離散型工期-成本優(yōu)化問題可描述為如下模型［16］：

同時，項目的實施模式X，應(yīng)確保項目的按期完工概率Pr {T(X) ≤T0}（項目工期T（X）不超出目標(biāo)工期T0的概率）較高，高于給定的限值1 -αt.

2 基于遺傳算法的雙層循環(huán)算法

針對公式（9）的隨機離散型工期-成本優(yōu)化問題，可采用現(xiàn)有的雙層循環(huán)算法框架進行求解.雙層循環(huán)算法的框架如圖1 所示，外層循環(huán)采用遺傳算法［18-20］搜尋、考察更優(yōu)的解，內(nèi)層循環(huán)需利用蒙特卡羅模擬方法估算考察解的按期完工概率，以檢驗按期完工概率約束條件，判斷考察解的可行性.原雙層循環(huán)算法中，針對不同考察解的按期完工概率估計，蒙特卡羅模擬方法均采用相同次數(shù)的項目進度網(wǎng)絡(luò)分析（相同的樣本數(shù)），導(dǎo)致優(yōu)化問題求解所需的分析次數(shù)過多.如外層循環(huán)搜尋10 000個考察解，內(nèi)層循環(huán)的蒙特卡羅模擬方法采用5 000 次分析來估計每一考察解的按期完工概率，則整個優(yōu)化過程需進行5×107次項目進度網(wǎng)絡(luò)分析.因此，當(dāng)問題規(guī)模較大（涉及工序較多）時，原雙層循環(huán)算法所需的計算資源過多，耗時過久.

圖1 雙層循環(huán)算法框架Fig.1 Framework for the double loop procedure

有鑒于此，研究在保持原雙層循環(huán)算法框架基礎(chǔ)上，對內(nèi)層循環(huán)的蒙特卡羅模擬方法動態(tài)分配計算資源（例如樣本數(shù)在200～5 000間動態(tài)調(diào)整），以提升雙層循環(huán)算法的計算效率.本節(jié)討論雙層循環(huán)算法中外層循環(huán)的遺傳算法實現(xiàn)，內(nèi)層循環(huán)中蒙特卡羅模擬方法的計算資源動態(tài)分配在第3節(jié)介紹.

2.1 編碼與解碼

隨機離散型工期-成本優(yōu)化問題適合采用實數(shù)編碼的方式.具體而言，可將染色體表示為序列θ=(θ(1)，θ(2)，…，θ(Na))，θ(i) (i=1，2，…，Na）為[1，Ki]內(nèi)的自然數(shù)，代表工序i的執(zhí)行模式.例如，考慮包含7 項工序的某工程項目，各工序執(zhí)行模式的總數(shù)分別是2，5，6，4，3，6，5，則編碼后的染色體可能為θ=(2，4，3，2，1，5，3)，表示第1～第7 項工序的執(zhí)行模式依次為第2，第4，第3，第2，第1，第5 和第3.采用上述編碼方式的染色體，其對應(yīng)的原問題的解X=｛xi，k，i=1，2，…，Na；k=1，2，…，Ki｝，可直接根據(jù)xi，k的含義得到，解碼過程非常簡便.考慮前例中的染色體θ=(2，4，3，2，1，5，3)，其解碼得到的X見表2所示.

表2 典型染色體解碼對應(yīng)的原問題解XTab.2 The solution of X corresponding to a typical chromosome

2.2 適應(yīng)度函數(shù)

針對染色體個體θ，其對應(yīng)的項目成本C(θ)，可通過將解碼值X(θ)代入公式（6）得到：

項目成本C(θ)為隨機變量，其概率分布由式（11）和ci，k的概率分布共同確定.θ對應(yīng)的目標(biāo)函數(shù)值，滿足條件≥1 -αc，可通過蒙特卡羅模擬方法估算.同時，估算時僅涉及ci，k隨機抽樣樣本的簡單求和，MCS 方法中大量重復(fù)模擬所需的計算資源較為有限.遺傳算法中，一般根據(jù)染色體個體的適應(yīng)度函數(shù)值決定其遺傳到下一代的概率.本算法中，適應(yīng)度函數(shù)F(θ)定義為的倒數(shù)，即：

2.3 種群迭代過程

遺傳算法為迭代算法，通過初始染色體種群的生成和相鄰種群的迭代，來實現(xiàn)染色體種群的進化和全局最優(yōu)解的搜尋.本節(jié)討論第i代染色體種群到第i+1 代染色體種群Ai+1=的迭代過程，包含選擇、交叉、變異、約束條件檢驗的操作，而初始染色體種群的產(chǎn)生方法參見第4節(jié).

1）選擇：針對第i代染色體種群Ai=，可根據(jù)公式（12）計算種群中各染色體對應(yīng)的適應(yīng)度函數(shù)值，j=1，2，…，M.本文采用輪盤賭準(zhǔn)則進行選擇，以各染色體的相對適應(yīng)度函數(shù)值（歸一化后的數(shù)值）作為選中概率，從種群Ai中隨機選擇出兩個染色體，以進行后續(xù)的操作.除輪盤賭準(zhǔn)則外，典型的選擇算子還包括錦標(biāo)賽選擇策略、隨機遍歷抽樣法等［21］.不同選擇算子間的優(yōu)劣，學(xué)界尚未達成共識.因此，本文采用遺傳算法中廣泛采用、使用簡便的輪盤賭準(zhǔn)則，并在后續(xù)研究中考察不同選擇算子對算法的整體影響.

2）交叉：本文的交叉操作采用單點交叉算子，并根據(jù)交叉概率pc進行.針對選擇操作得到的兩個染色體，如需進行交叉，則隨機選擇交叉點位置，并互換交叉點后的基因，以形成新的兩個染色體個體.

3）變異：針對交叉操作后的兩個染色體，根據(jù)變異概率pm進行變異操作.具體而言，兩個染色體上的所有基因值根據(jù)概率pm，變異為其他數(shù)值（該基因值對應(yīng)的工序的其他執(zhí)行模式）.

4）約束條件檢驗：每一代種群中的染色體個體，其解碼值需滿足公式（9）中的約束條件.由2.1 節(jié)和2.2 節(jié)的討論可知，公式（9）中的約束條件中，僅需檢驗按期完工概率約束條件，其他兩類約束條件可自動滿足.因此，針對變異操作后的兩個染色體，可采用MCS 方法（詳見第3 節(jié)），檢驗按期完工概率約束條件.如滿足按期完工概率約束條件，則放入下一代種群Ai+1中，否則應(yīng)舍棄.

3 內(nèi)層循環(huán)中計算資源的動態(tài)分配策略

針對染色體個體θ=(θ(1)，θ(2)，…，θ(Na))，需根據(jù)其解碼值X=｛xi，k，i=1，2，…，Na；k=1，2，…，Ki｝，檢驗按期完工概率約束條件.根據(jù)公式（5），θ對應(yīng)的項目工期為：

根據(jù)公式（9）中優(yōu)化模型的要求，項目工期T(θ)需滿足約束條件Pr{T(θ) ≤T0}≥1 -αt.為方便論述，后續(xù)采用PR(θ)表示染色體下的按期完工概率，即PR(θ)=Pr {T(θ) ≤T0}.

隨機離散型工期-成本優(yōu)化算法的雙層循環(huán)流程中，內(nèi)循環(huán)采用MCS 方法估計染色體θ下的按期完工概率PR(θ)，并檢驗約束條件PR(θ) ≥1 -αt.MCS 方法根據(jù)ti，k的概率分布進行隨機抽樣，并利用關(guān)鍵路徑法執(zhí)行項目的進度網(wǎng)絡(luò)分析，以得到染色體θ下的項目工期樣本.重復(fù)上述步驟N次，可得到染色體θ下項目工期的N個隨機樣本進而得到如下的按期完工概率的估計值［22］：

式 中：NR為隨機樣本{T(1)[X(θ)]，T(2)[X(θ)]，…，T(N)[X(θ)]}中數(shù)值不大于T0的個數(shù).采用上述流程得到的估計值具有隨機性，其準(zhǔn)確度可用變異系數(shù)（樣本標(biāo)準(zhǔn)差和樣本均值的比值）進行衡量，通過公式（15）估算［22］.

為確保估算的準(zhǔn)確度，此時的樣本數(shù)量N不能過小.由公式（15）可知，隨著樣本數(shù)量N（與計算資源的消耗相關(guān)）的增加，估計值的準(zhǔn)確度得到提高（對應(yīng)的變異系數(shù)R減?。?

考慮到PR(θ) ∈[0，1]，上述極大可能區(qū)間的上下界計算中引入了0 和1.該極大可能區(qū)間類似于不同概率分布下以期望值為中心、以4 倍標(biāo)準(zhǔn)差為寬度的區(qū)間.在不同的概率分布下，該區(qū)間對應(yīng)的概率均接近1.例如，正態(tài)分布下該區(qū)間對應(yīng)的概率為95.46%，均勻分布下該區(qū)間對應(yīng)的概率為100%，指數(shù)分布下該區(qū)間對應(yīng)的概率為95.02%.因此，公式（16）定義的區(qū)間有較大概率包含PR(θ)，可作為PR(θ)的極大可能區(qū)間.隨著采用樣本數(shù)N的增加，估計的準(zhǔn)確度提升（變小），包含PR(θ)的極大可能區(qū)間逐漸縮窄，如圖2所示.

圖2 極大可能區(qū)間隨樣本數(shù)量的變化Fig.2 The most probable range at different number of samples

內(nèi)層循環(huán)采用MCS 方法的目的，是檢驗約束條件PR(θ) ≥1 -αt是否成立，而非準(zhǔn)確估計PR(θ).因此，包含PR(θ)的極大可能區(qū)間并非都需要估計至非常狹窄，其與邊界值1 -αt能夠區(qū)分即可.當(dāng)PR(θ)距離邊界值1 -αt較遠時，準(zhǔn)確度較低的估計足以提供可靠的檢驗判斷.如圖3 所示，雖然此時采用的樣本數(shù)較少，對應(yīng)估計值的準(zhǔn)確度較低，包含PR(θ)的極大可能區(qū)間較寬，但是，此時的極大可能區(qū)間的上限小于1 -αt，足以可靠地說明約束條件PR(θ) ≥1 -αt此時不成立，因此并不需要額外增加計算資源（樣本數(shù)量）.當(dāng)PR(θ)距離約束條件邊界值1 -αt較近時，較小樣本數(shù)量得到的極大可能區(qū)間包含了邊界值1 -αt，無法提供約束條件PR(θ) ≥1 -αt的可靠判斷，此時需額外增加計算資源（樣本數(shù)量），直到縮窄的極大可能區(qū)間不包含1 -αt為止，如圖4所示.

圖3 僅需較少計算資源的約束條件檢驗情形Fig.3 Constraint examination in which few computational resources are required

圖4 需較多計算資源的約束條件檢驗情形Fig.4 Constraint examination in which more computationalresources are required

因此，為提供約束條件PR(θ) ≥1 -αt的可靠檢驗，MCS 方法中的樣本數(shù)N，應(yīng)使包含PR(θ)的極大可能區(qū)間與邊界值1 -αt區(qū)分開來，即但是，當(dāng)PR(θ)極其靠近1 -αt時，如仍采用上述原則，則會使MCS 方法中分配的樣本數(shù)量過于龐大.所以，應(yīng)對樣本數(shù)量N的上限進行限制，即N應(yīng)低于設(shè)定的限值Ntol.綜上所述，為提供約束條件PR(θ) ≥1 -αt的可靠判斷，本文采用極大可能區(qū)間指標(biāo)和樣本數(shù)量上限相結(jié)合的原則，動態(tài)分配MCS方法中的樣本數(shù)Nreq：

4 初始染色體種群的改進生成方法

現(xiàn)有的隨機離散型工期-成本優(yōu)化算法中，遺傳算法的初始染色體種群，采用隨機產(chǎn)生并檢驗約束條件PR(θ) ≥1 -αt的方法.但是，若滿足約束條件的染色體占比較小，則上述方法的效率過低.如滿足約束條件的染色體占比為5%，為得到滿足約束條件的100 個染色體，平均需要隨機產(chǎn)生2 000個染色體，并進行按期完工概率約束條件的檢驗，將耗費大量不必要的計算資源.

基于上述考量，研究采用“帶有反射壁的隨機游動”的馬爾可夫鏈蒙特卡羅（Markov Chain Monte Carlo，MCMC）方法［23］，來產(chǎn)生初始染色體種群.具體而言，為得到馬爾可夫鏈{θ1，θ2，…}的起點θ1=(θ1(1)，θ1(2)，…，θ1(Na))，令其基因值θ1(i)，i=1，2，…，Na為工序i的最趕工執(zhí)行模式序號.例如，第6 節(jié)算例中各工序的最趕工執(zhí)行模式序號均為1（見表3），此時起點θ1=(θ1(1)，θ1(2)，…，θ1(Na))的基因值均選為1，即θ1(i)=1，i=1，2，…，Na.該θ1在所有染色體中，最有可能滿足約束條件PR(θ) ≥1 -αt，如其亦不滿足，則說明該優(yōu)化問題無可行解.馬爾可夫鏈{θ1，θ2，…}中θk=(θk(1)，θk(2)，…，θk(Na))到θk+1=(θk+1(1)，θk+1(2)，…，θk+1(Na))的迭代操作如下：

表3 不同執(zhí)行模式下的工序數(shù)據(jù)Tab.3 Data of the activities at different execution modes

1）從染色體θk=(θk(1)，θk(2)，…，θk(Na))中隨機選擇一個可變基因θk(r)（對應(yīng)工序的執(zhí)行模式總數(shù)大于1，即Kr>1）.

3）采用第3 節(jié)的動態(tài)檢驗方法，檢驗備選狀態(tài)點是否滿足約束條件PR(θ) ≥1 -αt.如滿足約束條件，則將備選狀態(tài)點作為下一狀態(tài)點，即θk+1=否則重復(fù)上一狀態(tài)點，即θk+1=θk.

5 建議的改進優(yōu)化算法總結(jié)

針對建設(shè)項目的隨機離散型工期-成本優(yōu)化問題，本文建議對現(xiàn)有的雙層循環(huán)算法（遺傳算法為外循環(huán)、蒙特卡羅模擬方法為內(nèi)循環(huán)）進行改進.改進優(yōu)化算法的具體步驟總結(jié)如下：

1）確定算法中各參數(shù)的取值，包括遺傳算法中的迭代代數(shù)NG、種群規(guī)模M、交叉概率pc、變異概率pm，檢驗約束條件時動態(tài)分配MCS 樣本數(shù)所需的參數(shù)值Nl和Ntol.

2）利用第4 節(jié)的MCMC 方法，產(chǎn)生滿足按期完工概率約束條件的初始染色體種群A0=，并令迭代指示變量i=0.

3）計算第i代種群Ai中各染色體的適應(yīng)度函數(shù)值根據(jù)精英保留策略，選擇Ai中適應(yīng)度函數(shù)值最高的染色體，直接放入下一代種群Ai+1中.

4）執(zhí)行選擇、交叉、變異及約束條件檢驗操作，直至得到下一代種群的M個染色體Ai+1=令迭代指示變量i=i+1.多次重復(fù)步驟3）～4），直至迭代次數(shù)i達到NG.選擇最后一代種群中的最優(yōu)解，作為隨機離散型工期-成本優(yōu)化問題的最優(yōu)解.

6 算例分析

研究通過算例來檢驗建議優(yōu)化算法的性能，采用的計算機硬件配置為處理器Intel（R）Core（TM）i7-8700、內(nèi)存16 G，軟件配置為MATLAB R2020b.基于文獻［8］的案例，本文將其中的項目網(wǎng)絡(luò)圖重復(fù)4 次，以增加算例復(fù)雜程度，構(gòu)建了圖5 所示的算例項目網(wǎng)絡(luò)圖（虛線內(nèi)為原案例的項目網(wǎng)絡(luò)圖）.算例項目中包含72 項工序，不同執(zhí)行模式下各工序持續(xù)時間和成本的三點估計值如表3 所示.算例項目的隨機離散型工期-成本優(yōu)化問題中，目標(biāo)工期T0為550 d，工期和成本約束條件中的限值1 -αt和1 -αc均為95%.

圖5 算例項目的單代號網(wǎng)絡(luò)圖Fig.5 The activity-on-node network of the example project

針對算例項目的優(yōu)化問題，建議算法采用如下的參數(shù)：遺傳算法中種群規(guī)模M為100，交叉概率pc為0.4，變異概率pm為0.01，終止迭代代數(shù)NG為140.同時，為確定MCS 方法中動態(tài)分配策略的參數(shù)值Nl和Ntol，研究利用公式（15）和（16）計算了給定樣本數(shù)量下MCS 方法的失效范圍.圖6 繪制了樣本數(shù)N=200 時不同按期完工概率MCS 估計值的極大可能區(qū)間.由圖6可知，當(dāng)按期完工概率估計值時，其極大可能區(qū)間的上限，此時按期完工概率約束條件不成立的判斷較為可靠.當(dāng)按期完工概率估計值時，其極大可能區(qū)間的下限，此時按期完工概率約束條件成立的判斷較為可靠.當(dāng)，其極大可能區(qū)間包含邊界值0.95，因此不能提供約束條件的可靠判斷，此時MCS 方法檢驗失效.類似地，當(dāng)樣本數(shù)N=5 000 時，計算出的MCS 方法失效范圍縮窄至［0.943，0.956］，滿足較好的精度要求.因此，動態(tài)分布策略中的參數(shù)值取Nl=200 和Ntol=5 000.對應(yīng)更高的計算精度時，可提高Ntol的數(shù)值，以便其所對應(yīng)的MCS方法失效范圍縮窄至可接受的目標(biāo)范圍.

圖6 樣本數(shù)N=200時按期完工概率MCS估計值的極大可能區(qū)間Fig.6 The most probable range for the MCS estimator with N=200

研究考察了采用上述參數(shù)的建議優(yōu)化算法的求解過程.圖7 描述了一次典型求解中最優(yōu)目標(biāo)函數(shù)值隨迭代階段的變化.由圖7 可見，算法經(jīng)過140 代后已收斂到最優(yōu)解，對應(yīng)最優(yōu)目標(biāo)函數(shù)值434.175千元.針對求解中所考察的14 026個解，研究統(tǒng)計了約束條件檢驗所動態(tài)分配的MCS 樣本數(shù)，并由表4 給出了不同樣本數(shù)區(qū)間對應(yīng)的考察解的比例.由表4可知，14 026個考察解中，98.97%的解分配了較少的MCS 樣本數(shù)Nreq=200.該結(jié)果說明大部分考察解的按期完工概率距離邊界值0.95 較遠，因此較少的分配樣本數(shù)就足以提供按期完工概率約束條件的可靠判斷.同時，其他的1.03%的解所分配的樣本數(shù)，散布于Nl=200 和Ntol=5 000 之間，驗證了按期完工概率約束條件的動態(tài)檢驗方法的有效性.

圖7 建議優(yōu)化算法典型求解中最優(yōu)目標(biāo)函數(shù)值隨迭代階段的變化Fig.7 Optimal objective function value at different stages in a typical run of using the proposed method

表4 不同Nreq區(qū)間對應(yīng)的考察解的比例Tab.4 The ratio of examined solutions at different ranges of Nreq

為檢驗動態(tài)分配策略對優(yōu)化算法準(zhǔn)確度和穩(wěn)定性的影響，研究將建議優(yōu)化算法與現(xiàn)有優(yōu)化算法（與建議優(yōu)化算法類似，但未采用動態(tài)分配策略，約束條件檢驗采用固定樣本數(shù)5 000下的MCS方法）的求解進行比較.同時，為排除初始樣本種群的影響，兩種算法采用相同的初始樣本種群.研究將兩種算法的對比獨立進行了30 次，算法運行所得最優(yōu)解的目標(biāo)函數(shù)值和按期完工概率如圖8 所示，最優(yōu)目標(biāo)函數(shù)值的統(tǒng)計結(jié)果如表5 所示.由圖8 和表5 可知，建議優(yōu)化算法和現(xiàn)有優(yōu)化算法的求解結(jié)果基本類似，30 次運行結(jié)果中，最優(yōu)目標(biāo)函數(shù)值的最大值、最小值、平均值、標(biāo)準(zhǔn)差都很接近.因此，采用動態(tài)分配策略，可保持與現(xiàn)有優(yōu)化算法類似的求解準(zhǔn)確度和穩(wěn)定性.同時，建議優(yōu)化算法的單次運行耗時約為0.54 h，而現(xiàn)有優(yōu)化算法單次運行耗時約為7.12 小時.與現(xiàn)有優(yōu)化算法相比，采用動態(tài)分配策略的建議優(yōu)化算法的計算效率提升了約13倍.

圖8 兩種算法獨立運行30次所得最優(yōu)解的目標(biāo)函數(shù)值和按期完工概率Fig.8 The objective function value and the completion reliabil?ity for the optimal solutions obtained by the 30 independent runs of using two different methods

表5 兩種算法獨立運行30次的統(tǒng)計結(jié)果Tab.5 Statistical results of 30 independent runs using two different methods

7 結(jié)論

本文針對建設(shè)項目的隨機離散型工期-成本優(yōu)化問題，研究遺傳算法為外循環(huán)、蒙特卡羅模擬方法為內(nèi)循環(huán)的優(yōu)化算法的改進，主要研究結(jié)論如下：

1）內(nèi)層循環(huán)中采用蒙特卡羅模擬方法檢驗按期完工概率約束條件時，可利用按期完工概率估計值的極大可能區(qū)間，進行計算資源的動態(tài)、高效分配.

2）針對外層循環(huán)中遺傳算法所需的初始染色體種群，可采用“帶有反射壁的隨機游動”的馬爾可夫鏈蒙特卡羅方法，以提高染色體種群的產(chǎn)生效率.

3）通過算例驗證，與現(xiàn)有優(yōu)化算法相比，建議優(yōu)化算法的求解準(zhǔn)確度和穩(wěn)定性類似，而計算效率有較大的提升（約13倍）.