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

張 智 涌， 雙 學 珍

(四川水利職業技術學院，四川 成都 611830)

?

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

張 智 涌， 雙 學 珍

(四川水利職業技術學院，四川 成都 611830)

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

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

1 概 述

水利水電工程項目管理中最常用的是網絡計劃技術。在網絡計劃中，資源作為工程實施的基本要素和必不可少的條件，是影響工程進度計劃的主要因素。資源優化的失誤往往會造成工程進度和投資目標失控。“工期固定 資源均衡”是資源優化的目標之一，即在工期一定的條件下，合理調整網絡計劃中的某些工序，實現資源的均衡利用。

在采用傳統的優化方法解決大規模網絡和多資源約束問題時，隨著活動數目的增加，求解最優解的計算量將會急劇增加，而遺傳算法的引入，則能很好地解決這個問題。

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

2.1 問題描述

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

(1)假設網絡計劃中的每個工序活動是不可分割的，活動一旦開始就不能中斷；

(2) 假設每個工序只有一種執行模式；

(3)假設網絡中的每項工序的工期均為常數，其所需資源的需要量和供應量在其工期內也是不變的常數。

目標函數以工期內每天資源需求量的標準差σk為目標函數，標準差越小，說明資源均衡程度越好。

問題的數學描述如下：

(1)

s.t.

ti-ESi≤TFi

(2)

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

(3)

式中 RLI為資源均衡系數，表示資源均衡程度；σk為第k種資源每天資源需求量的標準差；wk為第k種資源的權重；ti為作業i的開始時間；ESi為作業i的最早開始時間；TFi為作業i的總時差；m為總資源數；n為總作業數。

(4)

工期內任何一種資源k在工期內資源消耗的標準差σk為：

(5)

式中 di為第i項作業的持續時間；ri為第i項作業每天的資源需求量；riq為第i項作業第q天的資源需求量；T為項目總工期。

2.2 遺傳算法設計

2.2.1 染色體結構

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

表1 染色體結構表

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

2.2.2 初始化

在進行初始化之前，我們應當已經知道每個工作的最早開始時間，且個體的初始化是從右向左進行的，即從項目的結束工作向項目的開始工作進行。已知ESi為工作i的最早開始時間，Si為工作i的緊后工作集合，di為工作i的持續時間，則工作i的基因值(即開始時間vi)為：

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

(6)

由于整個過程是從右向左進行的，工作i緊后工作的開始時間vk已經賦值，因此，式(6)不會產生非法計劃安排。可以看出，這種方法完全避免了利用總時差對工作開始時間進行調整所帶來的對該工作的后續工作總時差重新計算的問題。

2.2.3 編碼設計

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

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

(7)

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

2.2.4 遺傳算子

由于工作的開始時間依賴于其后續工作的開始時間，而單純的交叉操作后會產生非法個體，故在交叉之后需要對個體進行合法性檢驗，對不合理的個體進行調整。檢驗和調整的過程仍然按照從右向左的方向進行，檢驗公式如下：

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

(8)

當基因值滿足上述條件時該基因值合理，否則需要進行調整。調整方式依據公式(8)重新向該基因賦值。

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

算子采用輪盤式的方法進行選擇，并且采取保留父代最優個體的策略。

2.2.5 約束條件

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

(1)基本約束。直接來自環境向系統提供的實例，標志變量定義域范圍的約束。

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

(9)

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

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

由于在編碼設計中，工序的實際開工時間在工序的總時差范圍內取任意數，從而有可能使工序用完自己的自由時差而影響后續工序的最早開工時間，使網絡的邏輯結構產生矛盾：TF(k,i)

(i,j) ∈N

(10)

2.2.6 修復算子

圖1 修復算子流程圖

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

2.3 遺傳算法流程

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

(a)算法流程圖；(b)產生下一代子函數；(c)適應度評價值函數圖2 工期固定資源均衡遺傳算法流程圖

3 工程實例分析

某水電站項目總工期定為由“資源有限 工期最短”優化模型中得出的87個月。結合理論和實際優化分析，確定此遺傳算法優化模型的交叉概率、變異概率、種群規模和最大進化代數分別為0.7、0.1、100和2 000，各資源權重均取1/4。利用所建遺傳算法模型得出的優化結果見圖3。

圖3 工期固定資源均衡遺傳算法優化結果示意圖

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

采用優化程序計算出的月土石方明挖量的均衡結果見圖4。

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

4 結 語

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

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

[1] 玄光男，程潤偉.遺傳算法與工程設計[M].北京：科學出版社，2000.

[2] 田 軍，寇紀淞，李敏強.利用遺傳算法優化施工網絡計劃[J].系統工程理論與實踐，1999，14(5)：78-82.

[3] 仲景冰.“工期固定，資源均衡”優化的動態規劃法[J].武漢城市建設學院學報，2000，17(2)：6-10.

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

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

(責任編輯：李燕輝)

2016-06-06

TV7；TV52；TV2；TV

B

1001-2184(2016)06-0071-03

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

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