基于罰函數(shù)遺傳算法的水土保持土方調(diào)配優(yōu)化

霍正剛, 王子旸, 查曉庭, 張森森, 陸孟瑤

(揚(yáng)州大學(xué)建筑科學(xué)與工程學(xué)院, 江蘇 揚(yáng)州 225127)

隨著中國(guó)城市化進(jìn)程的快速發(fā)展, 如何平衡規(guī)模不斷擴(kuò)大的城市建設(shè)和城市的水土保持已成為城市規(guī)劃和建設(shè)過(guò)程中亟需解決的問(wèn)題之一, 而環(huán)境友好、資源友好型的工程項(xiàng)目有利于我國(guó)經(jīng)濟(jì)的持續(xù)發(fā)展．水土保持項(xiàng)目涉及場(chǎng)平工程、土石壩工程、路堤工程和地下工程等, 這些工程均須考慮土方的調(diào)配問(wèn)題, 包括地上與地下之間的調(diào)配、不同場(chǎng)地間的調(diào)配等．目前, 土方調(diào)配問(wèn)題通常歸結(jié)為管理運(yùn)籌學(xué)中的運(yùn)輸問(wèn)題,并將土方調(diào)配優(yōu)化模型問(wèn)題轉(zhuǎn)化為線性關(guān)系, 以線性規(guī)劃為基礎(chǔ)建立理論框架, 運(yùn)用數(shù)學(xué)方法得到最優(yōu)解．景明等[1]采用LINGO工具對(duì)大型土方調(diào)運(yùn)問(wèn)題進(jìn)行線性規(guī)劃求解, 所得結(jié)果較為準(zhǔn)確; Artun等[2]通過(guò)垂直優(yōu)化的單純形法求解線形規(guī)劃模型, 較大幅度地降低了優(yōu)化后的成本; Karimi等[3]考慮到土方挖填區(qū)體積和單價(jià)的模糊性, 提出一種土方調(diào)配模糊線性規(guī)劃模型; Liu等[4]建立具有模糊參數(shù)和約束的全系數(shù)模糊線性規(guī)劃土方分配模型, 有效克服了傳統(tǒng)土方分配方法的不足; Wan等[5]利用線性規(guī)劃模型, 采用表格運(yùn)算法對(duì)土方調(diào)配進(jìn)行優(yōu)化, 最小元素法確定初始運(yùn)輸方案,并通過(guò)閉路法優(yōu)化方案, 最終得到最小土方運(yùn)費(fèi)的方案．這些研究成果顯示, 線性規(guī)劃因采用嚴(yán)格的數(shù)學(xué)方法建模, 故不管是表格法還是表上作業(yè)法其計(jì)算量均較大, 且計(jì)算時(shí)易陷入局部最優(yōu)解．Katebi等[6]采用一種穩(wěn)健優(yōu)化方法對(duì)傳統(tǒng)道路施工中土方調(diào)配的規(guī)劃模型進(jìn)行修正, 使該模型具有較好的魯棒性; Villar等[7]利用ICOM(intelligent method of optimized mass compensation)方法對(duì)經(jīng)典的土方挖掘和填充過(guò)程進(jìn)行優(yōu)化, 該方法能有效降低土方挖掘與填充的成本; Akgul等[8]運(yùn)用無(wú)人機(jī)和全球衛(wèi)星導(dǎo)航系統(tǒng), 提高了土方計(jì)算中網(wǎng)格的分辨率, 使土方調(diào)配精度大幅提高; Shehadeh等[9]基于進(jìn)化多目標(biāo)方法提出一種新型優(yōu)化系統(tǒng), 使時(shí)間和成本分別下降了14.35%和9.50%．這些方法的優(yōu)點(diǎn)是計(jì)算方便, 但在模型的解釋性上不如線性規(guī)劃, 計(jì)算結(jié)果的準(zhǔn)確性也存在不足．本文以某水土保持項(xiàng)目為研究對(duì)象, 擬采用線性規(guī)劃法并結(jié)合罰函數(shù)基因遺傳算法對(duì)該水土保持土方調(diào)配進(jìn)行快速優(yōu)化, 為解決類(lèi)似土運(yùn)問(wèn)題提供參考．

1 土方調(diào)配模型

1.1 基本假設(shè)

本文建立的土石方調(diào)配模型基于以下幾個(gè)假設(shè):

1) 土方之間的運(yùn)輸路線按照最短直線距離進(jìn)行．由于土方調(diào)配工程中施工現(xiàn)場(chǎng)地形的不規(guī)則性和不一致性, 通常采用面積中心或幾何中心計(jì)算兩個(gè)區(qū)域之間的距離．

2) 每個(gè)工段既可以是挖區(qū)也可以是填區(qū), 各挖填區(qū)的土方量已知, 且滿足挖填總體平衡, 忽略挖填土方的臨時(shí)變更量．

3) 因?qū)嶋H工況中, 中轉(zhuǎn)場(chǎng)地只是起到臨時(shí)存儲(chǔ)作用, 并不影響最終土方調(diào)運(yùn)區(qū)域之間的調(diào)配關(guān)系, 故不考慮中轉(zhuǎn)場(chǎng)地的影響．

1.2 變量參數(shù)符號(hào)及含義

土方調(diào)配的費(fèi)用組成主要由單位體積綜合單價(jià)、運(yùn)距及土方調(diào)配量構(gòu)成,表1 給出了本文模型中各參數(shù)的符號(hào)及含義．

表1 變量符號(hào)及含義

1.3 綜合單價(jià)

1.4 目標(biāo)函數(shù)及求解

1.4.1 目標(biāo)函數(shù)及其約束條件

在同一工段內(nèi)進(jìn)行挖掘和填筑時(shí), 因不涉及運(yùn)輸調(diào)配量, 故有Xii=0; 而各工段間的距離在設(shè)計(jì)階段已經(jīng)確定, 故Sij為常量．因此, 總運(yùn)費(fèi)的線性規(guī)劃函數(shù)

(1)

則土方調(diào)配模型的目標(biāo)函數(shù)

(2)

其約束條件為

(3)

1.4.2 帶罰函數(shù)的目標(biāo)函數(shù)

為解決遺傳算法求解土方調(diào)運(yùn)過(guò)程中的約束優(yōu)化問(wèn)題時(shí)可能存在不可行解產(chǎn)生偏離可行域的解和遺傳因子作用于可行解后產(chǎn)生不可行解的問(wèn)題[12], 本文采用罰函數(shù)使其轉(zhuǎn)化為無(wú)約束問(wèn)題后再求解．此時(shí), 無(wú)約束帶罰函數(shù)的目標(biāo)函數(shù)

g(Xij)=f(Xij)/Cij+kp(Xij),

(4)

其中k為懲罰因子．當(dāng)Xij取值符合約束等式條件時(shí), 罰函數(shù)p(Xij)不起作用或作用很小; 當(dāng)Xij取值不符合約束等式條件時(shí),p(Xij)起作用, 此時(shí)g(Xij)增大, 適應(yīng)度變小, 不易被復(fù)制而遺傳給下一代．因此, 式(3)中的等式約束利用罰函數(shù)變成無(wú)約束形式, 令約束函數(shù)

(5)

(6)

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

1.4.4 遺傳算法求解目標(biāo)函數(shù)

遺傳算法是一種模擬自然界優(yōu)勝劣汰、適者生存的算法[14]．其本質(zhì)是一種排序的算法或是一種選優(yōu)的算法, 圖1給出了這種算法的步驟．但是傳統(tǒng)的遺傳算法運(yùn)算量較大,收斂速度較慢, 且當(dāng)調(diào)配數(shù)目達(dá)到一定程度時(shí)易陷入局部最優(yōu)而不能得到最優(yōu)解．為解決這些問(wèn)題, 本文在目標(biāo)函數(shù)上引入罰函數(shù)[15], 此時(shí)線性規(guī)劃問(wèn)題的求解步驟為:

圖1 遺傳算法流程圖Fig.1 The flow chart of genetic algorithm

1) 確定所需種群數(shù)量的大?。疚膶?shí)例中選取初始種群大小為30, 并以各區(qū)域間調(diào)運(yùn)土方量Xij作為基因編碼個(gè)體[16], 用二進(jìn)制編碼將個(gè)體基因編碼成一個(gè)二進(jìn)制符號(hào)串, 其中每一個(gè)符號(hào)串代表一條染色體．為避免初始種群遠(yuǎn)離全局最優(yōu)解編碼空間, 根據(jù)土方量變動(dòng)區(qū)間隨機(jī)生成初始種群．

2) 定義一組優(yōu)化函數(shù)．以總運(yùn)費(fèi)的線性規(guī)劃函數(shù)式(1)為優(yōu)化函數(shù), 式(2)為目標(biāo)函數(shù), 加入罰函數(shù)及其他限制參數(shù)得到適應(yīng)度函數(shù)．

3) 計(jì)算各個(gè)體的適應(yīng)度．以0.60的交叉率對(duì)個(gè)體進(jìn)行基因交叉操作, 以0.01的變異率對(duì)子代個(gè)體進(jìn)行變異操作．為提高子代中適應(yīng)度高的個(gè)體的比例, 采用輪盤(pán)賭法[17]選擇個(gè)體．

4) 對(duì)新產(chǎn)生的子代個(gè)體進(jìn)行適應(yīng)度計(jì)算, 并進(jìn)行種群的更新．

5) 滿足終止條件時(shí)算法終止, 并對(duì)原始編碼信息根據(jù)編碼的方向進(jìn)行二進(jìn)制解碼, 輸出最終結(jié)果, 即區(qū)域間調(diào)運(yùn)土方量Xij．

2 仿真實(shí)驗(yàn)

2.1 項(xiàng)目簡(jiǎn)介

揚(yáng)州市某居住項(xiàng)目土方施工區(qū)分為建筑物區(qū)、道路廣場(chǎng)區(qū)、綠化區(qū)．其中, 建筑物區(qū)包含基礎(chǔ)開(kāi)挖工段W1/T1、場(chǎng)地平整工段W2/T2、場(chǎng)地清淤工段W3/T3; 道路廣場(chǎng)區(qū)分為管線施工段W4/T4、場(chǎng)地平整工段W5/T5、場(chǎng)地回填工段W6/T6; 綠化區(qū)分為綠化覆土工段W7/T7、綠地開(kāi)挖工段W8/T8、綠地回填工段W9/T9．根據(jù)設(shè)計(jì)方提供的數(shù)據(jù), 此項(xiàng)目的開(kāi)挖及回填的土方量如表2所示．表3給出了不同工段間的運(yùn)輸距離Sij．

表2 各施工段開(kāi)挖填筑土方量

表3 不同工段間的運(yùn)輸距離Sij

2.2 模型簡(jiǎn)化與約束矩陣

2.2.1 變量及罰函數(shù)個(gè)數(shù)簡(jiǎn)化

如果i區(qū)域挖方量Wi為0.00 m3, 則所有從i區(qū)域調(diào)運(yùn)出的Xij為0.00 m3．同理, 若j區(qū)域填方量Ti為0.00 m3, 則所有調(diào)往j區(qū)域的Xij為0.00 m3, 且挖填自給區(qū)域的Xii=0.00 m3, 故該項(xiàng)目的未知變量Xij可從81個(gè)簡(jiǎn)化至12個(gè),約束等式從18個(gè)簡(jiǎn)化為7個(gè)．此時(shí),簡(jiǎn)化后的罰函數(shù)為p(Xij)=(X15+X16+X17+X18-7.10)2+(X35+X36+X37+X38-1.90)2+(X95+X96+X97+X98-1.68)2+(X15+X35+X95-0.45)2+(X16+X36+X96-2.96)2+(X17+X37+X97-1.25)2+(X18+X38+X98-6.03)2．適應(yīng)度函數(shù)則化簡(jiǎn)成由12個(gè)變量及7個(gè)約束等式求平方和的復(fù)合函數(shù), 使函數(shù)的求解更方便．

2.2.2 參數(shù)設(shè)置

懲罰系數(shù)k=30.00; 帶罰函數(shù)的目標(biāo)函數(shù)

Q(Xij)=1.48X15+1.70X16+1.21X17+1.30X18+1.10X35+1.39X36+
1.27X37+1.40X38+1.33X95+1.36X96+0.71X97+0.53X98+30.00p(Xij);

約束條件為W=(7.10,0.00,1.91,0.52,0.00,0.00,0.00,0.00,1.68),T=(0.00,0.00,0.00,0.52,0.45,2.96,1.25,6.03,0.00); 隱含條件為Xij≥0．

2.3 結(jié)果與分析

2.3.1 仿真結(jié)果

運(yùn)用MATLAB中遺傳算法工具箱, 輸入帶罰函數(shù)的目標(biāo)函數(shù), 下限設(shè)置為Zeros(12,1), 種群規(guī)模設(shè)為200代．圖2為優(yōu)化過(guò)程的運(yùn)行曲線．從圖2可以看出, 遺傳算法在迭代30次后曲線趨于平穩(wěn), 染色體隨迭代次數(shù)的增加差異較小, 表明已經(jīng)找到最優(yōu)解．在最優(yōu)條件下該項(xiàng)目的土方調(diào)用結(jié)果為:X15=4.30×103m3,X16=1.77×104m3,X17=6.70×103m3,X18=4.23×104m3,X36=8.10×103m3,X37=3.70×103m3,X38=6.90×103m3,X96=3.70×103m3,X97=2.00×103m3,X98=1.11×104m3．

圖2 遺傳算法運(yùn)行曲線Fig.2 Genetic algorithm running curve

2.3.2 不同算法結(jié)果比較

假設(shè)運(yùn)輸?shù)木C合單價(jià)為1.00元·m-3·km-1, 不同算法中各區(qū)域運(yùn)輸距離一致．

1) 表上作業(yè)法. 圖3為該項(xiàng)目實(shí)際工程的傳統(tǒng)表上作業(yè)法求解調(diào)運(yùn)結(jié)果．根據(jù)式(2)將傳統(tǒng)算法下土方調(diào)配量與距離矩陣點(diǎn)乘求和, 表上作業(yè)的運(yùn)輸規(guī)劃按照?qǐng)D3的箭頭方向調(diào)運(yùn), 則運(yùn)費(fèi)總和為13.94萬(wàn)元．此法不能通過(guò)有關(guān)條件簡(jiǎn)化工作, 計(jì)算工作量大而繁雜．

圖3 表上作業(yè)法土方平衡圖(104 m3)Fig.3 Earth balance diagram for table operation method

2) MATLAB自帶線性規(guī)劃工具箱算法. 函數(shù)寫(xiě)成調(diào)用格式, 等式約束矩陣選取W、T, 下限為L(zhǎng)=Zeros(12,0), 線性規(guī)劃優(yōu)化函數(shù)為 [X,faval]=linprog(g(Xij),0,0,W,T,L), 運(yùn)行自帶線性工具箱, 得X=(0.45,2.96,1.25,2.44,0.00,0.00,0.00,1.91,0.00,0.00,0.00,1.68)．取對(duì)應(yīng)的距離矩陣S=(1.48,1.70,1.21,1.30,1.10,1.39,1.27,1.40,1.33,1.36,0.71,0.53)進(jìn)行點(diǎn)乘求和, 得到總費(fèi)用為13.94萬(wàn)元, 結(jié)果與表上作業(yè)法一致．該算法由計(jì)算機(jī)完成, 故計(jì)算速度更快, 人為誤差更少．

3) 罰函數(shù)遺傳算法.根據(jù)公式(2)將帶罰函數(shù)遺傳算法結(jié)果的變量值與運(yùn)輸距離矩陣點(diǎn)乘求和, 得運(yùn)費(fèi)總和為13.75萬(wàn)元．計(jì)算結(jié)果表明, 罰函數(shù)遺傳算法結(jié)果優(yōu)于傳統(tǒng)表上作業(yè)法和線性規(guī)劃工具箱結(jié)果,且收斂速度更快．

上述仿真結(jié)果表明, 與表上作業(yè)法比較,罰函數(shù)遺傳算法避免了手工計(jì)算, 可以通過(guò)具體問(wèn)題條件簡(jiǎn)化方程, 能快速且準(zhǔn)確地得到最優(yōu)解; 與MATLAB自帶線性規(guī)劃工具箱比較, 罰函數(shù)遺傳算法所得調(diào)運(yùn)費(fèi)用結(jié)果優(yōu)于線性規(guī)劃工具箱．因此, 在復(fù)雜問(wèn)題上, 采用罰函數(shù)遺傳算法優(yōu)化線性規(guī)劃問(wèn)題時(shí)求解速度更快, 規(guī)劃質(zhì)量的結(jié)果更精確．

3 結(jié)論

對(duì)于復(fù)雜問(wèn)題, 遺傳算法在求解速度和質(zhì)量上均遠(yuǎn)超常規(guī)方法．仿真實(shí)驗(yàn)過(guò)程表明, 遺傳算法只是一種近似算法,在運(yùn)用的過(guò)程中需要巧妙的構(gòu)思來(lái)簡(jiǎn)化變量數(shù)量, 利用罰函數(shù)避免不可行解或可行域外的解．總之, 罰函數(shù)遺傳算法為計(jì)算約束優(yōu)化問(wèn)題提供了一條可行的途徑, 通過(guò)合理規(guī)劃和合理搭配, 實(shí)現(xiàn)了一定的經(jīng)濟(jì)價(jià)值．