基于聚類遺傳算法的管網優化設計

孫 濤 徐明海

1中國石油大學（華東）儲運與建筑工程學院

2中國石油大學勝利學院

基于聚類遺傳算法的管網優化設計

孫 濤1；2徐明海1

1中國石油大學（華東）儲運與建筑工程學院

2中國石油大學勝利學院

油田管網的拓撲模型優化是一個復雜的非線性優化問題，根據模型特點可分解為兩個分別包含連續變量與離散變量的優化問題。使用遺傳算法求解問題，將模型中的連續變量進行編碼，形成個體，使用K-means算法更新個體并計算適應度。通過實例計算，驗證了算法的收斂性與穩定性，與結合分枝定界法的遺傳算法進行對比，K-means算法提高了遺傳算法的收斂速度。

油田管網；優化設計；遺傳算法；K-means算法；函數值

油氣集輸系統是油田地面工程投資中的重要部分，對其進行優化設計，可以減少投資和運行費用，有利于提高經濟效益，減少油氣生產成本。目前國內廣泛采用的集輸管網系統是多級集輸，即油井經過各級中間站中轉，最后連接到聯合站。這一管網系統從數學上可以抽象成為一個有點集和邊集構成的網絡系統，規劃設計的目的是確定節點的位置和各節點的連接關系等。本文主要研究油田地面管網中油井到中轉站之間管網的優化設計。

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

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

1 管網的拓撲優化模型

油田集輸管網設計中，油井的位置和數目是給定的。油井與中轉站的連接網絡一般為樹狀網絡，在中轉站數量n給定的前提下，確定每個中轉站的位置，同時將油井分為n個不同的集合，每個油井隸屬于一個中轉站，這種隸屬關系具有唯一性，規劃優化設計的目標是降低整體投資成本。整體投資成本為管網的鋼管投資，其數學模型為

其中dij=如果第i油井隸屬于第j中轉站否則

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

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

在模型中，約束（1-1）表明隸屬關系的唯一性；約束（1-2）為井數約束，即各中轉站連接最大井數為M；約束（1-3）為幾何約束，D為中轉站位置向量V的可行域。

2 遺傳算法與K-means算法

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

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

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

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

3 算法的實現過程

3.1 編碼

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

3.2 初始化種群

在可行域D隨機產生n個位置坐標，構成1個個體，然后重復這一過程，產生l個個體，組成初始種群G0=(g1,g2,…,gl)。

3.3 確定適應度函數

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

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

（5）比較F1與F0，若F1＜F0，則令L0=L1，重復上述過程，若F1≥F0，則算法終止，以L0的坐標作為個體gk的改進，同時其費用總和為進而得到表征個體性能的適應度函數。

3.4 選擇

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

3.5 交叉

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

3.6 變異

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

3.7 保優策略

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

3.8 終止進化條件

遺傳算法是通過反復迭代的方法接近全局最優解，由于事先無法知道全局最優解的信息，因此需要預先設定終止條件。本文算法終止條件為設定最大循環代數，當迭代達到最大循環代數時算法終止。

4 算例分析

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

4.1 優化設計結果

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

圖1 原管網規劃設計

4.2 算法穩定性與收斂性分析

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

圖2 K-means遺傳算法優化設計

圖3 K-means遺傳算法

表1 算法最優目標函數值變化

4.3 算法的比較分析

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

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

表2 兩種遺傳算法結果對比

5 結論

將K-means算法融入遺傳算法進行油田管網的拓撲優化設計，其具有算法簡單，易于實現及適應性強等優點，不過受初值影響較大；將K-means算法融入遺傳算法中，既能夠充分發揮K-means算法的優勢，又避免了初值對結果的影響，能夠實現全局尋優。通過實例計算，驗證了算法的收斂性與穩定性，與人工規劃結果對比，能節省10%左右投資；與結合分枝定界法的遺傳算法進行對比，K-means算法提高了算法的收斂速度。

[1]劉揚，魏立新，李長林，等．油氣集輸系統拓撲布局優化的混合遺傳算法[J]．油氣儲運，2003，22（6）：33-36.

[2]劉揚，鞠志忠，鮑云波．一類多級星式網絡的拓撲優化設計方法[J]．大慶石油學院學報，2009．4，33（2）：68-73.

[3]楊建軍，劉揚，戰紅．基于混合遺傳算法的樹狀注水管網拓撲優化[J]．石油學報，2006，27（1）：106-110.

[4]楊建軍，戰紅，丁玉成．基于改進遺傳算法和圈的環狀管網優化優化[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]．北京：北京航空航天大學出版社，2011：17-26.

（欄目主持 張秀麗）

10.3969/j.issn.1006-6896.2015.10.019

孫濤：中國石油大學（華東）儲運與建筑工程學院在讀博士生，中國石油大學勝利學院講師，主要從事系統工程優化及優化算法研究。

2015-05-22

基金論文：國家自然科學基金51276199。

15615065776、55757910@qq.com