基于遺傳算法的建筑工程計劃管理優(yōu)化研究

張國富

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

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

1 問題建模

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

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

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

2 基于遺傳算法的優(yōu)化模型

2.1 算法概述

本優(yōu)化模型采用一種基于種群的算法，通過進行直接搜索解決全局優(yōu)化問題[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中的元素按照以下規(guī)則生成：

(2)

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

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

(3)

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

2.2 基于混沌技術的初始化

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

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

(4)

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

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

(5)

其中，rand[0,1]是0到1之間的隨機數，UB(j)是活動j的執(zhí)行模式的數量。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：在優(yōu)化過程的最后階段，算法必須加速收斂。用于突變的所有向量Xr1、Xr2和Xr3均是適應度值較高的個體。

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

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

(7)

2.4 資源受限子系統(tǒng)

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

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

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

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

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

2.5 精英庫更新

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

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

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

3 實驗評估

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

圖1 活動優(yōu)先級圖

表1 部分活動的信息

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

表2 三種算法結果對比

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

4 結論

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