基于粒子群優(yōu)化算法的樹狀注水管網(wǎng)拓樸優(yōu)化

向 華

(長江大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，湖北 荊州 434023)

羅 穎

(湖南大學(xué)信息科學(xué)與工程學(xué)院，湖南 長沙 410082)

基于粒子群優(yōu)化算法的樹狀注水管網(wǎng)拓樸優(yōu)化

向 華

(長江大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，湖北 荊州 434023)

羅 穎

(湖南大學(xué)信息科學(xué)與工程學(xué)院，湖南 長沙 410082)

樹狀注水管網(wǎng)拓?fù)鋬?yōu)化設(shè)計(jì)問題是一個(gè)涉及離散變量、連續(xù)變量的大型非線性優(yōu)化問題。使用粒子群優(yōu)化算法在現(xiàn)有管網(wǎng)的基礎(chǔ)上進(jìn)行管網(wǎng)優(yōu)化設(shè)計(jì)。該算法是從隨機(jī)解出發(fā)，根據(jù)迭代尋找最優(yōu)解，通過適應(yīng)度來評價(jià)解的品質(zhì)。實(shí)際算例表明，該算法對樹狀注水管網(wǎng)優(yōu)化效果比較明顯。

粒子群優(yōu)化算法；注水管網(wǎng)；拓?fù)鋬?yōu)化

油田注水系統(tǒng)管網(wǎng)是由許多注水站、配水間、注水井及連接它們的管線組成的復(fù)雜多級網(wǎng)絡(luò)系統(tǒng)，一般包括環(huán)狀和樹狀(也稱星式)2種形式。筆者擬針對樹狀注水管網(wǎng)中配水間到注水井之間的樹狀形式管網(wǎng)進(jìn)行拓?fù)鋬?yōu)化。注水管網(wǎng)拓?fù)鋬?yōu)化設(shè)計(jì)問題是一個(gè)涉及離散變量、連續(xù)變量的大型非線性優(yōu)化問題，該問題是布局-分配問題的擴(kuò)充，已被證明為非確定多項(xiàng)式(NP)問題。Kennedy J[1]與Eberhart R C[2]分別從鳥群覓食過程中表現(xiàn)的行為得到啟發(fā)而研究出粒子群優(yōu)化算法 (Particle Swarm Optimization,PSO)，該算法可以最大限度地用于搜索該類NP問題的最優(yōu)解。筆者根據(jù)油田注水系統(tǒng)管網(wǎng)的特點(diǎn)建立相應(yīng)的粒子群優(yōu)化模型，以求解最優(yōu)化的樹狀注水管網(wǎng)拓樸結(jié)構(gòu)。

1 粒子群優(yōu)化算法

在粒子群優(yōu)化算法中，問題域在D維空間中，每個(gè)個(gè)體都是一個(gè)沒有體積的粒子(點(diǎn))，該粒子以一定速度飛行，其飛行速度可根據(jù)自身飛行經(jīng)驗(yàn)和同伴(領(lǐng)域)飛行經(jīng)驗(yàn)進(jìn)行調(diào)整。

假設(shè)第i個(gè)粒子表示為Xi=(xi1,xi2,xi3,…,xiD)，第i個(gè)粒子的第d維(1≤d≤D)在第j次迭代過程中速度根據(jù)下式變化：

Vid(j)=wVid(j-1)+c1r1(pid-xid(j-1))+c2r2(pgd-xid(j-1))

(1)

式中，wVid(j-1)為慣性部分，w為慣性權(quán)重；Vid為第i個(gè)粒子第d維的速度分量；c1r1(pid-xid(j-1))為認(rèn)知項(xiàng)[3]，c2r2(pgd-xid(j-1))為社會(huì)項(xiàng)[4]，c1、c2分別為加速常數(shù);r1、r2分別為區(qū)間(0,1)中的隨機(jī)值；pid為第i個(gè)粒子所經(jīng)過的最好位置第d維位置分量；xid為第i個(gè)粒子第d維當(dāng)前位置分量；pgd為粒子群群體中所有經(jīng)歷過的最好位置第d維位置分量。

根據(jù)式(1)求得第j次迭代第i個(gè)粒子的最新速度Vi后，其最新位置根據(jù)下式更新：

xid(j)=Vid(j)+xid(j-1)

(2)

式中，xid(j)為第i個(gè)粒子在第j次迭代后的第d維值。

式(1)的慣性部分反映的是粒子的維持先前速度的趨勢，最初將w固定取值為1.0[1-2]，但這種做法很難使算法快速收斂，后來Bandura A[4]將w由0.9逐步降為0.4，而Shi等[5]采用隨機(jī)近似理論分析PSO的動(dòng)態(tài)行為，提出了將w隨更新代數(shù)遞減至0的方法。上述方法使得w隨著迭代次數(shù)的增加逐步變小，從而使該算法在早期有較高的搜索解空間的能力，在后期可以快速收斂。

式(1)的認(rèn)知項(xiàng)反映了粒子在飛行過程中對“經(jīng)歷”過的最好位置的記憶，而式(1)的社會(huì)項(xiàng)反映了粒子與粒子之間的知識(shí)共享群體最優(yōu)記憶，也代表粒子向最優(yōu)位置逼迫的趨勢。最初將c1和c2固定

取值為2.0，但Ratnaweera等[6]提出c1隨著迭代次數(shù)的增加，其值可以從2.5線性地減至0.5，以使單個(gè)粒子逐步向最優(yōu)位置靠近，而c2隨著迭代次數(shù)從0.5線性地增至2.5，以使群體逐步逼近最優(yōu)。

2 管網(wǎng)拓樸優(yōu)化數(shù)學(xué)模型

以注水井與配水間的隸屬關(guān)系及配水間的位置作為優(yōu)化設(shè)計(jì)變量，以注水系統(tǒng)管網(wǎng)管線長度最小為目標(biāo)函數(shù)，則樹狀注水系統(tǒng)管網(wǎng)拓?fù)鋬?yōu)化的數(shù)學(xué)模型為[7-8]：

(3)

式中，f為管線長度；Nw為注水井?dāng)?shù)量；Np為配水間數(shù)量；δij表示第i口井與第j個(gè)配水間的連接關(guān)系，其值為1或0，0表示沒有連接，1表示有連接；xi、yi為第i口井位置坐標(biāo)；Dxj、Dyj為第j個(gè)配水間的坐標(biāo)位置。

由式(3)可以看出，要使各注水井到配水間總的管線長度最短，必須滿足下列條件[9]：

Nw∈[Dwmin，Dwmax]

(4)

式中，Dwmin、Dwmax分別為每個(gè)配水間連接各注水井的最小值和最大值。

所以，樹狀注水管網(wǎng)拓樸優(yōu)化設(shè)計(jì)的實(shí)質(zhì)就是尋找最佳連接方案的過程。

3 算法求解

3.1編碼

編碼前，首先對所有的注水井與配水間編號，分別從編號1開始逐漸增加，使注水井與配水間分別都有一個(gè)唯一且連接的序列號，設(shè)最大配水間編號為dp max，最大注水井編號為dz max。然后，再把粒子群的維度設(shè)為dp max，并令第i個(gè)粒子Xi=(xi1,xi2,xi3,…,xdp max)中的xij表示第j(1≤j≤dp max)個(gè)配水間，連接的是第xij(1≤xij≤dz max)號井。

3.2產(chǎn)生初始粒子

對每一維xij的產(chǎn)生，都可以采用隨機(jī)數(shù)在[1,dz max]中選取，對最后的Xi只需要判斷基本可行性，即所產(chǎn)生的Xi中的連接到相同配水間的數(shù)量Nw∈[Dwmin，Dwmax]即可，如不滿足，可以采用隨機(jī)調(diào)整修正或丟棄重新產(chǎn)生[8]。

3.3確定適應(yīng)函數(shù)

管網(wǎng)整體優(yōu)化的過程是使目標(biāo)函數(shù)值最小，屬最小化優(yōu)化，應(yīng)加以調(diào)整，可采用歸一化方法：

(5)

式中，F(xiàn)i為適應(yīng)值;fmin為歷史最小目標(biāo)函數(shù)值；fmax為歷史最大目標(biāo)函數(shù)值；fi為第i個(gè)粒子的目標(biāo)函數(shù)值。

變換后，最大適應(yīng)值與最小目標(biāo)函數(shù)值相對應(yīng)，最小適應(yīng)值與最大目標(biāo)函數(shù)相對應(yīng)，并且在fi較小時(shí)，適應(yīng)值fi差距較大，這樣有利于選擇優(yōu)勢粒子。

3.4算法步驟

使用粒子群優(yōu)化算法進(jìn)行樹狀注水管網(wǎng)拓樸優(yōu)化的算法步驟如下：①隨機(jī)產(chǎn)生一定符合要求的粒子群，并計(jì)算各粒子的適應(yīng)值；②計(jì)算各粒子適應(yīng)值，并依據(jù)式(1)與式(2)重新計(jì)算粒子群的新位置；③ 檢測新的粒子是否滿足配水間數(shù)量的限制，如不滿足，做隨機(jī)調(diào)整或丟棄后重新生成新的粒子補(bǔ)充；④如果已經(jīng)達(dá)到大最迭代次數(shù)，輸出最大適應(yīng)值所對應(yīng)粒子，即為解，算法結(jié)束，否則轉(zhuǎn)向步驟②。

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

以某油田采油廠注水區(qū)塊為例，該區(qū)塊共有注水井41個(gè)，配水間12個(gè)(見圖1)。根據(jù)粒子群優(yōu)化算法，使用VC++工具編寫注水系統(tǒng)的軟件，得到優(yōu)化后的注水管網(wǎng)(見圖2)。原有注水管網(wǎng)管線總長為30.07km，使用粒子群優(yōu)化算法后，管線總長減少為28.01km，降低幅度為6.85%，可見采用該優(yōu)化方案的效果十分顯著。

圖1 使用粒子群算法優(yōu)化前的注水管網(wǎng) 圖2 使用粒子群算法優(yōu)化后的注水管網(wǎng)

5 結(jié) 語

把注水井與配水間的匹配位置關(guān)系做為粒子優(yōu)化變量，以最短管網(wǎng)線為目標(biāo)函數(shù)，同時(shí)結(jié)合配水間的上下限約束條件建立了樹狀管網(wǎng)粒子群拓樸優(yōu)化數(shù)學(xué)模型。根據(jù)目標(biāo)函數(shù)特點(diǎn)，對目標(biāo)函數(shù)做了適當(dāng)變換，以最大適應(yīng)值為目標(biāo)進(jìn)行求解，最后使用VC++為工具，對實(shí)際的油田注水管網(wǎng)進(jìn)行優(yōu)化求解，并與現(xiàn)在管網(wǎng)進(jìn)行比較。結(jié)果表明，使用粒子群優(yōu)化算法可以有效優(yōu)化現(xiàn)有注水管網(wǎng)拓樸結(jié)構(gòu)，節(jié)省管網(wǎng)建設(shè)投資。

[1]Kennedy J,Eberhart R C. Particle swarm optimization[A].Proc IEEE Int Conf on Neural Networks[C].Perth, 1995:1942-1948.

[2]Eberhart R C, Kennedy J A. A new optimizer using particle swarm theory[A]. Proc The Sixth Int Symposium on Micro Machine and Human Science[C].Nagoya, 1995:39-43.

[3]Thorndike E L. Animal I ntellig ence: Emp ir ica l Stud ies[M] . New York: MacMillan, 1991.

[4] Bandura A. Social Founda tions of Thought and Action: A Social Cognitive Theory [M]. New Jersey: Prentice-Hall,1986.

[5]Shi Y，Eberhart R C, Empirical study of particle swarm optimization [A]. In Proc IEEE Congr Evol Comput[C]. Washington, 1998:1945-1950.

[6]Ratnaweera A, Halgamuge S K,Watson H C. Self-Organizing Hierarchical Particle Swarm Optimizer with Time-Varying Acceleration Coefficients [J]. IEEE Transactions on Evolutionary Computation, 2004,8(3):240-255.

[7] 劉楊.油田注水系統(tǒng)智能優(yōu)化方法研究[D].大慶:大慶石油學(xué)院,2006.

[8] 康正凌,袁宗明.樹枝狀天然氣管網(wǎng)優(yōu)化設(shè)計(jì)[J].天然氣工業(yè),2001,21(3):76-78.

[9]劉揚(yáng).石油工程優(yōu)化設(shè)計(jì)理論及方法[M].北京:石油工業(yè)出版社,1994.

[編輯] 李啟棟

10.3969/j.issn.1673-1409.2011.09.024

TP301.6

A

1673-1409(2011)09-0076-03