摘 要

摘　要：將環(huán)狀燃氣管網(wǎng)布置優(yōu)化問題轉(zhuǎn)換為旅行商問題，采用蟻群算法進行求解，列舉了算例。關(guān)鍵詞：環(huán)狀燃氣管網(wǎng) 布置優(yōu)化 旅行商問題 蟻群算法Layout Optimization of Loop Ga

摘　要：將環(huán)狀燃氣管網(wǎng)布置優(yōu)化問題轉(zhuǎn)換為旅行商問題，采用蟻群算法進行求解，列舉了算例。

關(guān)鍵詞：環(huán)狀燃氣管網(wǎng)  布置優(yōu)化  旅行商問題  蟻群算法

Layout Optimization of Loop Gas Pipe Network Based on Ant Colony Algorithm

Abstract：The layout optimization problem of loop gas pipe network is converted into a traveling salesman problem，and solution is performed by ant colony algorithm．The calculation examples are enumerated．

Keywords：loop gas pipe network；layout optimization；traveling salesman problem；ant colony algorithm

 

在設(shè)計燃氣管網(wǎng)時，設(shè)計人員通常根據(jù)經(jīng)驗確定布置形式，這使得管網(wǎng)的合理性有待探討。此外，國內(nèi)外學(xué)者對枝狀管網(wǎng)的布置優(yōu)化問題研究較多，對環(huán)狀管網(wǎng)的布置優(yōu)化研究較少^[1-5]。本文將環(huán)狀燃氣管網(wǎng)布置優(yōu)化問題轉(zhuǎn)換為旅行商問題(Traveling Salesman Problem，簡稱TSP)，采用蟻群算法進行求解。

1　TSP

TSP是圖論領(lǐng)域中著名問題之一。形象地說，TSP是指一名旅行售貨員從一座城市出發(fā)，訪問每座城市恰好一次，再回到出發(fā)城市，最終使得旅費最低。對于燃氣管網(wǎng)，將調(diào)壓站、調(diào)壓裝置視為TSP中的“城市(節(jié)點)”，節(jié)點之間敷設(shè)的燃氣管道造價視為“旅費”，要求從起始節(jié)點出發(fā)，訪問剩余的每個節(jié)點恰好一次，再回到起始節(jié)點，要求燃氣管道造價最低。由此可知，環(huán)狀燃氣管網(wǎng)的布置優(yōu)化問題與TSP十分相似，因此可以將環(huán)狀燃氣管網(wǎng)布置優(yōu)

化問題轉(zhuǎn)換為TSP。

2　蟻群算法

蟻群算法(Ant Colony Algorithm，ACA)是1991年M．Dorigo提出的一種智能算法。該算法來源于螞蟻種群的覓食行為，其本質(zhì)是一個龐大的智能體系，具有很強的容錯性及并行計算能力，可與其他算法無縫銜接。

2.1　蟻群算法的數(shù)學(xué)模型

為了方便討論，設(shè)bi(t)表示t時刻位于節(jié)點i的螞蟻數(shù)量，則螞蟻總數(shù)量m的表達式為：

 

式中m——螞蟻總數(shù)量

n——節(jié)點總數(shù)

n個節(jié)點的集合為：

C＝{c1，c2，c3，…，cn}

式中C——n個節(jié)點的集合

c1…cn——集合C中的元素

節(jié)點i與j路徑長度的集合為：

L＝{lijúci，cjÌC}

 

式中L——集合C中節(jié)點i與j路徑長度的集合

lij——節(jié)點i與j路徑長度，m

xi、yi——節(jié)點i在二維坐標系(xOy)中的坐標

xi、yi——節(jié)點歹在二維坐標系(xOy)中的坐標

t時刻節(jié)點i與j路徑上殘留信息量集合G的表達式為：

G＝{tij(t)ú ci，cj，ÌC}

式中G——t時刻節(jié)點i與j路徑上殘留信息量集合

tij(t)——t時刻節(jié)點i與j路徑上的殘留信息量，在初始時刻各條路徑上殘留信息量相等

螞蟻k(1，2，3，…，m)的運動方向是根據(jù)各條路徑上的殘留信息量來確定的，t時刻螞蟻k由節(jié)點i轉(zhuǎn)移到節(jié)點j的狀態(tài)轉(zhuǎn)移概率為：

 

式中Pij(t)——t時刻螞蟻k由節(jié)點i轉(zhuǎn)移到節(jié)點j的狀態(tài)轉(zhuǎn)移概率

a——信息啟發(fā)式因子，表示軌跡的相對重要性

hij(t)——啟發(fā)函數(shù)

b——期望啟發(fā)式因子，表示能見度的相對重要性

A——螞蟻k下一步允許選擇的節(jié)點集合，A＝{C-B}，B表示螞蟻k已經(jīng)走過的節(jié)點集合

需要注意的是，在每只螞蟻走完一步或者完成對所有n個節(jié)點的遍歷后，要對殘留信息進行更新處理，否則過多的殘留信息會淹沒啟發(fā)信息。因此，在螞蟻經(jīng)過一個節(jié)點或經(jīng)過所有節(jié)點完成一個循環(huán)所需的時間T后，即t+T時刻在節(jié)點i與j路徑上的殘留信息量tij(t+T)可按以下規(guī)則進行調(diào)整：

 

式中tij(t+T)——t+T時刻在節(jié)點i與j路徑上的殘留信息量

r——信息素揮發(fā)系數(shù)，取值范圍為[0，1)

Dtij(t)——本次循環(huán)中節(jié)點i與j路徑上的信息素增量，初始時刻為0

Dtij,k(t)——本次循環(huán)中第k只螞蟻在節(jié)點i與j路徑上的信息素增量

M．Dorigo提出了3種不同的信息素更新模型，分別為：Ant-Cycle模型、Ant-Quantity模型、Ant-Density模型，差別在于對Dtij,k(t)的求解方法不同。在求解Dtij,k(t)時，Ant-Quantity模型、Ant-Density模型采用局部信息(即螞蟻完成一步便更新當前路徑上的信息素)，而Ant-Cycle模型采用整體信息(即螞蟻完成一個循環(huán)后才更新所有路徑上的信息素)。Ant-Cycle模型更適用于求解TSP，因此本文采用Ant-Cycle模型來更新信息素。

對于Ant-Cycle模型：

 

式中Q——信息素強度

Lk——第五只螞蟻在本次循環(huán)中所走路徑的總長度

2.2　參數(shù)確定

蟻群算法中的a、b、r、m、Q等參數(shù)的設(shè)定尚無嚴格的理論依據(jù)，至今還沒有確定最優(yōu)參數(shù)的一般方法，已公布的參數(shù)設(shè)置成果都是針對不同蟻群算法模型的。當采用Ant-Cycle模型時，理想的參數(shù)設(shè)定范圍為：0≤a≤5，0≤b≤5，0.1≤r≤0.99，10≤Q≤10000。

在面對具體問題時，可以按照段海濱^[6]總結(jié)出的方法確定最優(yōu)參數(shù)，具體步驟如下：第一步，確定m，按照

 

確定所需的螞蟻數(shù)量。第二步，調(diào)整設(shè)定范圍大的參數(shù)：a、b、Q。第三步，調(diào)整設(shè)定范圍小的參數(shù)：r。反復(fù)按照以上步驟進行調(diào)整，直至選擇出一組比較滿意的參數(shù)為止。

3　優(yōu)化目標

引入當量費用長度概念，以環(huán)狀燃氣管網(wǎng)造價最低為目標，建立優(yōu)化目標函數(shù)Lmin為：

 

式中Lmin——優(yōu)化目標函數(shù)

lw,ij——當量費用長度，m

uij——判定系數(shù)

文獻[7—8]認為燃氣管網(wǎng)造價近似為管長的線性函數(shù)，基于這種理論，當量費用長度lw,ij的計算式為：

 

式中Wij——節(jié)點i與j路徑間管道的權(quán)系數(shù)

¦ij——燃氣管道在實際敷設(shè)方式下節(jié)點i與j路徑間管道單位管長造價，元／m

¦——燃氣管道在標準敷設(shè)方式下的單位管長造價，元／m

4　算例

選取某小型環(huán)狀燃氣管網(wǎng)(中壓)作為優(yōu)化對象，氣源擬采用單氣源供氣。為了方便討論，進行以下設(shè)定：所有的節(jié)點間管道的權(quán)系數(shù)相等，且為1；只考慮形成單環(huán)狀管網(wǎng)。中壓管網(wǎng)的初步布置形式見圖l，節(jié)點4與氣源連接，各節(jié)點在二維坐標系中的坐標見表1。

 

 

利用C語言編制蟻群算法程序，經(jīng)過多次試算確定蟻群算法的參數(shù)為：m＝15，a＝1.0，b＝5.0，r＝0.1，Q=100。迭代最大次數(shù)為200，防止出現(xiàn)死循環(huán)。優(yōu)化后的環(huán)狀管網(wǎng)布置形式見圖2，燃氣管網(wǎng)總長度為15.143km。

 

參考文獻：

[1]CHANG S K．The generation of minimal tree with a steiner topology[J]．Journal of Association of Computing Machinery，1972(4)：699-711．

[2]FLANIGN O．Constrained derivatives in natural gas pipeline system optimization[J]．Journal of Petroleum Technology，1972(5)：549-556．

[3]呂木英．基于遺傳算法的城市燃氣管網(wǎng)最優(yōu)化布局研究(碩士學(xué)位論文)[D]．武漢：武漢理工大學(xué)，2009：56-59．

[4]王垣，段常貴．改進遺傳算法在燃氣管網(wǎng)布局優(yōu)化中的應(yīng)用[J]．哈爾濱工業(yè)大學(xué)學(xué)報，2006，38(1)：46-48．

[5]SALZBORN B．Optimal design of gas pipeline networks[J]．The Journal of the Operational Research Society，1979(12)：1047-1060．

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

[7]劉洪，胡昌權(quán)，胡攀峰，等．用遺傳算法進行輸氣管網(wǎng)布置的優(yōu)化設(shè)計研究[J]．天然氣工業(yè)，2006，26(10)：127-129．

[8]聶廷哲，段常貴．基于Hopfield神經(jīng)網(wǎng)絡(luò)的輸氣管網(wǎng)布線優(yōu)化[J]．天然氣工業(yè)，2005，25(2)：155-157．

 

本文作者：李自力  趙峰  李佳  楊立業(yè)

作者單位：中國石油大學(xué)(華東)儲運與建筑工程學(xué)院

  武漢煉化工程設(shè)計有限責任公司

  勝利油田勝利勘察設(shè)計研究院有限公司