摘 要

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

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

關(guān)鍵詞：環(huán)狀燃?xì)夤芫W(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è)計(jì)燃?xì)夤芫W(wǎng)時(shí)，設(shè)計(jì)人員通常根據(jù)經(jīng)驗(yàn)確定布置形式，這使得管網(wǎng)的合理性有待探討。此外，國(guó)內(nèi)外學(xué)者對(duì)枝狀管網(wǎng)的布置優(yōu)化問題研究較多，對(duì)環(huán)狀管網(wǎng)的布置優(yōu)化研究較少^[1-5]。本文將環(huán)狀燃?xì)夤芫W(wǎng)布置優(yōu)化問題轉(zhuǎn)換為旅行商問題(Traveling Salesman Problem，簡(jiǎn)稱TSP)，采用蟻群算法進(jìn)行求解。

1　TSP

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

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

2　蟻群算法

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

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

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

 

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

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

n個(gè)節(jié)點(diǎn)的集合為：

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

式中C——n個(gè)節(jié)點(diǎn)的集合

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

節(jié)點(diǎn)i與j路徑長(zhǎng)度的集合為：

L＝{lijúci，cjÌC}

 

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

lij——節(jié)點(diǎn)i與j路徑長(zhǎng)度，m

xi、yi——節(jié)點(diǎn)i在二維坐標(biāo)系(xOy)中的坐標(biāo)

xi、yi——節(jié)點(diǎn)歹在二維坐標(biāo)系(xOy)中的坐標(biāo)

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

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

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

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

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

 

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

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

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

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

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

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

 

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

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

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

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

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

對(duì)于Ant-Cycle模型：

 

式中Q——信息素強(qiáng)度

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

2.2　參數(shù)確定

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

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

 

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

3　優(yōu)化目標(biāo)

引入當(dāng)量費(fèi)用長(zhǎng)度概念，以環(huán)狀燃?xì)夤芫W(wǎng)造價(jià)最低為目標(biāo)，建立優(yōu)化目標(biāo)函數(shù)Lmin為：

 

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

lw,ij——當(dāng)量費(fèi)用長(zhǎng)度，m

uij——判定系數(shù)

文獻(xiàn)[7—8]認(rèn)為燃?xì)夤芫W(wǎng)造價(jià)近似為管長(zhǎng)的線性函數(shù)，基于這種理論，當(dāng)量費(fèi)用長(zhǎng)度lw,ij的計(jì)算式為：

 

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

¦ij——燃?xì)夤艿涝趯?shí)際敷設(shè)方式下節(jié)點(diǎn)i與j路徑間管道單位管長(zhǎng)造價(jià)，元／m

¦——燃?xì)夤艿涝跇?biāo)準(zhǔn)敷設(shè)方式下的單位管長(zhǎng)造價(jià)，元／m

4　算例

選取某小型環(huán)狀燃?xì)夤芫W(wǎng)(中壓)作為優(yōu)化對(duì)象，氣源擬采用單氣源供氣。為了方便討論，進(jìn)行以下設(shè)定：所有的節(jié)點(diǎn)間管道的權(quán)系數(shù)相等，且為1；只考慮形成單環(huán)狀管網(wǎng)。中壓管網(wǎng)的初步布置形式見圖l，節(jié)點(diǎn)4與氣源連接，各節(jié)點(diǎn)在二維坐標(biāo)系中的坐標(biāo)見表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，燃?xì)夤芫W(wǎng)總長(zhǎng)度為15.143km。

 

參考文獻(xiàn)：

[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]呂木英．基于遺傳算法的城市燃?xì)夤芫W(wǎng)最優(yōu)化布局研究(碩士學(xué)位論文)[D]．武漢：武漢理工大學(xué)，2009：56-59．

[4]王垣，段常貴．改進(jìn)遺傳算法在燃?xì)夤芫W(wǎng)布局優(yōu)化中的應(yīng)用[J]．哈爾濱工業(yè)大學(xué)學(xué)報(bào)，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)，胡攀峰，等．用遺傳算法進(jìn)行輸氣管網(wǎng)布置的優(yōu)化設(shè)計(jì)研究[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è)

作者單位：中國(guó)石油大學(xué)(華東)儲(chǔ)運(yùn)與建筑工程學(xué)院

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

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