基于差分粒子群算法的裝配式住宅項目進度優(yōu)化研究

趙 平，吳 昊，李萍萍，喬媛媛

（西安建筑科技大學土木工程學院，陜西 西安 710055）

裝配式建筑在施工的過程中可以改變傳統(tǒng)建筑“濕作業(yè)”的生產方式，減少揚塵、無交叉污染、減少CO2排放、緩解日趨嚴重的霧霾污染問題，是未來建筑產業(yè)發(fā)展的必然趨勢．但是目前裝配式建筑在我國發(fā)展十分緩慢，主要的原因是裝配式建筑在進度上和傳統(tǒng)現(xiàn)場澆筑方式相比并沒有發(fā)揮太多的優(yōu)勢，究其原因是施工過程各環(huán)節(jié)協(xié)調配合的問題，而解決這一問題的關鍵就是裝配式建筑施工中的合理調度問題．

裝配式建筑的調度問題，是在滿足施工工序的邏輯關系和資源約束的條件下，對施工工序和資源進行合理的安排，控制好工序的開始、結束時間，以達到工期優(yōu)化的目標，也就是單執(zhí)行模式資源受限項目調度問題(Single-Mode Resource-constrained Project Scheduling Problem，簡稱SRCPSP)．雖然此類問題被證明是Np難問題[1]，但國內外學者做了大量的研究并取得了豐碩的研究成果．一般采用數(shù)學規(guī)劃、動態(tài)規(guī)劃[2-3]等精確算法來求解小規(guī)模調度問題的最優(yōu)解；采用啟發(fā)式算法，如遺傳算法、模擬退火算法、蟻群算法、粒子群算法等[4-7]來求解較大規(guī)模調度問題的最優(yōu)解．但是由于各個算法都存在一定的缺陷，單純應用某一算法優(yōu)化調度問題時，就會導致性能較差的結果，進行算法相結合可以實現(xiàn)二者之間的優(yōu)勢互補，提高算法優(yōu)化的性能．本文提出的差分粒子群算法(DEPSO)通過差分算法(DE)彌補了粒子群算法(PSO)容易陷入局部最優(yōu)和搜索精度相對較低的缺陷，并將全局優(yōu)化性能較好的差分算法和收斂速度較快的粒子群算法優(yōu)勢結合在一起，加強兩個種群間的信息融合，提高整個種群的進化能力，達到增強混合算法的求解能力．

1 問題描述和數(shù)學模型

1.1 問題描述

工程項目的施工過程屬于資源約束的調度問題，資源主要分為可更新資源和不可更新資源．可更新資源是指總量雖然有限，但一旦結束某項任務開始下個任務時資源可更新為原來的總量，如：勞動力、設備等；不可更新資源是指該項資源會隨著工程的開展而不斷減少，如使用的原材料、資金等．

裝配式住宅項目進度優(yōu)化問題是以最短工期為最優(yōu)目標，假設裝配式住宅項目中每一項工作都只有一種執(zhí)行模式，緊前工作或緊后工作的邏輯關系是確定的，要求所有緊前工作結束后，緊后工作立刻開始，執(zhí)行過程沒有間歇；而且不考慮不可更新資源的約束情況，只考慮可更新資源的約束，在滿足各個工作之間的邏輯關系約束和資源需求約束的條件下，對各項工作的開始或結束時間進行合理安排，使工期最優(yōu)[8]．

1.2 裝配式住宅項目模型的建立

裝配式住宅項目共包含N項工作，第一項工作1表示項目的開始工作，最后一項工作N表示項目的結束工作，是虛工作．進度控制目的是在滿足裝配式住宅項目工作合理搭接的前提下，通過合理安排各項工作的資源，使工期最小化．

工作i的開始時間：

工作i的完成時間：

建設項目需要J種可更新資源，其中第j種資源在t時刻的供給量為要完成第i項工作需要若干種資源，其中對第j種資源的需求量rji；要求所使用的各種資源總和不能超過資源總量．項目在某一時刻對某種資源的需求不能超過該資源的供給量．則資源約束表示為：

2 基于差分粒子群優(yōu)化的裝配式住宅項目調度算法

2.1 差分算法

差分算法主要用于求解優(yōu)化最小值的問題，是從隨機產生的初始群體開始，求解父代個體間隨機選取的兩個個體差值的基礎之上與另外一個隨機選取個體的加權求和生成變異種群．在父代個體和變異個體間執(zhí)行交叉操作形成一個新的種群，然后通過比較由交叉算子生成的個體和相應父代個體的適應值優(yōu)劣，如此反復迭代和進化，保留優(yōu)良個體，舍棄劣質個體，直到找到最優(yōu)解．需要注意的是整個運行過程中保持群體的規(guī)模不變．

設原始種群X包含N個候選解，定義 [1,]r∈R為空間的維度，空間內的個體，則變異個體為

根據(jù)交叉操作由式(8)可生成新的一個種群表示為：

通過交叉后的個體Pir和父代個體的適應度值，保留較優(yōu)的適應度值．

2.2 差分混合粒子群算法

粒子群算法(PSO)，是基于隨機群體的一種新型智能優(yōu)化方法[9]．其算法簡單，易于操作，魯棒性較強，收斂速度較快，但在求解的過程中容易陷入局部最優(yōu)而且搜索精度相對較低．基于PSO不足之處，Yuhui Shi[10]對基本粒子群算法進行了優(yōu)化，通過引入一個慣性權重因子ω，調整上下時刻之間速度的影響，平衡全局和局部的搜索能力，從而提高了該算法的精確性．由于ω對算法性能影響較大，一般的做法是將其開始設置較大隨著迭代次數(shù)的增加而逐漸減小，通常

現(xiàn)定義維度為R的空間中個數(shù)為N的粒子在以一定的速度飛行，第j個粒子的位置和速度分別表示為和該粒子所經歷的最好位置為全局最優(yōu)位置為Q，它表示Pj中的最優(yōu)值，式(9)式(10)分別表示了粒子的速度和位置更新公式．

2.3 差分混合進化粒子群算法

PSO的特點是在優(yōu)化求解過程中前期收斂速度較快，而在后期求解中如果沒有新的粒子來更新當前最好位置時，那么群體中的其他粒子就會朝著這個當前最好位置靠近，由于粒子都集中到較小范圍的區(qū)域，將會導致適應值變化緩慢或者無變化，算法就會出現(xiàn)停滯現(xiàn)象[11]．通過DE 的變異操作可以對個體的最好位置進行不斷地更新，增加了全局的搜索能力，而交叉操作提高了局部搜索能力，選擇操作則產生了優(yōu)秀的個體．

DEPSO就是通過一種新的信息互融機制，使兩個種群中的信息能夠互相交流，從而避免了某些個體得到錯誤的判斷信息而陷入局部最優(yōu)點．采取非線性慣性權重策略來對權重進行改進，以進一步提高其優(yōu)化性能，權重優(yōu)化狀態(tài)方程如式(11)．

其中m為控制因子．用來控制ω與t變化曲線的平滑度，通常取3．

為了克服兩個種群中的粒子在后期的迭代進化中出現(xiàn)停滯現(xiàn)象，引入一種變異機制，也就是說如果粒子在設定的最大迭代次數(shù)內出現(xiàn)了停滯現(xiàn)象即發(fā)生變異，該粒子將被任一新位置所取代，具體實現(xiàn)過程如式(12)．

其中∶η代表適應度函數(shù)在整個種群中的最小值，m是允許停滯的最大迭代次數(shù)，是搜索的范圍．

2.4 混合算法的參數(shù)設置及實現(xiàn)步驟

合理的設置算法的參數(shù)能更好的發(fā)揮算法的優(yōu)化性能，參考Kennedy和Eberahart對PSO算法以及Price[12]對DE算法參數(shù)設置研究，本文算法基本參數(shù)設置如下:群體規(guī)模N=100、最大迭代次數(shù)最大慣性權重最小慣性權重加速因子C1=2=C2、縮放因子τ=0.5、變異概率CR=0.5、設置迭代計數(shù)器t=0．

本文提出的混合算法DEPSO實現(xiàn)步驟如下:

第一步：基本參數(shù)設置，群體規(guī)模N、最大迭代次數(shù)Tmax、最大慣性權重wmax、最小慣性權重加速因子C1和C2縮放因子、變異概率CR、設置迭代計數(shù)器t=0．

第二步：將群體等分成兩個種群PPSO和PDE，隨機產生兩個粒子，初始化PPSO和PDE而且讓二者位于不同的區(qū)域．

第三步：根據(jù)式(7)、式(8)對PDE群體中所有個體執(zhí)行變異、交叉、選擇操作．

第四步：根據(jù)式(9)、(10)和式(11)對PPSO群體中所有個體執(zhí)行速度、位置更新．

第五步：通過比較適應值，選出PPSO群體中最佳個體GPSO．

第六步：通過比較適應值，選出DEP 群體中最佳個體GDE．

第七步：比較GPSO、GDE優(yōu)劣，選擇最佳個體作為PPSO和PDE下一代進化依據(jù)．

第八步：判斷個體是否有停滯現(xiàn)象，如果有，按式(12)執(zhí)行變異操作．

第九步：更新迭代計數(shù)器t=t+1并記錄當前整個群體中最佳個體，如果滿足精度要求或整個進化已達到最大迭代次數(shù)，就終止算法，輸出全局最優(yōu)位置的粒子并生成調度方案，否則轉至第三步．

3 實例分析

現(xiàn)以某地某保障性住宅項目為例，本工程主體結構形式為剪力墻結構，共5幢，每幢4個單元六層，建筑面積19 225 m2，占地面積3 204 m2．單幢樓東西長63.02 m，南北寬11.02 m．層高為3 m，室內凈高2.89 m．主體結構部分內、外墻板均采用預制裝配式墻體，結構樓板、樓梯部分采用疊合板，樓梯、陽臺均采用預制裝配式形式，空調板、節(jié)點、接縫等采用現(xiàn)場現(xiàn)澆的方式．

通過將施工過程進行科學的施工組織，按樓層將其分為多個施工段．論文以其中一個施工階段為研究對象，設定每項任務只有一種模式，在滿足邏輯關系和資源的約束下，力求使項目的總工期最小，假定建設項目所需預制構件數(shù)量能滿足施工要求，預制構件的運輸、固定、堆放等都能保證裝配施工順利進行．

施工企業(yè)在以往的進度計劃的編制過程中，采用的是Project軟件，并以此作為項目的執(zhí)行計劃．從圖1所示的工程項目網絡圖可以得到關鍵線路上的工期為2.85 d，但是在計劃的編制過程中，管理者幾乎沒有考慮資源的約束問題，依靠關鍵線路得到的項目工期是不合理的．

圖1 項目網絡圖Fig.1 Project network diagram

表1 項目任務信息列表Tab.1 Project task information

本工程每項工作的工期及資源需求量見表1．由于這里是以標準層為研究對象故表中前幾項項工作中某些任務不需要專業(yè)的人員和設備，從表中可以看出預制剪力墻結構施工主要分為：墻體部分、現(xiàn)澆部分以及樓梯、樓板部分．

由于承建公司同時開展多個項目，故依據(jù)項目部的資源實際可調配情況，選取所有活動影響系數(shù)較高的3種可更新資源，分別為專業(yè)操作人員(司機、混凝土工、木工、鋼筋工等)、可用吊裝及其輔助設備(塔吊、電焊機、葫蘆等)、其他可用設備(鋼梁、鋼絲繩等)．

本文采用差分算法(DE)、粒子群算法(PSO)、差分粒子群算法(DEPSO)對上述工程的調度問題進行求解，每種算法運行50次，分別求出平均工期以及工期的標準差，進而比較算法的合理性及性能的先進性．用Matlab軟件實現(xiàn)算法并用Excel進行處理，運行結果如表2所示．

表2 算法結果對比Tab.1 The results of algorithm

從表2可以看出，三種算法均對裝配式項目工期起到了優(yōu)化作用，其中DEPSO在求解工期方面有較大的優(yōu)勢，經過多次運算后得到的平均工期為3.40 d、標準差為0.126，在三種算法中最優(yōu)，DE和PSO在裝配式工期優(yōu)化方面效果較DEPSO差．在既有資源約束相同的情況下，通過DESPSO所得到的最優(yōu)工期比同行業(yè)平均裝配施工工期短，較好的實現(xiàn)了預期的目標，可為同類問題的進度優(yōu)化提供很好的借鑒意義．

DEPSO混合算法通過加強兩個種群之間的信息互融機制擴大了搜索的范圍．另外，通過變異機制解決算法在迭代過程中的停滯現(xiàn)象，同時通過非線性慣性權重策略對其性能進行調整，使其跳出局部最優(yōu)進而實現(xiàn)全局最優(yōu)．最后得到的最優(yōu)調度序列為（1，2，3，4，5，7，6，8，9，10，11，12，13，14，15，18，19，16，17，20，21，22），項目優(yōu)化后的標準層工期為3.40 d．

4 結論

(1) 單一的算法在求解復雜項目的進度優(yōu)化中不僅運行較慢，而且搜索全局最優(yōu)解的的能力較低、求解精度不高；而通過算法的改進使其優(yōu)勢互補，可以提高其全局搜索能力，進而提高尋求最優(yōu)解的概率．

(2) 建立的DEPSO混合算法通過在二者之間建立一種信息互融機制，使兩種算法的有機結合；改進后的混合算法克服了DE收斂速度慢和PSO容易局部最優(yōu)的缺陷，使得算法的性能更加合理、高效．

(3) 通過DEPSO求解構建的裝配式住宅項目調度數(shù)學模型，得到了在有限資源下的最優(yōu)工期，對工程實踐有一定的指導作用．但裝配式住宅項目優(yōu)化過程中受多種資源的約束，文中只分析了影響較大的三種可更新資源，建議將受約束的不可更新資源考慮進去，使優(yōu)化的結果更接近實際．

Reference

[1]KOLIS R, HARTMANN S. Experimental investigation of heuristics for resource-contrained project scheduling:an update[J]. European Journal of Operational Research,2006, 174(1):23-37.

[2]李雪, 聶蘭順, 齊文艷. 基于近似動態(tài)規(guī)劃的動態(tài)車輛調度算法[J]. 中國機械工程, 2015, 26(5): 682-688.LI Xue, NIE Lanshun, QI Wenyan.Dynamic vehicle scheduling algorithm based on approximate dynamic programming [J]. China Mechanical Engineering, 2015,269(5): 682-688.

[3]黃風林,屈端,范崢.數(shù)學規(guī)劃法優(yōu)化氫網絡的應用研究[J].化學工程,2015,43(3):70-73.HUANG Fenglin,QU Duan,FAN Zheng .Application research on mathematical programming methodology forhydrogen network optimization[J]. Chemical Engineering,2015,43(3):70-73.

[4]張光明,劉東峰,劉春峰.基于遺傳算法的兩階段建筑工程多目標優(yōu)化[J].西安建筑科技大學學報(自然科學版),2011,43(3):410-416.ZHANG Guangming, LIU Dongfeng, LIU Chunfeng.Comprehensive optimization for multiple objectives inconstruction based on GA[J]. J. Xi'an Univ. of Arch. &Tech. (Natural Science Edition), 2011,43(3):410-416.

[5]王秋平,史榮,張琦.基于改進蟻群算法和網絡GIS分析的慢行交通最優(yōu)路徑選擇[J].西安建筑科技大學學報(自然科學版),2013,45(5):668-674,687.WANG Qiuping, SHI Rong, ZHANG Qi. Optimal path selection of slow traffic based on GIS network analysis[J]. J. Xi'an Univ. of Arch. & Tech. (Natural Science Edition), 2013,45(5): 668-674, 687.

[6]劉海霞,李仁旺,李學.基于遺傳模擬退火算法的制造網格資源調度策略[J].計算機工程與應用,2008,44(6):234-237.LIU Haixia, LI Renwang, LI Xue. Resource scheduling strategy in manufacture grid based on genetic algorithms and simulated anealing[J]. Computer Engineering and Application, 2008,44(6): 234-236.

[7]甄彤,郭嘉,吳建軍.粒子群算法求解糧堆溫度模型參數(shù)優(yōu)化問題[J].計算機工程與應用,2012,48(12):206-208.ZHEN Tong, GUO Jia, WU Jianjun. To solve problems of mathematical model of temperature field for grain based on PSO[J]. Computer Engineering and Applications, 2012, 48(12): 206-208.

[8]劉士新.項目優(yōu)化調度理論與方法[M].北京:機械工業(yè)出版社,2007.LIU Shixin. Theory and method of project optimization scheduling[M]. Beijing: Mechanical Industry Press, 2007.

[9]KENNEDY J,EBERHARTR C. Particle Swarm Optimization[C]//Proc. IEEE Int. Conf. on Neural Networks,Piscataway: IEEE, 1995: 1942-1948.

[10]SHI Y, EBERHARTR C. A Modified Particle Swarm Optimizer[C]//Proc. IEEE World Congress on Computational Intelligence, Piscataway: IEEE, 1998:69-73.

[11]池元成,方杰,蔡國飆.基于差分進化和粒子群優(yōu)化算法的混合優(yōu)化算法[J].計算機工程與計,2009,30(12):2963- 2965.CHI Yuancheng, FANG Jie,CAI Guobiao. Hybrid optimization algorithm based on differential evolution and particle swarm optimization[J]. Computer Engineering and Design, 2009,30 (12):2963-2965.

[12]PRICE K. An introduction to differential evolution: new ideas in optimization[M].. Maidenhead: McGraw-Hill,1999:79-1087.