施工現(xiàn)場設(shè)施布局優(yōu)化問題的新型啟發(fā)式算法

王家，王洋，鄧鐵軍，2?，劉可心

（1.湖南大學(xué) 土木工程學(xué)院，湖南 長沙 410082；2.湖南大學(xué)設(shè)計研究院有限公司，湖南 長沙 410082）

施工現(xiàn)場設(shè)施布局是施工組織設(shè)計的重要任務(wù)，其目的是在滿足場地約束條件下，為一組特定的臨時設(shè)施分配適當(dāng)?shù)奈恢肹1].施工現(xiàn)場設(shè)施布局的科學(xué)性和合理性直接關(guān)系到施工現(xiàn)場的生產(chǎn)效率和成本節(jié)約，進(jìn)而影響項目成本等目標(biāo)的實現(xiàn)[2].在傳統(tǒng)的工程實踐中，施工現(xiàn)場設(shè)施布局決策主要依靠施工人員的經(jīng)驗，決策的效率較低、不確定性較高[3].為提高施工現(xiàn)場設(shè)施布局的效率和科學(xué)性，國內(nèi)外的相關(guān)學(xué)者從不同角度入手，進(jìn)行了大量的研究工作.

施工現(xiàn)場設(shè)施布局問題為組合優(yōu)化問題，一般利用二次分配問題（Quadratic Assignment Problem，QAP）的模型進(jìn)行分析，其復(fù)雜程度隨布局設(shè)施的數(shù)量增加而急速上升[4].當(dāng)問題涉及的設(shè)施個數(shù)較多時，難以采用枚舉法或解析方法獲得最優(yōu)解，一般采用元啟發(fā)式算法（如遺傳算法、蟻群算法、粒子群算法等）來得到問題的最優(yōu)解或近似最優(yōu)解[5].針對施工現(xiàn)場設(shè)施布局問題，遺傳算法是應(yīng)用較廣的一種元啟發(fā)式算法.Li 和Love 針對施工現(xiàn)場設(shè)施布局優(yōu)化問題提出了一種以修飾的邊緣重組算子作為交叉算子、以對稱基因交換算子作為變異算子的遺傳算法[6].Adrian 等人比較了遺傳算法、粒子群優(yōu)化算法和蟻群優(yōu)化算法在不同施工現(xiàn)場設(shè)施布局優(yōu)化問題實例中的性能和效率，結(jié)果顯示三種算法在解決施工現(xiàn)場設(shè)施布局優(yōu)化問題時的性能和效率相當(dāng)[7].元啟發(fā)式算法具有隨機(jī)性，其每次運行獲得的最優(yōu)解不一定相同（不穩(wěn)定），但現(xiàn)有元啟發(fā)式算法在全局最優(yōu)解獲取的穩(wěn)定性上仍有較大的改進(jìn)空間.

本文基于過渡馬爾可夫鏈蒙特卡羅方法，提出一種針對施工現(xiàn)場設(shè)施布局優(yōu)化問題的新型啟發(fā)式全局優(yōu)化算法.具體而言，針對涉及設(shè)施較多的施工現(xiàn)場設(shè)施布局優(yōu)化問題，本文首先將優(yōu)化問題轉(zhuǎn)換為高維空間的隨機(jī)抽樣問題，進(jìn)而利用過渡馬爾可夫鏈蒙特卡羅方法的思想，提出一種高效的全局優(yōu)化啟發(fā)式算法.通過實例驗證，與應(yīng)用較廣的遺傳算法相比，本文提出的優(yōu)化算法在全局最優(yōu)解獲取的穩(wěn)定性上有較好的改進(jìn).

1 施工現(xiàn)場設(shè)施布局優(yōu)化問題模型

施工現(xiàn)場設(shè)施布局優(yōu)化的目的，在于為一組臨時設(shè)施分配施工現(xiàn)場的合適位置，以提高施工現(xiàn)場的工作效率，節(jié)約成本.如圖1 所示，考慮n 個臨時設(shè)施和n 個預(yù)先確定的施工現(xiàn)場位置，并假定任一預(yù)先確定的施工現(xiàn)場位置均足以容納任一臨時設(shè)施.以降低臨時設(shè)施間物流的總移動距離為目的，施工現(xiàn)場設(shè)施布局優(yōu)化問題模型可描述如下：

其中任一布局方案可表示為一個n×n 的置換矩陣，δxi（x，i=1，…，n）代表置換矩陣第x 行第i 列的元素.當(dāng)設(shè)施x 被分配至位置i 時，δxi=1，否則δxi=0.系數(shù)fxy（x，y=1，…，n）代表設(shè)施x 和y 之間物流的頻次，系數(shù)dij（i，j=1，…，n）代表位置i 和j 之間的距離.

圖1 典型施工場地及預(yù)定位置示意圖Fig.1 Typical construction site and predetermined locations

表1 為針對5 個臨時設(shè)施、5 個位置的一個布局方案的置換矩陣表示.置換矩陣的每一行和每一列中均只有一個元素為1，其他元素均為0，該特性可保證公式（1）中的約束條件自動滿足.從物理意義上看，公式（1）中約束條件的含義為：一個位置只能布置一個臨時設(shè)施，而一個臨時設(shè)施也只能被分配到一個位置.

表1 典型布局方案的置換矩陣表示（5 個設(shè)施，5 個位置）Tab.1 Permutation matrix representation for a typical layout with 5 facilities and 5 locations

上述模型亦適用于將m 個臨時設(shè)施分配至n 個位置（n ＞m）的布局優(yōu)化問題.此時，可添加（n-m）個虛擬設(shè)施，并將與虛擬設(shè)施相關(guān)的物流頻次fxy賦值為0.在這種處理方法下，虛擬設(shè)施的引入不會影響最終布局優(yōu)化的結(jié)果.

2 施工現(xiàn)場設(shè)施布局優(yōu)化問題的新型啟發(fā)式算法

針對公式（1）描述的施工現(xiàn)場設(shè)施布局優(yōu)化問題，首先將布局方案的置換矩陣表示轉(zhuǎn)變?yōu)橄蛄勘硎荆M(jìn)而通過建立適當(dāng)?shù)母怕史植己瘮?shù)，將施工現(xiàn)場設(shè)施布局優(yōu)化這一組合優(yōu)化問題轉(zhuǎn)化為根據(jù)給定的高度集中、高維概率分布進(jìn)行隨機(jī)抽樣的問題，最后給出利用過渡馬爾可夫鏈蒙特卡羅（Transitional Markov Chain Monte Carlo，TMCMC）方法完成隨機(jī)取樣、獲取優(yōu)化問題最優(yōu)解的方法.本文考慮的施工現(xiàn)場設(shè)施布局優(yōu)化問題為離散型變量優(yōu)化問題，故其求解過程需解決的是離散型隨機(jī)概率分布的抽樣問題，與原始的TMCMC 方法針對的隨機(jī)抽樣問題（針對連續(xù)型高維概率密度分布）不同.

因此，在利用TMCMC 方法建立施工現(xiàn)場設(shè)施布局優(yōu)化問題的新型啟發(fā)式算法過程中，需對隨機(jī)抽樣對象以及由此引起的馬爾可夫鏈的構(gòu)造方法進(jìn)行修改，以適應(yīng)施工現(xiàn)場設(shè)施布局優(yōu)化問題的不同特性.

2.1 布局方案的向量表示

描述施工現(xiàn)場設(shè)施布局優(yōu)化模型的公式（1）中，布局方案表示為n×n 的置換矩陣.為便于應(yīng)用本文所提出的啟發(fā)式方法，布局方案采用含有n 個元素的行向量θ=[θ1，θ2，…，θn]來表示，其中行向量的第i個元素代表第i 個設(shè)施被分配的位置標(biāo)號.布局方案的向量表示與置換矩陣表示存在一一對應(yīng)關(guān)系.例如，表1 的布局方案可表示為[3，5，2，1，4]，即將臨時設(shè)施1，2，3，4，5 分別分配至位置3，5，2，1，4 處.

為滿足公式（1）中的約束條件，布局方案行向量中的所有元素需從n 個位置標(biāo)號中選取，且不允許重復(fù)，因此可行布局方案的個數(shù)為n！.對應(yīng)于任一可行布局方案行向量θ=[θ1，θ2，…，θn]，為計算其在公式（1）中的目標(biāo)函數(shù)值g（θ），可先將布局方案行向量轉(zhuǎn)化為對應(yīng)的置換矩陣，進(jìn)而利用公式（1）中的目標(biāo)函數(shù)表達(dá)式進(jìn)行計算.

2.2 組合優(yōu)化問題與隨機(jī)抽樣問題的聯(lián)系

本文考慮的施工現(xiàn)場設(shè)施布局優(yōu)化這一組合優(yōu)化問題，與給定概率分布的隨機(jī)抽樣問題存在密切的聯(lián)系.在布局方案的向量表示下，可在可行布局方案集合上定義如下概率分布：

式中：g0為預(yù)先選定的無量綱化常數(shù)，g（θ）為給定可行布局方案θ 下的目標(biāo)函數(shù)值，T 為溫度參數(shù).

在公式（2）定義的概率分布下，具有較小目標(biāo)函數(shù)值（θ）的布局方案θ 對應(yīng)于較大的概率分布.當(dāng)溫度參數(shù)T 趨近0 時，上述的概率分布（趨近）完全集中在擁有最小目標(biāo)函數(shù)值的可行布局方案（集）上.如對此時的概率分布（對應(yīng)T 趨于0）進(jìn)行隨機(jī)抽樣，進(jìn)而在隨機(jī)抽樣的布局方案中選取最優(yōu)，則可得到施工現(xiàn)場設(shè)施布局優(yōu)化問題的最優(yōu)解.但是針對高度集中的概率分布，一般的馬爾可夫鏈蒙特卡羅（Markov Chain Monte Carlo，MCMC）方法的抽樣效率較差，需經(jīng)過大量過渡階段的樣本才能得到服從目標(biāo)概率分布的馬爾可夫鏈樣本[8].

2.3 過渡馬爾可夫鏈蒙特卡羅方法

過渡馬爾可夫鏈蒙特卡羅（Transitional Markov Chain Monte Carlo，TMCMC）方法是由Ching 和Chen提出的、適用于高度集中的高維概率密度分布函數(shù)的高效抽樣方法[9].該方法在借鑒模擬退火算法[10]思想的基礎(chǔ)上，引入了自適應(yīng)溫度下降策略和重抽樣方法，以提高算法的抽樣性能.針對公式（2）的離散型概率分布的隨機(jī)抽樣問題，利用TMCMC 方法，可通過改變溫度參數(shù)T，引入一組過渡階段的概率分布（定義在可行布局方案集合上）：

式中：hi（θ）為第i 階段的概率分布（對應(yīng)溫度參數(shù)Ti），溫度參數(shù)逐漸遞減T0＞T1＞…＞Tm，由第0 階段的溫度參數(shù)T0=∞逐漸減小到目標(biāo)的溫度參數(shù)Tm=0+（正向接近0）.由式（3）可知，當(dāng)T0=∞時，h0（θ）為均勻分布，其抽樣較為簡單，當(dāng)Tm=0+時，hm（θ）高度集中于全局最優(yōu)解，其抽樣較為困難.TMCMC 以滿足均勻分布h0（θ）的樣本{θ10，θ20，…，θN0}為起點，通過下述的迭代操作，來得到服從概率分布hm（θ）的樣本{θ1m，θ2m，…，θNm}，進(jìn)而得到問題的最優(yōu)解.

給定服從第i 階段概率分布hi（θ）的樣本{θ1i，θ2i，…，θNi}，迭代操作首先確定下一階段的溫度參數(shù)Ti+1，進(jìn)而產(chǎn)生服從概率分布hi+1（θ）（對應(yīng)Ti+1）的樣本{θ1i+1，θ2i+1，…，θNi+1}[11，12].考慮給定樣本{θ1i，θ2i，...，θNi}上概率分布函數(shù)hi+1（θ）與hi（θ）的比值：

當(dāng)Ti+1與Ti相比降低較少時，比值函數(shù)在樣本{θ1i，θ2i，…，θNi}上的取值差異很小，而當(dāng)Ti+1與Ti相比降低較多時，比值函數(shù)在樣本{θ1i，θ2i，…，θNi}上的取值差異較大.因此，TMCMC 采用比值函數(shù)值w（θki）（k=1，2，…，N）的樣本變異系數(shù)（樣本標(biāo)準(zhǔn)差與樣本均值的比值）來動態(tài)控制相鄰兩階段的溫度降低幅度，即選擇下一階段的溫度參數(shù)Ti+1，使得比值函數(shù)值w（θki）（k=1，2，…，N）的樣本變異系數(shù)等于預(yù)先設(shè)定的常數(shù).樣本變異系數(shù)一般取0.01～0.5，當(dāng)問題規(guī)模較小、需投入的計算資源較少時，宜取較大值，當(dāng)問題規(guī)模較大、需投入的計算資源較多時，宜取較小值.

確定第i+1 階段的溫度參數(shù)Ti+1后，TMCMC 利用重抽樣方法（Re-sampling Method）和MCMC 方法來產(chǎn)生服從第i+1 階段概率分布的樣本{θ1i+1，θ2i+1，…，θNi+1}.根據(jù)溫度參數(shù)Ti+1可計算給定樣本{θ1i，θ2i，…，θNi}對應(yīng)的比值函數(shù)w（θki）（k=1，2，…，N），重抽樣方法針對樣本{θ1i，θ2i，…，θNi}按如下概率

進(jìn)行重抽樣來得到服從第i+1 階段概率分布hi+1（θ）的樣本{θ1i+1，θ2i+1，…，θNi+1}.即樣本θki（k=1，2，…，N）被選中作為第i+1 階段樣本的概率為p（k）.在上述的N 次選擇過程中，對應(yīng)選中概率p（k）較大的樣本θki有較大可能被選中多于一次.若θki被選中m ＞1 次，則利用MCMC 方法產(chǎn)生一個以θki為起點、以hi+1（θ）為穩(wěn)態(tài)分布、具有m 個狀態(tài)點的馬爾可夫鏈，來代替被重復(fù)選中多次的樣本θki，作為第i+1 階段的m 個樣本.

2.4 基于TMCMC 的新型啟發(fā)式優(yōu)化算法

針對研究的施工現(xiàn)場設(shè)施布局優(yōu)化問題，基于TMCMC，提出的啟發(fā)式優(yōu)化算法的流程如下：

1）選定無量綱化常數(shù)g0，并根據(jù)公式（2）構(gòu)造不同溫度參數(shù)下的概率分布.隨機(jī)產(chǎn)生服從第0 階段概率分布h0（θ）（對應(yīng)溫度參數(shù)T0=∞，均勻分布）的N 個可行布局方案{θ10，θ20，…，θN0}.

2）根據(jù)當(dāng)前階段i（i=0，1，…）的溫度參數(shù)Ti及服從概率分布hi（θ）的N 個可行布局方案{θ1i，θ2i，…，θNi}，確定第i+1 階段的溫度參數(shù)Ti+1，以確保在樣本{θ1i，θ2i，…，θNi}上的比值函數(shù)w（θki）（k=1，2，…，N）的樣本變異系數(shù)等于預(yù)先設(shè)定的常數(shù).進(jìn)而利用重抽樣方法和MCMC 方法產(chǎn)生服從第i+1 階段概率分布hi+1（θ）的N 個可行布局方案{θ1i+1，θ2i+1，…，θNi+1}.

如果在重抽樣中，第i 階段的樣本θki被選中m＞1 次，則需解決以θki為起點、以hi+1（θ）為穩(wěn)態(tài)分布、具有m 個狀態(tài)點的馬爾可夫鏈的構(gòu)造問題.考慮到施工現(xiàn)場設(shè)施布局優(yōu)化問題為離散變量優(yōu)化問題，相應(yīng)的隨機(jī)抽樣問題針對的是離散型概率分布，不能采用以高斯分布函數(shù)為“建議概率密度分布函數(shù)”的Metropolis 方法（原始TMCMC 方法中）來完成馬爾可夫鏈{θ1，θ2，…}的構(gòu)造工作[13].因此，需對馬爾可夫鏈的構(gòu)造方法進(jìn)行修改，采用如下馬爾可夫鏈{θ1，θ2，…}中狀態(tài)點θk（k=1，2，…）到下一狀態(tài)點θk+1的迭代操作：

a）隨機(jī)交換狀態(tài)點θk中的兩個元素，以得到備選狀態(tài)點ξ.該操作相當(dāng)于選取“建議概率分布函數(shù)”p*（ξ|θk）為離散型均勻分布，可滿足對稱性要求p*（ξ|θk）=p*（θk|ξ）.

b）計算備選狀態(tài)點ξ 和當(dāng)前狀態(tài)點θk對應(yīng)的穩(wěn)態(tài)概率分布函數(shù)的比值：

c）若比值r≥1，則下一狀態(tài)點θk+1=ξ；若比值r＜1，則下一狀態(tài)點θk+1以r 的概率取值為ξ，以（1-r）的概率取值為θk.

3）重復(fù)步驟2，直到滿足迭代終止原則.本文的迭代終止原則取為達(dá)到預(yù)先設(shè)定的迭代次數(shù).

3 案例分析

為檢驗基于TMCMC 的建議優(yōu)化算法的性能，并與施工現(xiàn)場設(shè)施布局優(yōu)化領(lǐng)域中采用較廣的遺傳算法進(jìn)行對比分析，本文采用兩個工程實例進(jìn)行驗證.驗證模擬實驗使用的計算機(jī)硬件配置為處理器Intel（R）Core（TM）i7-7700、內(nèi)存16G，軟件配置為MATLAB R2017b.

3.1 工程實例一（11 項臨時設(shè)施）

本實例采用文獻(xiàn)[6]中的施工現(xiàn)場設(shè)施布局優(yōu)化問題，該問題涉及11 個臨時設(shè)施和11 個用以分配臨時設(shè)施的位置，并假定每個預(yù)定位置都足以容納任一臨時設(shè)施.表2 提供了11 個臨時設(shè)施的具體信息和編號.設(shè)施中的側(cè)門（設(shè)施8）和正門（設(shè)施11）通常在開始施工之前就已經(jīng)確定，在設(shè)施分配過程中正門和側(cè)門的位置不會發(fā)生變化.但是其它設(shè)施與正門及側(cè)門的相對位置仍會影響布局的物流移動總距離（模型的目標(biāo)函數(shù)），因此側(cè)門和正門不能從模型的考察設(shè)施中排除，仍需作為模型中的一種特殊約束存在.

表2 臨時設(shè)施信息（實例一）Tab.2 Information of temporary facilities（Example 1）

該施工現(xiàn)場設(shè)施布局優(yōu)化問題的模型可根據(jù)公式（1）建立.其中，設(shè)施間物流頻次（一天內(nèi)）參數(shù)fxy（x，y=1，…，11）如表3 所示，例如，設(shè)施1（現(xiàn)場辦公室）與設(shè)施2（臨時支架車間）一天內(nèi)的物流頻次為f12=5，設(shè)施6 與設(shè)施8 一天內(nèi)的物流頻次為f68=8.位置間的距離參數(shù)dij（i，j=1，…，11）如表4 所示，例如，位置1 與位置7 間的距離為d17=47 米，位置4 與位置5 間的距離為d45=7 米.在該案例的布局優(yōu)化模型中，側(cè)門（設(shè)施8）和正門（設(shè)施11）固定安排在位置1 和位置10 內(nèi)，要求公式（1）增加約束條件δ8，1=1 和δ11，10=1，對應(yīng)的布局方案向量表示θ=[θ1，θ2，…，θ11]中要求元素θ8=1，θ11=10.

表3 設(shè)施間的移動頻率fxy（次）（實例一）Tab.3 Movement frequency fxy between facilities（Example 1）

表4 位置間的距離dij（實例一） 米Tab.4 Distance dij between locations（Example 1）meter

該設(shè)施布局優(yōu)化問題需考慮將9 個設(shè)施分配在9 個位置，故問題的可行解（布局方案）個數(shù)為9!=362 880.通過枚舉法可得到問題的最優(yōu)目標(biāo)函數(shù)值為6 273 m.針對本實例問題，基于TMCMC 的建議優(yōu)化算法的參數(shù)中，無量綱化常數(shù)g0取值10 000，樣本變異系數(shù)取0.3.圖2 描述了基于TMCMC 的建議優(yōu)化算法一次典型求解過程（每一階段的樣本個數(shù)取100）中最優(yōu)目標(biāo)函數(shù)值隨迭代階段的變化，圖3 描述了該求解過程中溫度參數(shù)隨迭代階段的變化.

圖2 典型求解過程中最優(yōu)目標(biāo)函數(shù)值隨迭代階段的變化（實例一）Fig.2 Optimal objective function value at different stages in a typical optimization run（Example 1）

圖3 典型求解過程中溫度參數(shù)隨迭代階段變化（實例一）Fig.3 Temperature parameter at different stages in a typical optimization run（Example 1）

為檢驗基于TMCMC 的施工現(xiàn)場設(shè)施布局優(yōu)化算法的穩(wěn)定性，表5 給出了針對案例問題的500 次建議優(yōu)化算法求解的統(tǒng)計結(jié)果.作為對比，表5 也提供了遺傳算法（Genetic Algorithm，GA）的500 次求解的統(tǒng)計結(jié)果.本文采用的遺傳算法為雙交叉算子遺傳算法，其與傳統(tǒng)遺傳算法相比，更適用于組合優(yōu)化問題，且性能更優(yōu)[14].其交叉操作采用交叉掩碼和部分映射雜交算子作為雙交叉算子，既能保護(hù)優(yōu)質(zhì)染色體，又不影響劣質(zhì)染色體的進(jìn)化，從而提高種群的收斂速度.其變異操作采用染色體內(nèi)部變異的方式，即隨機(jī)選擇染色體內(nèi)的兩個基因進(jìn)行交換.考慮到計算資源對兩種優(yōu)化算法性能的影響，兩種算法的迭代終止原則均取為迭代次數(shù)不超過20 代.

由表5 可知，當(dāng)優(yōu)化算法每代的樣本數(shù)取50時，基于TMCMC 的建議優(yōu)化算法的500 次獨立運行結(jié)果中，有72.4%的頻率可獲得真實最優(yōu)解（對應(yīng)目標(biāo)函數(shù)值6273 m），而基于GA 的優(yōu)化算法的相應(yīng)頻率僅為32.8%.當(dāng)每代的樣本數(shù)增加到100、150 和200 時，兩種優(yōu)化算法獲得真實最優(yōu)解的頻率都隨著樣本數(shù)的增加而提高，且基于TMCMC 的優(yōu)化算法獲得真實最優(yōu)解的頻率更高，這表明基于TMCMC的優(yōu)化算法具有更好的求解穩(wěn)定性.

表5 基于TMCMC 的建議優(yōu)化算法和GA獨立運行500 次的統(tǒng)計結(jié)果（實例一）Tab.5 Statistical results of 500 independent runs using GA and TMCMC-based proposed optimization algorithm（Example 1）

此外，表5 也提供了兩種算法獲得的最優(yōu)解的目標(biāo)函數(shù)值的統(tǒng)計結(jié)果（最大值、最小值、平均值及標(biāo)準(zhǔn)差）.對比可知，在每代樣本數(shù)相同的情況下，基于TMCMC 的優(yōu)化算法獲得最優(yōu)解的目標(biāo)函數(shù)值的最大值（最差情況下）小于基于GA 的優(yōu)化算法的相應(yīng)數(shù)值，且樣本標(biāo)準(zhǔn)差更小，這再次驗證了基于TMCMC 的優(yōu)化算法的求解穩(wěn)定性.同時，在每代不同樣本數(shù)下兩種算法的單次運行平均耗時如表5 中的第8 列所示.對比可見，在每代樣本數(shù)相同的情況下，基于TMCMC 的建議優(yōu)化算法單次運行平均耗時更短，但性能（獲取全局最優(yōu)解的穩(wěn)定性）更優(yōu)，說明基于TMCMC 的優(yōu)化算法更為高效（與GA 算法相比）.

3.2 工程實例二（16 項臨時設(shè)施）

本實例來源于某房地產(chǎn)工程項目，該項目總建筑面積約17.88 萬m2，其中地上建筑面積12.88 萬m2，地下建筑面積5 萬m2.在主體施工階段需考慮將16 個臨時設(shè)施分配至16 個預(yù)定位置內(nèi)，同樣假定每個預(yù)定位置都足以容納任一臨時設(shè)施.16 個臨時設(shè)施的具體信息和編號如表6 所示.一天內(nèi)臨時設(shè)施間的物流頻次如表7 所示，所涉及的位置間的距離如表8 所示.因正門和側(cè)門的位置預(yù)先已確定，分別分配在位置1（設(shè)施8，側(cè)門）和位置10（設(shè)施11，正門）內(nèi).該優(yōu)化問題需考慮將14 個臨時設(shè)施分配在14 個位置，故問題的可行解個數(shù)為14!=8.718×1010.

表6 臨時設(shè)施信息（實例二）Tab.6 Information of temporary facilities（Example 2）

針對本實例問題，基于TMCMC 的建議優(yōu)化算法的參數(shù)中，無量綱化常數(shù)g0取500 000，樣本變異系數(shù)取值0.1.圖4 描述了基于TMCMC 的建議優(yōu)化算法一次典型求解過程（每一階段樣本數(shù)取1 000）中最優(yōu)目標(biāo)函數(shù)值隨迭代階段的變化，圖5 描述了該求解過程中溫度參數(shù)隨迭代階段的變化.為比較建議優(yōu)化算法和GA 算法的性能，表9 給出了針對本實例問題的500 次建議優(yōu)化算法和GA 算法求解的統(tǒng)計結(jié)果.兩種算法的迭代終止原則均取迭代次數(shù)不超過100 代.由于本實例問題可行解的個數(shù)過多（14!=8.718×1010），無法采用枚舉法來得到問題的真實最優(yōu)解，故采用考察中優(yōu)化算法（建議優(yōu)化算法和GA 算法每代采用不同樣本，獨立運行500 次）所有求出“最優(yōu)解”中的最優(yōu)者作為“真實全局最優(yōu)解”，其目標(biāo)函數(shù)值267 577（表9 中第5 列-最小值中的最小數(shù)）作為“真實最優(yōu)目標(biāo)函數(shù)值”，并以此作為比較建議優(yōu)化算法和GA 算法的基礎(chǔ).同時，與實例一的問題相比，實例二的設(shè)施布局優(yōu)化問題中可行解的個數(shù)為實例一的240 240（即14!/9! ）倍，問題復(fù)雜程度急劇上升，故在建議優(yōu)化算法和GA 算法中每代的樣本數(shù)取較大數(shù)值，即表9 中的500、1 000、1 500、2 000.

表7 設(shè)施間的移動頻率fxy（次）（實例二）Tab.7 Movement frequency fxy between facilities（Example 2）

表8 位置間的距離dij（實例二） 米Tab.8 Distance dij between locations（Example 2） meter

圖4 典型求解過程中最優(yōu)目標(biāo)函數(shù)值隨迭代階段的變化（實例二）Fig.4 Optimal objective function value at different stages in a typical optimization run（Example 2）

圖5 典型求解過程中溫度參數(shù)隨迭代階段變化（實例二）Fig.5 Temperature parameter at different stages in a typical optimization run（Example 2）

表9 基于TMCMC 的建議優(yōu)化算法和GA 獨立運行500 次的統(tǒng)計結(jié)果（實例二）Tab.9 Statistical results of 500 independent runs using GA and TMCMC-based proposed optimization algorithm（Example 2）

通過對比表9 和表5 的結(jié)果可知，基于TMCMC的建議優(yōu)化算法和GA 算法在實例二中的求解統(tǒng)計結(jié)果不如實例一中的結(jié)果理想.但考慮到兩個實例問題中差距巨大的可行解個數(shù)和復(fù)雜程度，上述的結(jié)果也較為合理.同時，由表9 可知，當(dāng)每代的樣本數(shù)取500 時，基于TMCMC 的建議優(yōu)化算法的500次獨立運行結(jié)果中，有41.0%的頻率可獲得“真實全局最優(yōu)解”（對應(yīng)目標(biāo)函數(shù)值267 577 m），且其獲得“真實全局最優(yōu)解”的頻率隨著樣本數(shù)的增加而提高.當(dāng)每代樣本數(shù)取2 000 時，其獲得“真實全局最優(yōu)解”的頻率為80.4%.作為對比，GA 優(yōu)化算法在每代樣本數(shù)取500、1 000、1 500、2 000 時獲得“真實全局最優(yōu)解”的頻率幾乎全部為0，最高值僅為0.6%.此外，由表9 可知，在每代樣本數(shù)相同的情況下，基于TMCMC 的建議優(yōu)化算法獲得的最優(yōu)目標(biāo)函數(shù)值的平均值更接近2 675 577 m，且標(biāo)準(zhǔn)差大大小于GA 算法的相應(yīng)數(shù)值.由此可見，與GA 算法相比，基于TMCMC 的優(yōu)化算法在獲取全局最優(yōu)解的穩(wěn)定性上有較大的改進(jìn).同時，由表9 中第8 列兩種算法的單次運行平均耗時的對比可見，與GA 算法相比，基于TMCMC 的建議優(yōu)化算法計算效率更高，能夠以更短的單次運行平均耗時獲得更優(yōu)的性能（獲取全局最優(yōu)解的穩(wěn)定性）.

4 結(jié)論

本文針對涉及較多設(shè)施的施工現(xiàn)場布局優(yōu)化問題，基于TMCMC 方法進(jìn)行啟發(fā)式優(yōu)化算法的研究，主要研究結(jié)論如下：

1）在布局方案的向量表示下，可通過合理構(gòu)造的概率分布函數(shù)，將施工現(xiàn)場設(shè)施布局優(yōu)化問題轉(zhuǎn)化為高維空間中的隨機(jī)抽樣問題，進(jìn)而利用TMCMC方法來進(jìn)行隨機(jī)抽樣、并獲取最優(yōu)解.

2）為適應(yīng)離散型變量優(yōu)化問題的不同特性，本文提出的啟發(fā)式算法的框架基礎(chǔ)需從原始TMCMC針對的連續(xù)型概率密度分布函數(shù)的隨機(jī)取樣轉(zhuǎn)變?yōu)殡x散型概率分布函數(shù)的隨機(jī)取樣，進(jìn)而需修改其中的馬爾可夫鏈狀態(tài)點的產(chǎn)生方法.

3）通過實例驗證，與應(yīng)用較廣的GA 算法相比，基于TMCMC 的啟發(fā)式優(yōu)化算法在全局最優(yōu)解的獲取穩(wěn)定性上有較大改進(jìn).