基于SAGA的工程項目資源均衡優化方法

李英攀，李亞峰，孫志凌，管 慧

(1. 武漢理工大學 土木工程與建筑學院， 湖北 武漢 430070；2. 中建三局第二建設工程有限公司， 湖北 武漢 430070)

工程項目資源優化可以使項目更合理、順利地進行，合理的勞動力資源配置方案能夠在保證項目工期的前提下，避免人員扎堆而增加施工現場人員管理成本，或者在有限的勞動力資源情況下，盡可能縮短工期，減少人工成本支出或獲得提前竣工獎勵，從而提高企業的經濟效益，具有很強的實踐意義[1]。由此可見，工程項目資源優化問題主要分為兩類：“工期固定-資源均衡”問題和“資源有限-工期最短”問題[2]。本文擬先針對“工期固定-資源均衡”問題進行深入研究，該問題是典型的NP(Non-deterministic Polynomial)-hard問題，其求解難度和計算量隨著工作或約束數量的增加而呈指數型增長，導致傳統的甘特圖分析、關鍵路徑分析等人工計算方法的求解效率低下，并且其求解結果的最優性難以確定[3]。因此，粒子群優化算法[4]、遺傳算法[5,6]、模擬退火算法[7]等機器學習算法在該問題上的應用被大量提出，用來避免傳統方法繁瑣的推斷計算過程。但是，對比相關研究和大量重復實驗發現，此類算法在應用中存在陷入局部最優的概率，即有概率只能得到次優的項目資源配置方案，不能達到資源均衡最優化的目的。

因此，本文擬開發一種應用于項目資源均衡優化問題的模擬退火遺傳算法(Simulated Annealing Genetic Algorithm，SAGA)，以降低甚至消除陷入局部最優的概率，提高項目資源管理能力和資源使用效率。

1 SAGA理論基礎

模擬退火算法(Simulated Annealing，SA)是一種基于蒙特卡羅迭代求解策略的一種隨機尋優算法，模擬退火算法生成的隨機解從較高初始溫度出發，伴隨溫度的不斷下降在解空間中尋找全局最優解[8]。與一般的尋優算法不同，模擬退火算法是以基于Metropolis準則的概率在鄰域中尋找目標值較小的狀態。同時，工程項目資源配置方案在一定范圍內的小幅度變化，不一定會對目標值產生影響。因此，針對工程項目資源優化問題，模擬退火算法的全局尋優能力欠佳，比較容易陷入局部最優。

遺傳算法(Genetic Algorithm，GA)將自然生物進化過程中的“優勝劣汰”作為尋優的基本思想，在全局范圍內隨機創建初始種群，根據種群中個體對環境的適應度大小對其進行選擇，再通過交叉、變異等行為得到下一代，循環往復得到全局最優解[9]。但是，當種群內某個體適應度遠高于其他個體時，該個體將難以得到進一步優化，從而可能導致算法過早收斂，陷入局部最優解。

模擬退火算法和遺傳算法在單獨使用時都可能陷入局部最優，但是，如果以模擬退火算法的重復尋優結果建立遺傳算法的初始種群，避免隨機創建初始種群時某個體適應度遠高于其他個體的情況，就可以解決遺傳算法陷入局部最優的問題[10]。在工程項目“工期固定-資源均衡”問題中，模擬退火算法的尋優結果是解空間內的最優解或者近似最優解，并且兩者在目標值上的差異不大，不會導致遺傳算法過早收斂，再通過遺傳算法的進一步選擇、交叉遺傳可以得到其中的最優解，并且小概率的變異行為增加了解的多樣性，增強了算法的全局意義。同時，模擬退火算法和遺傳算法在優化機制、優化結構、優化操作等方面也具有較強的互補性或可融合性[4]，如表1所示。

綜上所述，模擬退火算法和遺傳算法的有機結合可以降低解決項目資源均衡優化問題時陷入最優解的概率，達到提高資源優化效率的目的。

表1 模擬退火算法和遺傳算法的對比

2 工程項目資源優化模型構建

2.1 理論數學模型

工期固定的工程項目資源均衡優化問題的理論數學模型為：

(1)

s.t. ESn≤Tn≤LSn，n=1,2,…,N

(2)

2.2 SAGA算法求解

(1)目標函數

由理論數學模型可知，目標函數由關鍵變量Rt計算得到，而Rt又受自變量Tn影響。因此，利用統一的數學語言表示Rt和Tn之間的關系是算法求解的前提。在“工期固定-資源均衡”問題中，關鍵線路是固定不變的，則自變量Tn實際是非關鍵工作的實際開始時間，N實際是非關鍵工作的總項數。

因此，建立非關鍵工作資源表示矩陣W(W=(wnt)N×T)：

(3)

式中：Rn為第n項工作的資源占用量；dn為第n項工作的持續時間。從而通過W列項求和可得到的T維行向量表示非關鍵工作的日資源占用量。而所有關鍵工作的日資源占用量是固定的，兩者相加即為工程項目所有工作的日資源占用量Rt。至此，結合式(1)即構成算法求解的目標函數。

(2)SAGA算法求解

利用SAGA對上述模型進行求解，旨在通過SA對建立的隨機工程項目資源配置方案進行優化，得到最優或次優資源配置方案。從而建立遺傳算法的初始種群，再通過選擇、交叉以及變異等遺傳操作得到最優資源配置方案。SAGA算法優化工程項目資源均衡的步驟如下：

步驟1：導入數據與模型初始化。導入工程項目的相關數據，包括工期以及關鍵工作與非關鍵工作的最早開始時間ESn、最晚開始時間LSn、工作持續時間dn和資源占用量Rn。設置模擬退火算法相關參數，包括初始溫度Tstart、終止溫度Tend以及降溫速率q等。設置遺傳算法相關參數，包括種群大小popsize，迭代次數time，交叉概率Pc和變異概率Pv等。

步驟2：隨機產生一個資源配置方案，記為S1。根據前文分析，該模型僅需隨機產生一組符合最早、最晚開始時間要求的非關鍵工作開始時間即可：

S1n=round((LSn-ESn)rand+ESn)

(4)

式中：round為四舍五入函數；rand為在[0，1]區間內取隨機數的隨機函數。

步驟3：在S1基礎上產生新的方案，記為S2。在S1中隨機挑選一項工作a，并對該工作的開始時間進行隨機提前或延后1 d：

S2a=S1a±1

(5)

同時，利用判斷語句保證S2中非關鍵工作的開始時間始終符合其最早、最晚開始時間要求：若符合要求則進行步驟4；若不符合要求則重復步驟3，直至符合要求再進行步驟4。

步驟4：判斷是否接受新方案。分別計算S1，S2的勞動力資源不平衡系數K1，K2，并以基于Metropolis準則的概率P接受S2。概率P的計算式如下：

(6)

步驟5：迭代優化。接受S2后，將S2賦予S1，重復步驟2～4。并進行降溫，當溫度低于終止溫度時迭代結束，輸出結果。

步驟6：建立遺傳算法初始種群。重復步驟2～5，得到多組SA優化結果，作為遺傳算法的初始種群，并進入遺傳算法優化部分。

步驟7：編碼。對SA結果組成的初始種群進行編碼，實數編碼具有染色體串短以及直接高效等優點，并且非關鍵工作開始時間只能是整數。因此，模型采用實數編碼方式，每一個基因代表對應非關鍵工作的開始時間。

步驟8：選擇-交叉-變異。模型采用錦標賽選擇策略，即個體適應度越高越容易被選擇作為父本產生下一代。交叉策略采用離散交叉，因為使用實數編碼時，離散交叉比算術交叉收斂性強。此外，在沒有特定需求的情況下，采用均勻變異概率是最可靠的[5]，變異策略與步驟3類似。

步驟9：迭代優化。根據迭代次數要求重復步驟8，對優化結果進行解碼并輸出最優解。

3 算例分析

為便于對比實驗結果，驗證SAGA算法的先進性，本文采用文獻[1]中的工程項目資源案例進行優化求解。已知某工程項目的雙代號時標網絡計劃如圖1所示，橫線上方為工作號，橫線下方為工作持續時間，相關參數如表2所示。

圖1 算例雙代號時標網絡計劃

由圖1、表2可知，項目工期為20 d，并且工作A，E，H為關鍵工作，工作B，C，D，F，G為非關鍵工作，但工作D自由時差為0，沒有可用的機動時間，因此，本例中僅需調整工作B，C，F，G的開始時間。在初始方案中，所有工作均按最早開始時間進行施工，此時日最高資源占用量Rmax=13人，資源不平衡系數K=1.512>1.5，該資源配置方案不可接受，需進一步優化。

表2 算例相關參數

設置模擬退火遺傳算法相關參數，初始溫度Tstart=108，終止溫度Tend=10-30，降溫速率q=0.9，種群大小popsize=30，迭代次數time=50，交叉概率Pc=0.5，變異概率Pv=0.005。經過SAGA求解計算，得到非關鍵工作B，C，F，G的開始時間分別為1，7，18，11 h，資源不平衡系數最小，為1.163，滿足小于1.5的要求，該資源配置方案可以接受。SAGA算法迭代優化過程如圖2所示。

圖2 迭代優化過程

模擬退火遺傳算法相比于其他尋優算法的先進性不在于能夠得到最優解，而是更小的陷入局部最優的概率。因此，分別采用GA，SA，SAGA算法對上述案例進行重復優化求解100次，并在優化程度、最優解穩定性和平均運行時間等方面進行對比，對比結果如表3所示。

表3 各算法重復優化結果對比

由于GA對工程項目的資源優化效果受種群大小影響，表中列出當遺傳算法設置不同種群大小時的優化結果。隨著種群大小的增加，算法運行時間增加，算法陷入局部最優概率減小。同時，最優解穩定性和種群大小之間是凸性函數，即雖然增加種群大小可以增加最優解的穩定性，但是種群越大，優化效率越低。僅使用SA對工程項目進行資源優化，其最優解穩定性和運行時間方面的表現均欠佳，不能滿足實際優化需求。而SAGA在資源優化過程中，能夠用較小的種群，在較短的運行時間內得到100%穩定的優化結果，工程項目資源優化效率和穩定性極佳，具有極高的指導實踐能力。

4 結 語

(1)基于對模擬退火算法和遺傳算法的搜索能力、優化機制、優化結構和優化操作互補性和可融合性的分析，將兩者有機結合，利用模擬退火算法優化結果作為遺傳算法初始種群，降低了遺傳算法由于某個體適應度遠高于其他個體導致的過早收斂概率，增強了算法的全局搜索能力。

(2)對模擬退火算法產生新解方式和遺傳算法的變異策略進行重新設計，建立了適用于工程項目資源均衡優化問題的模擬退火優化算法。通過算例驗證，相較于GA和SA，SAGA在最優解穩定性和運行時間方面的綜合表現更優秀，大大提高了資源優化效率。

(3)SAGA算法能夠有效解決項目資源優化中的“工期固定-資源均衡”問題，在下一步的研究中，擬選取合適的算法解決“資源有限-工期最短”問題，同時考慮工期獎懲制度，尋找資源配置和工期之間的最佳平衡點，完善項目資源優化應用體系。