基于遺傳算法的建筑工程計劃管理優化研究

張國富

(滁州職業技術學院 土木工程系，安徽 滁州 239000)

建筑工程計劃管理涉及多個緊密相關的任務，人員和設備資源分配的決策會影響項目成本和完成時間[1-2]。諸如關鍵路徑方法(Critical Path Method，CPM)和程序評估與審查技術(Program Evaluation and Review Technique，PERT)之類的傳統項目計劃方法假定資源的無限可用性。然而在許多建筑環境中，無限制地使用各種資源的假設可能不成立，因為只有固定數量的資源可用，或者獲取額外資源的成本非常高[3]。同時，資源的可用性也可能影響活動持續時間，影響決策者對于執行模式的選擇。因此，本文在資源有限的情況下，通過設計一種基于遺傳算法的計劃管理優化模型來平衡工期和成本之間的矛盾。

1 問題建模

建筑工程項目由一系列活動j組成，用G(V,E)表示活動和活動之間的關系。其中，節點集合V表示活動的集合，弧集合E表示優先關系。在項目網絡G(V,E)中，活動從0開始編號，第J+1號位置。其中活動0和J+1是“虛擬”活動，用來表示項目的開始和結束?；顒又g的優先關系能夠約束活動的開始，例如活動j需要在所有先前的活動Pj完成后才開始[4]。用Mj表示活動j的執行模式，當活動的執行模式確定后就不能更改了。假設共有K種可再生資源類型，用Rk表示資源類型k的可用量。在模式m中執行活動j需要花費時間為djm，需要的資源類型集合為Rjm和對資源k的需求表示為rjmk。

本研究的目的是確定一組非支配計劃，以減少項目時間和成本為目標，同時滿足優先級和資源約束。第一個目標是最小化項目的總工時Ft。在為每個活動選擇執行模式后，確定相應的活動持續時間、直接費用和資源需求。然后將活動模式信息輸入到多模型的第二階段。搜索引擎將遺傳算法與進度表生成方案集成在一起，以搜索最佳的序列，從而根據給定的約束為所有活動生成可行的進度表。

第二個目標是將總項目成本FC降至最低。項目成本分為直接成本和間接成本，其計算方式為FC=∑j∑mxjmcjm+fjci。直接成本(即∑j∑mxjmcjm)與項目活動的執行直接相關，并與項目資源的可用性密切相關。其中，cjm是活動j以模式m執行的直接成本，xjm是決策變量。間接成本(即fjci)與項目活動的執行無關。在這項研究中，假設每個時期的間接費用是固定的(即ci為常量)，而一個項目的總間接費用取決于項目工期fj。項目的總直接成本是活動執行成本的總和，直接費用總額取決于所選的執行模式。

2 基于遺傳算法的優化模型

2.1 算法概述

本優化模型采用一種基于種群的算法，通過進行直接搜索解決全局優化問題[5]。該算法簡要描述如下：

令S?R為問題的搜索空間，向量Xi,G為種群。初始種群是隨機生成的，并且覆蓋整個參數空間。在每一代中，算法應用兩個算子(突變和交叉重組)為每個目標向量Xi,G產生一個試驗向量Ui,G+1。然后，選擇階段確定試驗向量是否進入下一代。使用以下公式為每個目標向量Xi,G確定一個突變向量Vi,G+1：

Vi,G+1=Xr1,G+F(Xr2,G-Xr3,G

(1)

其中，r1、r2和r3是從種群中隨機選擇的個體，F是比例因數，取值范圍是0到1。

在突變階段之后，采用交叉算子來增加種群的多樣性。對于每一個突變向量Vi,G+1，其對應的試驗向量Ui,G+1中的元素按照以下規則生成：

(2)

其中，CR是自定義的交叉常數，其取值范圍是0到1。jrand是從種群中隨機選擇的個體索引。

為了確定是否將試驗向量Ui,G+1加入到下一代種群中，使用貪婪算法將該向量與其對應的目標向量Xi,G進行比較。選擇算子表示如下：

(3)

算法的進化循環將反復進行，直到滿足停止條件為止。

2.2 基于混沌技術的初始化

本研究同時優化了項目成本和項目工期。在優化之前，該模型需要項目信息輸入，包括活動關系、每天的可用性資源、活動持續時間、成本、資源類型以及每個活動的執行模式。另外，還需要對以下的參數進行設置：種群大小NP、決策變量的數量D、目標函數的數量K、突變常數F和交叉概率常數CR。

種群初始化是進化算法中重要的一個步驟，結合均勻隨機分布和混沌技術生成初始種群。

(4)

在使用混沌生成個體之后，選擇NP個最佳的解決方案，并將其輸入到模型的主循環中。可以將問題的候選解決方案表示為具有D個元素的向量，即xi=[Xi,1,…,Xi,D]。向量Xi,j表示活動j的一種執行模式，索引i表示種群中的第i個個體。執行模式Xi,j的取值范圍是[1,Mj]。使用一個函數將那些活動的執行模式選項從實際值轉換為可行域內的整數值，即

Xi,j=ceil(rand[0,1]×UB(j))

(5)

其中，rand[0,1]是0到1之間的隨機數，UB(j)是活動j的執行模式的數量。ceil是向上取整的函數。

采用快速的非支配排序技術將種群分類為非支配集合(F1,F2,…)。選擇屬于最佳非支配集合(集合F1)的解，并將其輸入到種群中。如果F1小于NP，則按照排序將其它非支配解(F2,F3,…)加入到種群。假設Fk是最后一個加入的非支配的集合。通常，集合F1,…,Fk中解的數量會大于NP。因此使用熵排序技術選擇最佳NP個種群成員。

2.3 突變和交叉操作

初始化后，算法對種群進行突變操作。突變向量Vi,G+1的生成公式如下所示：

Vi,G+1=Xr1,G+F(Xr2,G-Xr3,G)

(6)

為了提升算法的收斂速度，選擇適應度最高的向量作為突變操作的基向量。

針對算法的三個階段設計了三種選擇機制：

(1)g≤ms×Gmax：采用隨機選擇機制，在種群中隨機選擇Xr1、Xr2和Xr3。在進化過程的開始，所有用于突變的個體都是隨機選擇的，隨機選擇可以確保種群的多樣性。

(2)ms×Gmax

(3)g>2×ms×Gmax：在優化過程的最后階段，算法必須加速收斂。用于突變的所有向量Xr1、Xr2和Xr3均是適應度值較高的個體。

其中：ms是突變選擇系數，Gmax是最大迭代次數。

交叉操作交換目標向量和突變向量的元素，使種群多樣化。把交叉操作得到的向量稱為后代向量，如下所示：

(7)

2.4 資源受限子系統

后代向量首先定義每個活動的執行模式，然后確定相應的成本、持續時間和資源需求。將執行模式信息輸入到資源受限的子系統中，該子系統將基于給定的約束條件生成可行的時間表。在資源受限的子系統運行之前，隨機均勻分布生成器會創建包含M個個體的初始種群。資源受限問題的解決方案是一個具有D個元素的向量，即Xs=[Xs1,…,XsD]。其中D是當前問題中決策變量的數量，同時也是項目網絡中的活動數量。

將基于優先級的調度與串行轉換方案相結合，針對資源受限的項目調度問題，設計遺傳算法中個體的編碼表示方式。作為D維空間中的一個點，DE個體中的第D個元素可以表示項目中的D活動。向量Xs(t)中的D個參數{xs1(t),…,xsD(t)}表示D個活動的D維優先值。對向量中的元素按照其優先值排序，得到新的向量。

串行方法包含n個階段，每個階段中選擇一項活動進行調度。當一項活動的當前可用資源量足夠時，該活動將會在最早的優先時間被調度。所設計的串行方法如下所示：

步驟1：根據優先級約束將個體優先級轉移到活動計劃中。假設項目活動集合為j={1,2,…,n}。用集合C={(i,j)}表示集合J={1,2,…,n}中活動的優先級關系，其中(i,j)表示活動i必須在活動j之前執行。引入二元關系矩陣V=(vij,1≤i,j≤n)：當(imj)∈C時，vij=1；否則vij=0。同時引入優先級關系矩陣G=(gij,1≤i,j≤n)來描述所有優先級關系鏈：當(k,k1),(k1,k2),…,(kj-1,kj)都屬于集合C，那么有gkj=1。因此，可以根據集合C來構建矩陣G。

步驟2：根據活動時間表計算項目工期。在應用串行方法之前，必須考慮兩個重要點：首先，活動A在所有前繼活動完成后開始；其次，活動開始時間取決于資源的可用性。因此，當活動A的前繼活動完成后且有足夠的資源時，活動A立刻會被執行。

2.5 精英庫更新

項目總工期和每個執行模式的成本會被輸入到子系統以進行評估。多目標優化的一個重要步驟是選擇機制，采用基于帕累托支配的選擇機制。該選擇機制首先評估后代向量Ui,G，然后將該向量與目標向量Xi,G進行行比較：當Xi,G支配Ui,G，則將Ui,G丟棄；當Ui,G支配Xi,G且Xi,G=Ui,G，更新外部精英庫；對于其他情況，采用熵排序選擇個體。

在選擇操作過程中選擇的向量稱為選擇向量。如果所有精英庫個體都支配選擇向量，則不將選擇向量加入到精英庫中。如果選擇向量支配一個或多個精英庫成員，則刪除該精英庫成員，并將選擇向量加入到精英庫。

當算法滿足停止條件時，優化過程終止。一個停止條件是最大迭代次數Gmax，即算法迭代次數達到Gmax，算法就停止。另一個停止條件是最大評估次數，即適應度函數的計算次數。在優化過程終止后，就會輸出一組最佳的解決方案。

3 實驗評估

采用案例來評估本方法的有效性，并將本方法獲得的結果與通過多目標差分進化算法(MODE)和非支配排序遺傳算法(NSGA-II)的結果進行比較。實驗采用MATLAB R2020a仿真平臺，實驗在工作站上進行，該工作站的配置為：CPU采用Intel 酷睿i7-10700 5.3 GHz，內存的大小為16 G，硬盤容量為256 G SSD + 1 T 機械硬盤。實驗采用了一個倉庫建筑工程的案例數據來驗證本文算法。該案例一共有37個活動，各個活動之間的優先級關系如圖1所示。案例數據中，每項活動的屬性包括了活動序號、活動的具體描述、工期、前繼活動以及成本，部分活動的時間成本如表1所示。

圖1 活動優先級圖

表1 部分活動的信息

分別將本文算法、MODE算法和NSGA-II算法運行20次，并取平均值。分別從三種算法所獲得的帕累托前沿中選取較好的結果，并將結果呈現在表2中。

表2 三種算法結果對比

由表2可知，解決方案1的工程總成本是最高的，但其工期是最短的；而解決方案3的工期較長，成本卻是最低的。對比三種算法的結果可知，相同工期的情況下，本算法能夠獲得最低的成本；而當成本相近時，本算法的工期是最短的。由此可知，本算法能獲得最佳的綜合性能。

4 結論

本研究提出了一種基于遺傳算法的優化模型，以解決資源受限的建筑工程計劃管理問題，實現了工期和成本的均衡。該模型生成的帕累托最優解有助于決策者在項目時間和成本限制下做出最佳工程計劃。實驗結果表明，本模型可以有效地解決計劃管理問題，并可以找到多目標帕累托最優解。擬議的模型使決策者能夠根據時間和成本偏好作出及時、知情的決定。未來的工作集中在將本模型應用于更多的實際案例中，以進一步評估本模型的性能。