張 智 涌， 雙 學(xué) 珍

(四川水利職業(yè)技術(shù)學(xué)院，四川 成都 611830)

?

基于遺傳算法的水電工程施工“工期固定資源均衡”優(yōu)化研究

張 智 涌， 雙 學(xué) 珍

(四川水利職業(yè)技術(shù)學(xué)院，四川 成都 611830)

水電工程施工具有影響因素多、約束條件多、工程量大、項(xiàng)目工藝復(fù)雜、周期長等特點(diǎn)，將先進(jìn)的科學(xué)技術(shù)和項(xiàng)目管理理論引進(jìn)水利水電工程建設(shè)和管理中是一個(gè)值得研究的領(lǐng)域，也是國際化的發(fā)展趨勢。資源優(yōu)化是項(xiàng)目管理的一部分，“工期固定 資源均衡”是資源優(yōu)化的目標(biāo)之一。與傳統(tǒng)的優(yōu)化方法相比，遺傳算法在解決資源優(yōu)化配置問題上有很多優(yōu)點(diǎn)。首先，它能夠大大減少計(jì)算的復(fù)雜度和計(jì)算量，尤其適用于大規(guī)模網(wǎng)絡(luò)的計(jì)算；其次，能夠與其他算法結(jié)合在一起使用；而且該算法比較適合于通過計(jì)算機(jī)編程實(shí)現(xiàn)。因此，采用遺傳算法解決水電工程施工資源優(yōu)化問題也就應(yīng)運(yùn)而生。建立了“工期固定 資源均衡”遺傳算法模型，并以某水電站項(xiàng)目為例，進(jìn)行了工期固定、資源均衡優(yōu)化計(jì)算，論證了所建模型的可行性。

遺傳算法；工期固定；資源均衡；水電工程施工

1 概 述

水利水電工程項(xiàng)目管理中最常用的是網(wǎng)絡(luò)計(jì)劃技術(shù)。在網(wǎng)絡(luò)計(jì)劃中，資源作為工程實(shí)施的基本要素和必不可少的條件，是影響工程進(jìn)度計(jì)劃的主要因素。資源優(yōu)化的失誤往往會(huì)造成工程進(jìn)度和投資目標(biāo)失控?！肮て诠潭?資源均衡”是資源優(yōu)化的目標(biāo)之一，即在工期一定的條件下，合理調(diào)整網(wǎng)絡(luò)計(jì)劃中的某些工序，實(shí)現(xiàn)資源的均衡利用。

在采用傳統(tǒng)的優(yōu)化方法解決大規(guī)模網(wǎng)絡(luò)和多資源約束問題時(shí)，隨著活動(dòng)數(shù)目的增加，求解最優(yōu)解的計(jì)算量將會(huì)急劇增加，而遺傳算法的引入，則能很好地解決這個(gè)問題。

2 “工期固定 資源均衡”遺傳算法模型的建立

2.1 問題描述

在此，筆者考慮的是一般的“工期固定 資源均衡”問題：

(1)假設(shè)網(wǎng)絡(luò)計(jì)劃中的每個(gè)工序活動(dòng)是不可分割的，活動(dòng)一旦開始就不能中斷；

(2) 假設(shè)每個(gè)工序只有一種執(zhí)行模式；

(3)假設(shè)網(wǎng)絡(luò)中的每項(xiàng)工序的工期均為常數(shù)，其所需資源的需要量和供應(yīng)量在其工期內(nèi)也是不變的常數(shù)。

目標(biāo)函數(shù)以工期內(nèi)每天資源需求量的標(biāo)準(zhǔn)差σk為目標(biāo)函數(shù)，標(biāo)準(zhǔn)差越小，說明資源均衡程度越好。

問題的數(shù)學(xué)描述如下：

(1)

s.t.

ti-ESi≤TFi

(2)

ti≥0,i=1,2,…,n

(3)

式中 RLI為資源均衡系數(shù)，表示資源均衡程度；σk為第k種資源每天資源需求量的標(biāo)準(zhǔn)差；wk為第k種資源的權(quán)重；ti為作業(yè)i的開始時(shí)間；ESi為作業(yè)i的最早開始時(shí)間；TFi為作業(yè)i的總時(shí)差；m為總資源數(shù)；n為總作業(yè)數(shù)。

(4)

工期內(nèi)任何一種資源k在工期內(nèi)資源消耗的標(biāo)準(zhǔn)差σk為：

(5)

式中 di為第i項(xiàng)作業(yè)的持續(xù)時(shí)間；ri為第i項(xiàng)作業(yè)每天的資源需求量；riq為第i項(xiàng)作業(yè)第q天的資源需求量；T為項(xiàng)目總工期。

2.2 遺傳算法設(shè)計(jì)

2.2.1 染色體結(jié)構(gòu)

基于遺傳算法的資源優(yōu)化主要是選擇適應(yīng)度最大的染色體作為父輩，交叉后產(chǎn)生子代。由于資源均衡問題的前提是工期固定，即網(wǎng)絡(luò)計(jì)劃的關(guān)鍵線路不變，關(guān)鍵線路上的工序開工時(shí)間均固定不變，所以，多種資源均衡優(yōu)化的工作是將非關(guān)鍵線路上的某些工序的開工時(shí)間向后移動(dòng)，同時(shí)使得多種資源的分布達(dá)到均衡分布。因此，將時(shí)標(biāo)網(wǎng)絡(luò)計(jì)劃中的各項(xiàng)工作的開工時(shí)間TS(I)作為染色體的基因，將非關(guān)鍵路線上的各個(gè)工序的實(shí)際開工時(shí)間排列的序列作為染色體串(表1)。

表1 染色體結(jié)構(gòu)表

注：工序(0，1)(1，2)…(i,j)…(n-1,n)為非關(guān)鍵工序。

2.2.2 初始化

在進(jìn)行初始化之前，我們應(yīng)當(dāng)已經(jīng)知道每個(gè)工作的最早開始時(shí)間，且個(gè)體的初始化是從右向左進(jìn)行的，即從項(xiàng)目的結(jié)束工作向項(xiàng)目的開始工作進(jìn)行。已知ESi為工作i的最早開始時(shí)間，Si為工作i的緊后工作集合，di為工作i的持續(xù)時(shí)間，則工作i的基因值(即開始時(shí)間vi)為：

vi=ESi+randon(min){vk|k∈Si}-ESi-di)

(6)

由于整個(gè)過程是從右向左進(jìn)行的，工作i緊后工作的開始時(shí)間vk已經(jīng)賦值，因此，式(6)不會(huì)產(chǎn)生非法計(jì)劃安排?？梢钥闯?，這種方法完全避免了利用總時(shí)差對工作開始時(shí)間進(jìn)行調(diào)整所帶來的對該工作的后續(xù)工作總時(shí)差重新計(jì)算的問題。

2.2.3 編碼設(shè)計(jì)

由于“工期固定資源均衡”的前提條件是關(guān)鍵線路的工序不變，所以，非關(guān)鍵工序的開工時(shí)間有較固定的取值范圍，其編碼方法如下所示：

TS(i,j) ∈RAN[ES(i,j),LS(i,j)]

(7)

式中TS(i,j)為工序(i,j)的實(shí)際開工時(shí)間(即染色體基因)；ES(i,j)為工序(i,j)的最早開工時(shí)間；LS(i,j)為工序(i,j)的最遲開工時(shí)間；RAN(a,b)為在a，b之間以隨機(jī)數(shù)方式取任意數(shù)。

2.2.4 遺傳算子

由于工作的開始時(shí)間依賴于其后續(xù)工作的開始時(shí)間，而單純的交叉操作后會(huì)產(chǎn)生非法個(gè)體，故在交叉之后需要對個(gè)體進(jìn)行合法性檢驗(yàn)，對不合理的個(gè)體進(jìn)行調(diào)整。檢驗(yàn)和調(diào)整的過程仍然按照從右向左的方向進(jìn)行，檢驗(yàn)公式如下：

vi≤min{vk|k∈Si}-di

(8)

當(dāng)基因值滿足上述條件時(shí)該基因值合理，否則需要進(jìn)行調(diào)整。調(diào)整方式依據(jù)公式(8)重新向該基因賦值。

變異的過程相對簡單，對于一個(gè)給定的個(gè)體，隨機(jī)選擇一個(gè)基因位，然后對該基因值按照初始化的公式(8)重新賦值。

算子采用輪盤式的方法進(jìn)行選擇，并且采取保留父代最優(yōu)個(gè)體的策略。

2.2.5 約束條件

為了使該算法能夠順利進(jìn)行，筆者充分利用問題本身的啟發(fā)式信息，將約束條件分為兩種不同類型的約束：

(1)基本約束。直接來自環(huán)境向系統(tǒng)提供的實(shí)例，標(biāo)志變量定義域范圍的約束。

ES(i,j)≤TS(i,j)≤LS(i,j)

(9)

這是工序開工時(shí)間的選擇范圍，此項(xiàng)約束在種群的初始化中予以考慮。

(2)屬性約束。定義在基本約束集上，反映變量間制約關(guān)系的約束。

由于在編碼設(shè)計(jì)中，工序的實(shí)際開工時(shí)間在工序的總時(shí)差范圍內(nèi)取任意數(shù)，從而有可能使工序用完自己的自由時(shí)差而影響后續(xù)工序的最早開工時(shí)間，使網(wǎng)絡(luò)的邏輯結(jié)構(gòu)產(chǎn)生矛盾：TF(k,i)

(i,j) ∈N

(10)

2.2.6 修復(fù)算子

圖1 修復(fù)算子流程圖

從約束條件出發(fā)，設(shè)計(jì)編碼范圍并產(chǎn)生隨機(jī)個(gè)體的種群進(jìn)行遺傳進(jìn)化，然后對產(chǎn)生的子代個(gè)體進(jìn)行篩選，對不滿足屬性約束的個(gè)體采用修復(fù)算子加以處理，從而能夠保證種群中的個(gè)體都能滿足給定的約束條件。修復(fù)的目的是對變量進(jìn)行一致性調(diào)整，使后面的變量服從前面的變量，以解決變量間的沖突，修復(fù)算子流程見圖1。

2.3 遺傳算法流程

“工期固定 資源均衡”遺傳算法流程見圖2。

(a)算法流程圖；(b)產(chǎn)生下一代子函數(shù)；(c)適應(yīng)度評價(jià)值函數(shù)圖2 工期固定資源均衡遺傳算法流程圖

3 工程實(shí)例分析

某水電站項(xiàng)目總工期定為由“資源有限 工期最短”優(yōu)化模型中得出的87個(gè)月。結(jié)合理論和實(shí)際優(yōu)化分析，確定此遺傳算法優(yōu)化模型的交叉概率、變異概率、種群規(guī)模和最大進(jìn)化代數(shù)分別為0.7、0.1、100和2 000，各資源權(quán)重均取1/4。利用所建遺傳算法模型得出的優(yōu)化結(jié)果見圖3。

圖3 工期固定資源均衡遺傳算法優(yōu)化結(jié)果示意圖

從圖3中可以看出：第一代個(gè)體適應(yīng)度值最大，其值為52.356 2,當(dāng)進(jìn)化到1 605代時(shí)，適應(yīng)度值達(dá)到最小，其值為25.775 4，并且到2000代時(shí)適應(yīng)值始終保持為25.775 4。我們還可以看出：遺傳算法在優(yōu)化過程中，剛開始時(shí)函數(shù)值下降的比較快，代數(shù)越高、優(yōu)化的速度越慢，最終達(dá)到全局收斂。繼續(xù)增加優(yōu)化代數(shù)，其結(jié)果仍不會(huì)改變(筆者曾試著計(jì)算過3000代和5000代，其優(yōu)化結(jié)果不變)，從而說明此時(shí)已達(dá)到優(yōu)化的全局最優(yōu)解。

采用優(yōu)化程序計(jì)算出的月土石方明挖量的均衡結(jié)果見圖4。

圖4 月土石方明挖量遺傳算法資源均衡結(jié)果圖

4 結(jié) 語

(1)筆者針對傳統(tǒng)算法在多種資源優(yōu)化中應(yīng)用的不足，建立了“工期固定 資源均衡”的遺傳算法優(yōu)化模型，解決了多種資源在網(wǎng)絡(luò)計(jì)劃優(yōu)化時(shí)的競爭問題，取得了較好效果，促進(jìn)了GA理論與應(yīng)用研究。

(2)遺傳算法在“工期固定 資源均衡”優(yōu)化中的成功運(yùn)用，充分證明了其在水利水電工程資源優(yōu)化中的應(yīng)用具有廣闊的前景。

[1] 玄光男，程潤偉.遺傳算法與工程設(shè)計(jì)[M].北京：科學(xué)出版社，2000.

[2] 田 軍，寇紀(jì)淞，李敏強(qiáng).利用遺傳算法優(yōu)化施工網(wǎng)絡(luò)計(jì)劃[J].系統(tǒng)工程理論與實(shí)踐，1999，14(5)：78-82.

[3] 仲景冰.“工期固定，資源均衡”優(yōu)化的動(dòng)態(tài)規(guī)劃法[J].武漢城市建設(shè)學(xué)院學(xué)報(bào)，2000，17(2)：6-10.

[4]Chung-WeiFeng,LiangLiu,andScotA.Burns.UsingGeneticAlgorithmstoSolveConstructionTime-CostTrade-OffProblems[J].JournalofComputinginCivilEngineering,1997,11(3): 184-189.

[5] 張連營，駱 剛，鹿麗寧. 遺傳算法在工程項(xiàng)目資源優(yōu)化中的應(yīng)用[J].天津大學(xué)學(xué)報(bào)，2001，34(2)：188-192.

(責(zé)任編輯：李燕輝)

2016-06-06

TV7；TV52；TV2；TV

B

1001-2184(2016)06-0071-03

張智涌(1964-)，男，重慶彭水人，副教授、高級工程師，從事水利水電工程設(shè)計(jì)與施工管理教學(xué)及科研工作；

雙學(xué)珍(1982-),女，山西交城人，副教授，工程師，碩士，從事水利水電工程設(shè)計(jì)與施工管理教學(xué)及科研工作.