基于聚類遺傳算法的管網(wǎng)優(yōu)化設(shè)計

孫 濤 徐明海

1中國石油大學(xué)（華東）儲運(yùn)與建筑工程學(xué)院

2中國石油大學(xué)勝利學(xué)院

基于聚類遺傳算法的管網(wǎng)優(yōu)化設(shè)計

孫 濤1；2徐明海1

1中國石油大學(xué)（華東）儲運(yùn)與建筑工程學(xué)院

2中國石油大學(xué)勝利學(xué)院

油田管網(wǎng)的拓?fù)淠Ｐ蛢?yōu)化是一個復(fù)雜的非線性優(yōu)化問題，根據(jù)模型特點(diǎn)可分解為兩個分別包含連續(xù)變量與離散變量的優(yōu)化問題。使用遺傳算法求解問題，將模型中的連續(xù)變量進(jìn)行編碼，形成個體，使用K-means算法更新個體并計算適應(yīng)度。通過實(shí)例計算，驗證了算法的收斂性與穩(wěn)定性，與結(jié)合分枝定界法的遺傳算法進(jìn)行對比，K-means算法提高了遺傳算法的收斂速度。

油田管網(wǎng)；優(yōu)化設(shè)計；遺傳算法；K-means算法；函數(shù)值

油氣集輸系統(tǒng)是油田地面工程投資中的重要部分，對其進(jìn)行優(yōu)化設(shè)計，可以減少投資和運(yùn)行費(fèi)用，有利于提高經(jīng)濟(jì)效益，減少油氣生產(chǎn)成本。目前國內(nèi)廣泛采用的集輸管網(wǎng)系統(tǒng)是多級集輸，即油井經(jīng)過各級中間站中轉(zhuǎn)，最后連接到聯(lián)合站。這一管網(wǎng)系統(tǒng)從數(shù)學(xué)上可以抽象成為一個有點(diǎn)集和邊集構(gòu)成的網(wǎng)絡(luò)系統(tǒng)，規(guī)劃設(shè)計的目的是確定節(jié)點(diǎn)的位置和各節(jié)點(diǎn)的連接關(guān)系等。本文主要研究油田地面管網(wǎng)中油井到中轉(zhuǎn)站之間管網(wǎng)的優(yōu)化設(shè)計。

油田地面管網(wǎng)的優(yōu)化設(shè)計由于其問題的復(fù)雜性和非線性，傳統(tǒng)的優(yōu)化方法遇到了極大困難，大多僅適用于某些特定的較簡單的管網(wǎng)。遺傳算法作為一種新興的全局優(yōu)化算法，已在油田管網(wǎng)優(yōu)化中得到了較廣泛的應(yīng)用研究，但這些研究大多是將遺傳算法應(yīng)用于管網(wǎng)設(shè)計的一部分，而其他部分仍采用傳統(tǒng)算法[1-4]。K-means算法是一種廣泛應(yīng)用的聚類算法，具有收斂速度快、算法簡單等特點(diǎn)，但受初值影響較大，一般只能達(dá)到局部最優(yōu)。而將遺傳算法與K-means算法結(jié)合可以獲得一種全局尋優(yōu)、收斂較快和與初值選擇無關(guān)的算法[5-7]。

管網(wǎng)優(yōu)化模型可以通過分解為兩個分別包含連續(xù)變量和離散變量的優(yōu)化問題，本文將模型中的連續(xù)變量進(jìn)行編碼，形成個體，利用K-means算法更新個體，確定個體適應(yīng)度，通過選擇和突變等遺傳操作，迭代選出最優(yōu)解。通過實(shí)例計算對比，驗證算法的有效性、收斂性與穩(wěn)定性。

1 管網(wǎng)的拓?fù)鋬?yōu)化模型

油田集輸管網(wǎng)設(shè)計中，油井的位置和數(shù)目是給定的。油井與中轉(zhuǎn)站的連接網(wǎng)絡(luò)一般為樹狀網(wǎng)絡(luò)，在中轉(zhuǎn)站數(shù)量n給定的前提下，確定每個中轉(zhuǎn)站的位置，同時將油井分為n個不同的集合，每個油井隸屬于一個中轉(zhuǎn)站，這種隸屬關(guān)系具有唯一性，規(guī)劃優(yōu)化設(shè)計的目標(biāo)是降低整體投資成本。整體投資成本為管網(wǎng)的鋼管投資，其數(shù)學(xué)模型為

其中dij=如果第i油井隸屬于第j中轉(zhuǎn)站否則

i=1，2，…，N，j=1，2，…，n

式中dij為第i油井與第j個中轉(zhuǎn)站間的距離；N為油井的數(shù)量；n為中轉(zhuǎn)站的數(shù)量；(xi,yi)是第i油井的位置坐標(biāo)；(Xj,Yj)是第j個中轉(zhuǎn)站的位置坐標(biāo)；V是中轉(zhuǎn)站位置坐標(biāo)向量；cij為第i油井與第j個中轉(zhuǎn)站間管網(wǎng)造價。

在模型中，約束（1-1）表明隸屬關(guān)系的唯一性；約束（1-2）為井?dāng)?shù)約束，即各中轉(zhuǎn)站連接最大井?dāng)?shù)為M；約束（1-3）為幾何約束，D為中轉(zhuǎn)站位置向量V的可行域。

2 遺傳算法與K-means算法

在管網(wǎng)模型中，中轉(zhuǎn)站的位置變量(Xj,Yj)為連續(xù)變量，而油井與中轉(zhuǎn)站的隸屬關(guān)系cij為0-1變量，因此該模型中既包含連續(xù)變量，也包含離散變量，對于規(guī)模較大的油田模型，使用傳統(tǒng)的算法進(jìn)行求解，會存在不同程度的“維數(shù)災(zāi)難”，很難取得最優(yōu)解。而遺傳算法由于其具有全局尋優(yōu)和并行特性，十分適合求解此類復(fù)雜的非線性問題。

遺傳算法是利用編碼和進(jìn)化機(jī)制，從一組初始解（稱為初始種群）開始，通過不斷的群體迭代實(shí)現(xiàn)對復(fù)雜問題的求解，其基本步驟為：①將問題的可行解進(jìn)行編碼，將其變?yōu)槿旧w或個體；②隨機(jī)產(chǎn)生多個個體，形成種群；③計算種群中個體的適應(yīng)度，并以此選擇個體進(jìn)入交叉操作；④對種群進(jìn)行交叉操作；⑤對交叉后的種群進(jìn)行變異操作；⑥判斷是否符合算法終止條件，如果符合，將最終的染色體通過解碼得到最優(yōu)解，否則重復(fù)步驟③、④、⑤。

K-means算法是一種被廣泛應(yīng)用的動態(tài)聚類方法，其思想是將給定的若干點(diǎn)視為聚點(diǎn)，按照距離遠(yuǎn)近將樣本進(jìn)行分類，得到初始分類后，求得各個類別的重心作為新的聚點(diǎn)，然后更新分類。如此迭代更新，直到滿足終止條件。

本文將管網(wǎng)模型中的連續(xù)變量空間作為遺傳算法的解空間進(jìn)行編碼，形成個體，當(dāng)個體確定后，中轉(zhuǎn)站的位置就確定了。將中轉(zhuǎn)站視為初始聚點(diǎn)，將油井視為待分類樣本，應(yīng)用K-means算法進(jìn)行聚類，求解出對應(yīng)的離散變量，從而對個體進(jìn)行更新并確定個體適應(yīng)度，這種算法下面稱之為K-means遺傳算法。

3 算法的實(shí)現(xiàn)過程

3.1 編碼

由于中轉(zhuǎn)站位置變量為連續(xù)變量，因此采用實(shí)數(shù)編碼，將中轉(zhuǎn)站的坐標(biāo)按順序排成一個向量，這個向量作為個體的編碼，即第k個體為：為第k個體中第i中轉(zhuǎn)站的位置坐標(biāo)，i=1,2,…,n。

3.2 初始化種群

在可行域D隨機(jī)產(chǎn)生n個位置坐標(biāo)，構(gòu)成1個個體，然后重復(fù)這一過程，產(chǎn)生l個個體，組成初始種群G0=(g1,g2,…,gl)。

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

對于染色體gk，以n個位置坐標(biāo)為初始聚點(diǎn)，按距離進(jìn)行聚類，形成n個聚類集合，然后利用重心法產(chǎn)生新的聚點(diǎn)從而進(jìn)行迭代，求得最終位置坐標(biāo)以及相應(yīng)的聚類，以最終位置坐標(biāo)更新個體gk，并計算相應(yīng)的距離和，從而產(chǎn)生適應(yīng)度函數(shù)。步驟如下：

（1）以gk的位置坐標(biāo)為初始聚點(diǎn)，即i=1，2，…，n，形成初始聚點(diǎn)集合。對每一口油井到聚點(diǎn)

（5）比較F1與F0，若F1＜F0，則令L0=L1，重復(fù)上述過程，若F1≥F0，則算法終止，以L0的坐標(biāo)作為個體gk的改進(jìn)，同時其費(fèi)用總和為進(jìn)而得到表征個體性能的適應(yīng)度函數(shù)。

3.4 選擇

選擇操作是從當(dāng)前種群中以一定概率選取個體用作父本去繁殖后代，個體被選中的概率與適應(yīng)度值有關(guān)，本文采用輪盤賭選擇方法，即基于適應(yīng)度比例的選擇策略。

3.5 交叉

從種群中選擇兩個父本個體，通過兩交換組合產(chǎn)生兩個新個體，將好的基因保存下去，這是遺傳算法的主要步驟。由于模型中個體采用的編碼方式是實(shí)數(shù)編碼，本文采用實(shí)數(shù)交叉法[8]進(jìn)行個體的交叉操作。

3.6 變異

變異操作是為了維持種群的多樣性，避免算法陷入局部搜索，以及在生物界基因變異發(fā)生的概率，因此，變異概率一般取值很小，本文中變異采用均勻變異，即隨機(jī)選取個體的一個基因，然后用在可行域內(nèi)區(qū)間中均勻分布的一個隨機(jī)數(shù)代替。

3.7 保優(yōu)策略

在算法中，為了保證好的基因能夠獲得遺傳，每次迭代中都會保存最優(yōu)個體，在下次迭代時用來取代適應(yīng)度最差的個體。

3.8 終止進(jìn)化條件

遺傳算法是通過反復(fù)迭代的方法接近全局最優(yōu)解，由于事先無法知道全局最優(yōu)解的信息，因此需要預(yù)先設(shè)定終止條件。本文算法終止條件為設(shè)定最大循環(huán)代數(shù)，當(dāng)?shù)_(dá)到最大循環(huán)代數(shù)時算法終止。

4 算例分析

利用K-means遺傳算法，編制MATLAB程序[8]，針對國內(nèi)某油田有88口油井的區(qū)塊，進(jìn)行了優(yōu)化設(shè)計并與實(shí)際管網(wǎng)進(jìn)行了對比。實(shí)際管網(wǎng)有12個計量站，管線總長度為482.059 0 km。為了對比，優(yōu)化設(shè)計也是12個計量站。故優(yōu)化設(shè)計的任務(wù)為確定12個計量站的位置和各個站所連接的油井及數(shù)目，設(shè)計中規(guī)定每個計量站最多下轄8口井。

4.1 優(yōu)化設(shè)計結(jié)果

使用K-means遺傳算法程序運(yùn)算，取初始群體規(guī)模為40，交叉概率取75%，變異概率取5%，進(jìn)化500代，原管網(wǎng)規(guī)劃設(shè)計、K-means遺傳算法優(yōu)化設(shè)計見圖1、圖2。遺傳算法優(yōu)化計算的管線總長度為420.263 2 km，在單位管線造價相同的情況下，與原管線相比，管線總投資減少12.82%，優(yōu)化效果明顯。

圖1 原管網(wǎng)規(guī)劃設(shè)計

4.2 算法穩(wěn)定性與收斂性分析

目標(biāo)函數(shù)值隨進(jìn)化代數(shù)的變化曲線見圖3。從圖3可知，由于K-means算法對個體進(jìn)行了優(yōu)化，因此進(jìn)化過程能夠較快地收斂，進(jìn)化200次就可接近達(dá)到最優(yōu)目標(biāo)函數(shù)值，而且從目標(biāo)函數(shù)值變化曲線可知，進(jìn)化300代后進(jìn)化過程趨于穩(wěn)定。為進(jìn)一步檢驗算法的穩(wěn)定性，在群體規(guī)模、交叉概率、變異概率及進(jìn)化代數(shù)相同的條件下，隨機(jī)產(chǎn)生不同的初始種群進(jìn)行比較，結(jié)果見表1。從表1結(jié)果可知，算法運(yùn)行5次，進(jìn)化300代后最優(yōu)函數(shù)值基本一致，說明算法穩(wěn)定性好，收斂速度快。

圖2 K-means遺傳算法優(yōu)化設(shè)計

圖3 K-means遺傳算法

表1 算法最優(yōu)目標(biāo)函數(shù)值變化

4.3 算法的比較分析

由于在中轉(zhuǎn)站位置坐標(biāo)一定的情況下，模型簡化為一個只含有0-1變量的線性規(guī)劃問題，可以采用傳統(tǒng)方法求解。為了進(jìn)行在相同計算條件下的算法比較，選擇分枝定界法進(jìn)行遺傳算法的適應(yīng)度函數(shù)運(yùn)算，使用分枝定界法的遺傳算法（下稱分枝定界遺傳算法），目標(biāo)函數(shù)值隨進(jìn)化代數(shù)的變化曲線見圖4，與K-means遺傳算法比較結(jié)果見表2。從圖4可知，使用分枝定界遺傳算法在進(jìn)化1 000代后才能趨于穩(wěn)定。與K-means遺傳算法相比，分枝定界遺傳算法需要進(jìn)化1 500次才能得到相近的計算結(jié)果。而且在相同MATLAB環(huán)境下，分枝定界遺傳算法進(jìn)化一次的平均時間約為20 s，而K-means遺傳算法僅為0.5 s，在計算時間上，K-means遺傳算法要遠(yuǎn)遠(yuǎn)優(yōu)于分枝定界遺傳算法。

圖4 使用分枝定界法的遺傳算法

表2 兩種遺傳算法結(jié)果對比

5 結(jié)論

將K-means算法融入遺傳算法進(jìn)行油田管網(wǎng)的拓?fù)鋬?yōu)化設(shè)計，其具有算法簡單，易于實(shí)現(xiàn)及適應(yīng)性強(qiáng)等優(yōu)點(diǎn)，不過受初值影響較大；將K-means算法融入遺傳算法中，既能夠充分發(fā)揮K-means算法的優(yōu)勢，又避免了初值對結(jié)果的影響，能夠?qū)崿F(xiàn)全局尋優(yōu)。通過實(shí)例計算，驗證了算法的收斂性與穩(wěn)定性，與人工規(guī)劃結(jié)果對比，能節(jié)省10%左右投資；與結(jié)合分枝定界法的遺傳算法進(jìn)行對比，K-means算法提高了算法的收斂速度。

[1]劉揚(yáng)，魏立新，李長林，等．油氣集輸系統(tǒng)拓?fù)洳季謨?yōu)化的混合遺傳算法[J]．油氣儲運(yùn)，2003，22（6）：33-36.

[2]劉揚(yáng)，鞠志忠，鮑云波．一類多級星式網(wǎng)絡(luò)的拓?fù)鋬?yōu)化設(shè)計方法[J]．大慶石油學(xué)院學(xué)報，2009．4，33（2）：68-73.

[3]楊建軍，劉揚(yáng)，戰(zhàn)紅．基于混合遺傳算法的樹狀注水管網(wǎng)拓?fù)鋬?yōu)化[J]．石油學(xué)報，2006，27（1）：106-110.

[4]楊建軍，戰(zhàn)紅，丁玉成．基于改進(jìn)遺傳算法和圈的環(huán)狀管網(wǎng)優(yōu)化優(yōu)化[J]．油氣田地面工程，2010，29（4）：38-40.

[5]Babu G P，Murty N M．A near-optimal initial seed selection in K-means algorithm using a genetic algorithm[J]．Pattern Recognition Letters，1993，14（10）：763-769.

[6]Krishna K，Murty N M．Genetic K-means algorithm[J]．IEEE Transactions on Systems，Man and Cybernetics，1999，29（3）：433-439.

[7]Ujjwal Maulik，Sanghamitra Bandyopadhyay．Genetic algorithmbased clustering technique[J]．Pattern Recognition，2000（33）：1 455-1 465.

[8]史峰，王輝，郁磊，等．MATLAB智能算法30個案例分析[M]．北京：北京航空航天大學(xué)出版社，2011：17-26.

（欄目主持 張秀麗）

10.3969/j.issn.1006-6896.2015.10.019

孫濤：中國石油大學(xué)（華東）儲運(yùn)與建筑工程學(xué)院在讀博士生，中國石油大學(xué)勝利學(xué)院講師，主要從事系統(tǒng)工程優(yōu)化及優(yōu)化算法研究。

2015-05-22

基金論文：國家自然科學(xué)基金51276199。

15615065776、55757910@qq.com