蟻群算法在輸電工程工期成本優化中的應用

屈成忠，馬瑞楓，劉衛星，馬曉東

(1.東北電力大學建筑工程學院，吉林 吉林 132012;2.元寶山發電有限責任公司，內蒙古 赤峰 027000)

自從M.Dorigo在1991年首次提出蟻群算法(ant colony algorithm)之后，因其能將問題求解的快速性、全局優化特征以及有限時間內答案的合理性結合起來的特點，為世界各地研究工作者廣泛關注，該算法現己被大量應用于數據分析、機器人協作問題求解、電力、通信、水利、采礦、化工、建筑、交通等領域。

在國外，Song等人提出一種蟻群搜索方法用以處理因多目標約束引起的熱量與能量擴散問題[1]。RACZY?SKI等人將蟻群算法應用于解決因Lennard-Jones現象導致的原子相互作用的最小勢能問題[2]。Lenin等人將蟻群算法應用于無功功率的優化和電力系統的電壓控制中[3]。SLIMANI等人將蟻群算法用于電力系統的優化能量流問題，以使總的熱能損耗降到最低[4]。Dréo等人提出了“持續作用蟻群算法”以處理連續函數多目標最小化問題[5]。Randall將平行分解技術應用于蟻群算法中，以使旅行銷售問題的處理更加快捷、有效[6]。

在國內，康莉等人提出一種新的非線性多目標跟蹤方法實現對單目標的跟蹤，使蟻群算法適用于解決數據關聯問題[7]。高尚等人提出了求解旅行商問題的多樣信息素的蟻群算法[8]。馬文霜等人通過對ACS－3－opt算法的改進，提出一種蟻群改進算法，用于大中型規模TSP問題的求解[9]。李梅娟等人設計一種改進的蟻群算法，用于自動化倉庫固定貨架揀選作業問題的解決[10]。康莉等人提出了一種新的基于蟻群算法的多目標跟蹤方法:通過將多目標跟蹤中的數據關聯問題表示為具有約束條件的優化問題，用蟻群算法對該優化問題求解得到最優關聯[11]。梁云川等人提出了一種基于子集類蟻群模型的屬性相對約簡算法以處理粗糙集屬性約簡問題[12]。

輸電工程中的工期—成本優化的目的是為了尋求工期縮短而直接成本最少，對于輸電工程施工過程中的成本控制、工期控制、資源管理具有極其重要的作用。本文應用蟻群算法實現對輸電線路施工進行工期－成本優化。

1 工期－成本優化數學模型

工期－成本優化是在關鍵線路上選擇趕工成本增率最低的工序或工序組合，通過縮短總工期，并把每次縮短工期后的工程的直接成本和間接成本疊加得到一系列工期和成本均不相同的方案。

工期－成本優化涉及兩類工程實際問題:允許工期條件下工程最低成本，規定工期條件下最低成本。

(1)允許工期條件下，最低成本數學模型

工程項目的直接成本隨著工期延長而減少，間接成本隨著工期延長而增加，因而項目的總成本隨著工期的延長必然出現一個先減后增的過程，確定最低成本的數學模型如下:

式中:TC為項目的總成本，是項目的直接費用和間接費用之和;DC為項目的直接費用，由項目的所有活動的直接費相加得到;IC為項目的間接費用，與項目工期有關的費用;fi(di)為工作i的持續時間與直接費用之間的函數，可以是線性的，也可以是非線性的;di為工作i的持續時間;e為項目的間接費用率，是一個常數;為極限狀態下工作的持續時間;為正常狀態下工作的持續時間;tj為工作j的結束時間;ti為工作i的結束時間;P(j)為工作j的緊前工作集合;TN為項目的實際工期;TD為項目的計劃工期。

公式(2)的約束是對工作持續時間的約束，保證活動的持續時間在允許的工期范圍之內;公式(3)的約束是工序約束，保證活動的施工順序符合邏輯關系。

(2)規定工期條件下，最低成本數學模型

如果項目按正常條件施工會超過規定工期，不能滿足工期要求，就需要對工期進行壓縮，也就是工期固定、成本最低的數學模型如下:

式中各物理量的含義同上。

若TN固定，間接成本變成一個常數，公式(4)eTN中的項可以去掉，不會影響求解結果，這樣目標函數變為:

2 蟻群算法設計

蟻群算法是一種基于種群的啟發式仿生進化算法，算法中螞蟻的行為模擬生物界中的螞蟻覓食行為。單只螞蟻在所通過的路徑上留下信息素，其他螞蟻則根據信息素選擇覓食線路。螞蟻在選擇路徑時會選擇其中一條信息素濃度最大的線路。線路質量好壞與信息素多少相關。路線上的信息素隨時間增加而逐漸減少，避免陷入局部最優解。

在進行線路搜索時，螞蟻通過轉移概率、選擇節點來完成整個旅程。搜索開始時，每條線路分配少量的相同信息素。每只螞蟻通過啟發因子和信息素因子選擇節點。啟發因子為ηij，信息素因子為τij。螞蟻應用Pseudo-Random-Proporlional法則選擇下一個節點。螞蟻在節點集合S中選取未曾選取的節點Si，使得下列式子值最大:

式中:α為路徑的相對重要性，β為能見度的相對重要性，α和β均是常量，且α≥0、β≥0。

從集合S中所選取的節點由轉移概率準則決定:

轉移概率是啟發因子和信息素因子之間平衡的結果。由啟發因子可知:越近的節點，所需時間越短，被選擇的概率越大。依據信息素因子，如果線路(Si，Sj)上交通量很大，則執行自催化過程。

啟發因子ηij可由下式算出:

式中:f(xj)為蟻群中任意一個螞蟻Xj的函數。

Si和Sj之間的信息素由下式定義:

通過蟻群算法進行輸電工程工期－成本優化的算法流程見圖1。

圖1 算法流程圖

圖2 網絡計劃圖

3 算 例

選取500 kV輸電線路施工為例，其網絡計劃見圖2，各工序實施方案、持續時間和直接費用見表1。工地每天的管理費為2500元/天。

按照上述提出的算法編制程序，設置程序參數如下:p=0.9，迭代次數為20，螞蟻數為40，以程序運行10次的結果作分析數據，表2表示10次運行結果。

表1 實施方案、持續時間、直接費用表

表2 分析結果

由表2可見，通過蟻群算法進行工期－成本優化時，可以按照優化序列結果，依據施工單位的經濟、技術、設備、人員配置情況，在遵照與建設單位簽訂的施工合同條款的前提下，選取最優的施工方案。

4 結 論

本文研究了輸電工程施工中的工期－成本優化問題應用蟻群算法進行求解的問題。首先分析了工期－成本優化問題中所涉及的兩類工程實際問題的優化模型的建立，對蟻群算法進行分析并將其應用于所建的優化模型中，選擇實際輸電線路工程運用所確定的方法進行工期－成本優化，優化結果表明蟻群算法對于輸電工程施工中的工期－成本優化是可行的。

[1]Y.H.Song，C.S.Chou，T.J.Stonham.Combined Heat and Power Economic Dispatch by Improved Ant Colony Search Algorithm[J].Electric Power Systems Research，1999，52(2):115 －121.

[2]P.RACZY?SKI，Z.GBURSKI.The Search for Minimum Potential Energy Structures of Small Atomic Clusters Application of The Ant Colony Algorithm[J].Materials Science － Poland，2005，23(3):599 －606.

[3]K.Lenin，M.R.Mohan.Ant Colony Search Algorithm for Optimal Reactive Power Optimization[J].SERBIAN JOURNAL OF ELECTRICAL ENGINEERING，2006，3(1):77 － 88.

[4]Linda Slimani，Tarek Bouktir.An Ant Colony Optimization for Solving The Optical Power Flow Problem in Medium － Scale Electrical Network[J].Journal of Electrical Engineering，2006，6(1):10 －15.

[5]J.Dréo，P.Siarry.Continuous Interacting Ant Colony Algorithm Based on Dense Heterarchy[J].Future Generation Computer Systems，2004，20(5):841－856.

[6]Marcus Randall.A Parallel Implementation of Ant Colony Optimization[J].Journal of Parallel and Distributed Computing，2002，62(9):1421－1432.

[7]康莉，謝維信，黃敬雄.基于SIS框架和蟻群算法的非線性多目標跟蹤[J].電子與信息學報，2008，30(9):2148－2151.

[8]高尚，孫玲芳，侯志遠，楊靜宇.基于多樣信息素的蟻群算法[J].計算機科學，2006，33(10):160－162.

[9]馬文霜，張洪偉.基于改進ACS－3－opt蟻群算法的TSP[J].計算機工程，2008，34(19):200－203.

[10]李梅娟，陳雪波，劉臣奇.基于改進蟻群算法揀選作業優化問題的求解[J].計算機工程，2009，35(3):219－221.

[11]康莉，謝維信，黃敬雄.基于蟻群算法的多目標跟蹤方法[J].系統工程與電子技術，2008，30(9):1782－1784.

[12]梁云川，李德玉.基于子集類蟻群模型的屬性相對約簡算法[J].計算機科學，2008，35(1):147－150.