蟻群算法在輸電工程工期成本優(yōu)化中的應(yīng)用

屈成忠，馬瑞楓，劉衛(wèi)星，馬曉東

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

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

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

在國內(nèi)，康莉等人提出一種新的非線性多目標(biāo)跟蹤方法實(shí)現(xiàn)對(duì)單目標(biāo)的跟蹤，使蟻群算法適用于解決數(shù)據(jù)關(guān)聯(lián)問題[7]。高尚等人提出了求解旅行商問題的多樣信息素的蟻群算法[8]。馬文霜等人通過對(duì)ACS－3－opt算法的改進(jìn)，提出一種蟻群改進(jìn)算法，用于大中型規(guī)模TSP問題的求解[9]。李梅娟等人設(shè)計(jì)一種改進(jìn)的蟻群算法，用于自動(dòng)化倉庫固定貨架揀選作業(yè)問題的解決[10]?？道虻热颂岢隽艘环N新的基于蟻群算法的多目標(biāo)跟蹤方法:通過將多目標(biāo)跟蹤中的數(shù)據(jù)關(guān)聯(lián)問題表示為具有約束條件的優(yōu)化問題，用蟻群算法對(duì)該優(yōu)化問題求解得到最優(yōu)關(guān)聯(lián)[11]。梁云川等人提出了一種基于子集類蟻群模型的屬性相對(duì)約簡算法以處理粗糙集屬性約簡問題[12]。

輸電工程中的工期—成本優(yōu)化的目的是為了尋求工期縮短而直接成本最少，對(duì)于輸電工程施工過程中的成本控制、工期控制、資源管理具有極其重要的作用。本文應(yīng)用蟻群算法實(shí)現(xiàn)對(duì)輸電線路施工進(jìn)行工期－成本優(yōu)化。

1 工期－成本優(yōu)化數(shù)學(xué)模型

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

工期－成本優(yōu)化涉及兩類工程實(shí)際問題:允許工期條件下工程最低成本，規(guī)定工期條件下最低成本。

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

工程項(xiàng)目的直接成本隨著工期延長而減少，間接成本隨著工期延長而增加，因而項(xiàng)目的總成本隨著工期的延長必然出現(xiàn)一個(gè)先減后增的過程，確定最低成本的數(shù)學(xué)模型如下:

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

公式(2)的約束是對(duì)工作持續(xù)時(shí)間的約束，保證活動(dòng)的持續(xù)時(shí)間在允許的工期范圍之內(nèi);公式(3)的約束是工序約束，保證活動(dòng)的施工順序符合邏輯關(guān)系。

(2)規(guī)定工期條件下，最低成本數(shù)學(xué)模型

如果項(xiàng)目按正常條件施工會(huì)超過規(guī)定工期，不能滿足工期要求，就需要對(duì)工期進(jìn)行壓縮，也就是工期固定、成本最低的數(shù)學(xué)模型如下:

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

若TN固定，間接成本變成一個(gè)常數(shù)，公式(4)eTN中的項(xiàng)可以去掉，不會(huì)影響求解結(jié)果，這樣目標(biāo)函數(shù)變?yōu)?

2 蟻群算法設(shè)計(jì)

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

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

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

從集合S中所選取的節(jié)點(diǎn)由轉(zhuǎn)移概率準(zhǔn)則決定:

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

啟發(fā)因子ηij可由下式算出:

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

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

通過蟻群算法進(jìn)行輸電工程工期－成本優(yōu)化的算法流程見圖1。

圖1 算法流程圖

圖2 網(wǎng)絡(luò)計(jì)劃圖

3 算 例

選取500 kV輸電線路施工為例，其網(wǎng)絡(luò)計(jì)劃見圖2，各工序?qū)嵤┓桨?、持續(xù)時(shí)間和直接費(fèi)用見表1。工地每天的管理費(fèi)為2500元/天。

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

表1 實(shí)施方案、持續(xù)時(shí)間、直接費(fèi)用表

表2 分析結(jié)果

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

4 結(jié) 論

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

[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框架和蟻群算法的非線性多目標(biāo)跟蹤[J].電子與信息學(xué)報(bào)，2008，30(9):2148－2151.

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

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

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

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

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