基于SAGA的工程項(xiàng)目資源均衡優(yōu)化方法

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

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

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

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

1 SAGA理論基礎(chǔ)

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

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

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

綜上所述，模擬退火算法和遺傳算法的有機(jī)結(jié)合可以降低解決項(xiàng)目資源均衡優(yōu)化問(wèn)題時(shí)陷入最優(yōu)解的概率，達(dá)到提高資源優(yōu)化效率的目的。

表1 模擬退火算法和遺傳算法的對(duì)比

2 工程項(xiàng)目資源優(yōu)化模型構(gòu)建

2.1 理論數(shù)學(xué)模型

工期固定的工程項(xiàng)目資源均衡優(yōu)化問(wèn)題的理論數(shù)學(xué)模型為：

(1)

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

(2)

2.2 SAGA算法求解

(1)目標(biāo)函數(shù)

由理論數(shù)學(xué)模型可知，目標(biāo)函數(shù)由關(guān)鍵變量Rt計(jì)算得到，而Rt又受自變量Tn影響。因此，利用統(tǒng)一的數(shù)學(xué)語(yǔ)言表示Rt和Tn之間的關(guān)系是算法求解的前提。在“工期固定-資源均衡”問(wèn)題中，關(guān)鍵線路是固定不變的，則自變量Tn實(shí)際是非關(guān)鍵工作的實(shí)際開(kāi)始時(shí)間，N實(shí)際是非關(guān)鍵工作的總項(xiàng)數(shù)。

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

(3)

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

(2)SAGA算法求解

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

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

步驟2：隨機(jī)產(chǎn)生一個(gè)資源配置方案，記為S1。根據(jù)前文分析，該模型僅需隨機(jī)產(chǎn)生一組符合最早、最晚開(kāi)始時(shí)間要求的非關(guān)鍵工作開(kāi)始時(shí)間即可：

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

(4)

式中：round為四舍五入函數(shù)；rand為在[0，1]區(qū)間內(nèi)取隨機(jī)數(shù)的隨機(jī)函數(shù)。

步驟3：在S1基礎(chǔ)上產(chǎn)生新的方案，記為S2。在S1中隨機(jī)挑選一項(xiàng)工作a，并對(duì)該工作的開(kāi)始時(shí)間進(jìn)行隨機(jī)提前或延后1 d：

S2a=S1a±1

(5)

同時(shí)，利用判斷語(yǔ)句保證S2中非關(guān)鍵工作的開(kāi)始時(shí)間始終符合其最早、最晚開(kāi)始時(shí)間要求：若符合要求則進(jìn)行步驟4；若不符合要求則重復(fù)步驟3，直至符合要求再進(jìn)行步驟4。

步驟4：判斷是否接受新方案。分別計(jì)算S1，S2的勞動(dòng)力資源不平衡系數(shù)K1，K2，并以基于Metropolis準(zhǔn)則的概率P接受S2。概率P的計(jì)算式如下：

(6)

步驟5：迭代優(yōu)化。接受S2后，將S2賦予S1，重復(fù)步驟2～4。并進(jìn)行降溫，當(dāng)溫度低于終止溫度時(shí)迭代結(jié)束，輸出結(jié)果。

步驟6：建立遺傳算法初始種群。重復(fù)步驟2～5，得到多組SA優(yōu)化結(jié)果，作為遺傳算法的初始種群，并進(jìn)入遺傳算法優(yōu)化部分。

步驟7：編碼。對(duì)SA結(jié)果組成的初始種群進(jìn)行編碼，實(shí)數(shù)編碼具有染色體串短以及直接高效等優(yōu)點(diǎn)，并且非關(guān)鍵工作開(kāi)始時(shí)間只能是整數(shù)。因此，模型采用實(shí)數(shù)編碼方式，每一個(gè)基因代表對(duì)應(yīng)非關(guān)鍵工作的開(kāi)始時(shí)間。

步驟8：選擇-交叉-變異。模型采用錦標(biāo)賽選擇策略，即個(gè)體適應(yīng)度越高越容易被選擇作為父本產(chǎn)生下一代。交叉策略采用離散交叉，因?yàn)槭褂脤?shí)數(shù)編碼時(shí)，離散交叉比算術(shù)交叉收斂性強(qiáng)。此外，在沒(méi)有特定需求的情況下，采用均勻變異概率是最可靠的[5]，變異策略與步驟3類(lèi)似。

步驟9：迭代優(yōu)化。根據(jù)迭代次數(shù)要求重復(fù)步驟8，對(duì)優(yōu)化結(jié)果進(jìn)行解碼并輸出最優(yōu)解。

3 算例分析

為便于對(duì)比實(shí)驗(yàn)結(jié)果，驗(yàn)證SAGA算法的先進(jìn)性，本文采用文獻(xiàn)[1]中的工程項(xiàng)目資源案例進(jìn)行優(yōu)化求解。已知某工程項(xiàng)目的雙代號(hào)時(shí)標(biāo)網(wǎng)絡(luò)計(jì)劃如圖1所示，橫線上方為工作號(hào)，橫線下方為工作持續(xù)時(shí)間，相關(guān)參數(shù)如表2所示。

圖1 算例雙代號(hào)時(shí)標(biāo)網(wǎng)絡(luò)計(jì)劃

由圖1、表2可知，項(xiàng)目工期為20 d，并且工作A，E，H為關(guān)鍵工作，工作B，C，D，F(xiàn)，G為非關(guān)鍵工作，但工作D自由時(shí)差為0，沒(méi)有可用的機(jī)動(dòng)時(shí)間，因此，本例中僅需調(diào)整工作B，C，F(xiàn)，G的開(kāi)始時(shí)間。在初始方案中，所有工作均按最早開(kāi)始時(shí)間進(jìn)行施工，此時(shí)日最高資源占用量Rmax=13人，資源不平衡系數(shù)K=1.512>1.5，該資源配置方案不可接受，需進(jìn)一步優(yōu)化。

表2 算例相關(guān)參數(shù)

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

圖2 迭代優(yōu)化過(guò)程

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

表3 各算法重復(fù)優(yōu)化結(jié)果對(duì)比

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

4 結(jié) 語(yǔ)

(1)基于對(duì)模擬退火算法和遺傳算法的搜索能力、優(yōu)化機(jī)制、優(yōu)化結(jié)構(gòu)和優(yōu)化操作互補(bǔ)性和可融合性的分析，將兩者有機(jī)結(jié)合，利用模擬退火算法優(yōu)化結(jié)果作為遺傳算法初始種群，降低了遺傳算法由于某個(gè)體適應(yīng)度遠(yuǎn)高于其他個(gè)體導(dǎo)致的過(guò)早收斂概率，增強(qiáng)了算法的全局搜索能力。

(2)對(duì)模擬退火算法產(chǎn)生新解方式和遺傳算法的變異策略進(jìn)行重新設(shè)計(jì)，建立了適用于工程項(xiàng)目資源均衡優(yōu)化問(wèn)題的模擬退火優(yōu)化算法。通過(guò)算例驗(yàn)證，相較于GA和SA，SAGA在最優(yōu)解穩(wěn)定性和運(yùn)行時(shí)間方面的綜合表現(xiàn)更優(yōu)秀，大大提高了資源優(yōu)化效率。

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