蟻群算法在弱電管線路由優(yōu)化中的應(yīng)用研究

景艷龍，趙立君 俞必勇

(北京工商大學(xué)規(guī)劃建設(shè)處，北京 100048) (北京工商大學(xué)網(wǎng)絡(luò)中心，北京 100048)

蟻群算法在弱電管線路由優(yōu)化中的應(yīng)用研究

景艷龍，趙立君 俞必勇

(北京工商大學(xué)規(guī)劃建設(shè)處，北京 100048) (北京工商大學(xué)網(wǎng)絡(luò)中心，北京 100048)

基于蟻群算法，建立地下弱電管線優(yōu)化模型，并將該模型應(yīng)用于弱電管線路由優(yōu)化設(shè)計(jì)中。結(jié)果表明，弱電管線路由優(yōu)化后可以節(jié)省施工費(fèi)用，說明該方法具有可行性，可以為弱電管線路由優(yōu)化設(shè)計(jì)提供參考。

弱電管線；路由；優(yōu)化；蟻群算法

近年來，弱電管線的規(guī)劃越來越受到人們的重視，其中路由規(guī)劃是一個(gè)重要研究方向。路由規(guī)劃除要考慮符合設(shè)計(jì)規(guī)范、方便施工外，還要考慮節(jié)約建設(shè)成本，這是進(jìn)行路由優(yōu)化的主要目的。鋪設(shè)弱電管線施工過程包括鋪設(shè)PVC格柵管和沿PVC格柵管鋪設(shè)弱電線纜2個(gè)階段。目前對(duì)弱電管線路由優(yōu)化的研究大多只限于其中1個(gè)階段，而沒有對(duì)上述2個(gè)階段進(jìn)行整體優(yōu)化。為此，筆者在考慮鋪設(shè)線路最短的基礎(chǔ)上，利用蟻群算法，將鋪設(shè)弱電管線施工階段的總工程費(fèi)最低作為優(yōu)化目標(biāo)，從而達(dá)到節(jié)約施工費(fèi)用的目的。

1 蟻群算法概述

蟻群算法是一種新興的模擬仿生算法，具有模擬生物界群體覓食的能力，并且能夠在實(shí)際的路徑搜索過程中對(duì)外界的影響作出動(dòng)態(tài)響應(yīng)，由于蟻群算法原型本身就是一個(gè)尋找最短路徑的模型，因此它在路徑優(yōu)化方面有著天然優(yōu)勢(shì)[1]。

為了便于描述蟻群算法數(shù)學(xué)模型，引入如下變量：N表示路由中的節(jié)點(diǎn)數(shù)；M是蟻群中螞蟻的數(shù)量；T表示循環(huán)次數(shù)；dij(i，j=1，2，…，N)表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的距離；τij(t)表示t(0

(1)

式中，allowedk={N-tabuk}表示螞蟻k下一步允許選擇的節(jié)點(diǎn)；α和β為2個(gè)參數(shù)，分別反映螞蟻在運(yùn)動(dòng)過程中所積累的信息和啟發(fā)信息在螞蟻選擇路徑中的相對(duì)重要性；ηij為啟發(fā)函數(shù)，其表達(dá)式為：ηij(t)=1/(dij+dje)；dij為相鄰兩節(jié)點(diǎn)之間的距離；dje為下一步可選節(jié)點(diǎn)和終點(diǎn)之間的直線距離。

為了避免殘留信息素過多引起殘留信息淹沒啟發(fā)信息，在每只螞蟻?zhàn)咄暌徊交蛲瓿梢粋€(gè)循環(huán)后，要對(duì)殘留信息進(jìn)行更新，可以采用局部更新和全局更新相結(jié)合的更新方式。

當(dāng)?shù)趉只螞蟻完成一條搜索路徑時(shí)，在其經(jīng)過的邊上按照局部更新規(guī)則對(duì)信息素濃度進(jìn)行局部更新[3]：

(2)

當(dāng)M只螞蟻全部完成一次循環(huán)，則對(duì)本次循環(huán)中產(chǎn)生的全局最優(yōu)路徑上的邊按照全局更新規(guī)則進(jìn)行更新：

(3)

式中，Lgb為到目前為止找到的最優(yōu)路徑。

2 地下弱電管線優(yōu)化模型的建立

在對(duì)弱電管線路由進(jìn)行優(yōu)化之前，首先要根據(jù)地上建筑情況和地下管線情況，確定可行的路由，在可行的路由基礎(chǔ)上確定最優(yōu)路徑。

2.1弱電管線可行路由的規(guī)劃

可行路由規(guī)劃的原則包括以下幾方面[4]：①為了方便施工和不影響交通，以及減少管線負(fù)荷，管線路由應(yīng)設(shè)在道路兩側(cè)人行道上或綠地內(nèi)。②為了方便管井的挖掘，管線路由應(yīng)設(shè)在地上障礙物、地下管線較少的地段。 ③管線路由應(yīng)考慮新舊管道銜接問題。④管線位置盡可能與現(xiàn)有弱電設(shè)備在路的同側(cè)，便于連接。⑤管線位置的選擇應(yīng)方便出戶入戶。

2.2費(fèi)用權(quán)值系數(shù)的確定

由于鋪設(shè)弱電管線分為鋪設(shè)PVC格柵管道和鋪設(shè)弱電線纜2個(gè)階段，因此鋪設(shè)管線的總費(fèi)用為線纜鋪設(shè)費(fèi)用與PVC格柵管道鋪設(shè)費(fèi)用之和：

(4)

式中，Cij表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j段管線鋪設(shè)總費(fèi)用；Cl表示每段線纜鋪設(shè)單價(jià)；Cd表示從每段PVC管道鋪設(shè)單價(jià)；Cw表示管線所經(jīng)路由中弱電井的造價(jià)；k′表示弱電井?dāng)?shù)量；dij表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j段距離。

如果起點(diǎn)和終點(diǎn)不同的2條及以上線纜路由在某一路段可沿同一管溝鋪設(shè)，即部分路由重合，則線纜費(fèi)用為多條線纜的總費(fèi)用，而管道費(fèi)用為1條管道的費(fèi)用。如果管道費(fèi)用計(jì)入第1條線纜，則第2條及以上線纜管道的費(fèi)用為0，則式(4)可以改寫為：

(5)

式中，kij為加權(quán)系數(shù)，如果進(jìn)行某條管線路由優(yōu)化時(shí)，發(fā)現(xiàn)已有其他管線從本段路由經(jīng)過，則kij取0，否則取1。

2.3優(yōu)化的步驟及優(yōu)化目標(biāo)函數(shù)的確定

假設(shè)需要鋪設(shè)的管線條數(shù)為m，將第1條進(jìn)行最低費(fèi)用優(yōu)化的管線稱為首選優(yōu)化管線，確定的優(yōu)化步驟如下：①任選出1條線路j′作為首選優(yōu)化管線，利用蟻群算法進(jìn)行優(yōu)化；②在確定了首選優(yōu)化管線的基礎(chǔ)上，任選第2條管線進(jìn)行優(yōu)化；③重復(fù)步驟②，隨機(jī)選第i′條管線，在前i′-1條路徑已確定的條件下，進(jìn)行管線路由優(yōu)化；④當(dāng)所有管線路由均優(yōu)化后，將所有的管線費(fèi)用求和，表示為：

(6)

由于第2條及以后的管線路由優(yōu)化都在首選優(yōu)化線路選定的基礎(chǔ)上進(jìn)行，首選優(yōu)化線路不同會(huì)導(dǎo)致施工總費(fèi)用不同，因而需要把m條管線中的每1條都作為首選優(yōu)化線路進(jìn)行優(yōu)化并計(jì)算總費(fèi)用，然后進(jìn)行對(duì)比，從而找出費(fèi)用最低的優(yōu)化方案。

所以，最終優(yōu)化的目標(biāo)函數(shù)為：

(7)

3 應(yīng)用實(shí)例

圖1 規(guī)劃的可行路由

為了驗(yàn)證優(yōu)化模型的可行性，以北京工商大學(xué)阜成路校區(qū)西區(qū)架空線改造工程中7條光纜的鋪設(shè)為例，進(jìn)行了弱電管線路由優(yōu)化設(shè)計(jì)。

3.1可行路由的規(guī)劃

根據(jù)可行路由規(guī)劃的原則，規(guī)劃出架空線改造工程的可行路由(見圖1)。

3.2Cl、Cd、Cw參數(shù)的確定

根據(jù)工程實(shí)際測(cè)算，7條管線線纜費(fèi)用(Cl)的值分別為142.5、240、101.25、101.25、320、160和95元/m；管道鋪設(shè)費(fèi)用(Cd)為222.52元/m；弱電井工程費(fèi)用(Cw)為3750元/個(gè)。

3.3運(yùn)行結(jié)果

確定相關(guān)參數(shù)后,利用開發(fā)的軟件和地理信息組件運(yùn)行蟻群優(yōu)化算法程序，使用ArcEngine的渲染方法對(duì)找到的最優(yōu)路徑進(jìn)行顯示(見圖2)，圖3為原設(shè)計(jì)路由。經(jīng)過計(jì)算，原設(shè)計(jì)路由總造價(jià)為555882.11元，優(yōu)化路由的總造價(jià)為526296.69元，施工總造價(jià)減少5.32%，說明筆者提出的優(yōu)化方法是可行的，可以應(yīng)用于弱電管線路由優(yōu)化設(shè)計(jì)中。

圖2 優(yōu)化路由 圖3 原設(shè)計(jì)路由

[1]段海濱.蟻群算法原理及其應(yīng)用[M].北京：科學(xué)出版社，2005.

[2]Dorigo M，Gambardella L M. Ant colony system: A cooperative learning approach to the traveling salesman problem [J]. IEEE Transactions on Evolutionary Computation, 1997, 21(1)：53-66.

[3]黃貴玲，高西全.基于蟻群算法的最短路徑問題的研究與應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2007，43(13)：233-235.

[4]韋鶴平.最優(yōu)化技術(shù)應(yīng)用[M].上海:同濟(jì)大學(xué)出版社,2000.

[編輯] 李啟棟

10.3969/j.issn.1673-1409(N).2012.11.042

TP301 6

A

16731409(2012)11N13003