譜聚類在給水管網(wǎng)分區(qū)優(yōu)化中的應(yīng)用

劉俊　周鵬

摘要：利用圖劃分技術(shù)和圖論算法實現(xiàn)給水管網(wǎng)分區(qū)。根據(jù)給水管網(wǎng)分析，確定分區(qū)數(shù)量，建立權(quán)重鄰接矩陣并計算圖拉普拉斯矩陣及其特征向量，通過多路圖劃分對隱藏在特征向量中的聚類信息進行數(shù)據(jù)挖掘，采用遺傳算法和K均值方法實現(xiàn)最佳節(jié)點聚類。利用PageRank和最短路徑算法確定水表和閥門位置，最終實現(xiàn)給水管網(wǎng)優(yōu)化分區(qū)。實際給水管網(wǎng)模型分區(qū)實例表明所提方法在給水管網(wǎng)分區(qū)的有效性。

關(guān)鍵詞：給水管網(wǎng)；分區(qū)；聚類；優(yōu)化

中圖分類號：TU991

文獻標(biāo)志碼：A

文章編號：1674-4764（2016）06-0142-06

給水管網(wǎng)分區(qū)是在系統(tǒng)性能影響最小的情況下通過安裝閥門、水表形成獨立供水區(qū)域，便于優(yōu)化調(diào)度、漏損控制等各方面的管理，以適應(yīng)信息化、智能化、精細化的要求。管網(wǎng)分區(qū)目的是獲得規(guī)模均等，壓力、水質(zhì)均衡的分區(qū)。由于管網(wǎng)的高度復(fù)雜性以及眾多技術(shù)要求和制約因素，使得分區(qū)這一問題面臨較大挑戰(zhàn)。

目前，管網(wǎng)分區(qū)優(yōu)化方法主要有圖論算法和復(fù)雜網(wǎng)絡(luò)聚類算法。圖論分區(qū)算法主要使用搜索算法獲得管網(wǎng)拓撲結(jié)構(gòu)。其中，廣度優(yōu)先搜索算法在DMA規(guī)模約束下，搜索與某一節(jié)點路徑最短的節(jié)點集，當(dāng)滿足設(shè)定規(guī)模時，搜索終止，則可得到滿足要求的分區(qū)。這類方法可獲得各種分區(qū)方案供決策者選定，或者通過模型分析獲得水力最優(yōu)方案。相比于廣度優(yōu)先搜索算法的局部搜索，深度優(yōu)先搜索算法可從整體上獲得給水管網(wǎng)樹狀結(jié)構(gòu)，并通過優(yōu)化算法獲得減壓閥最佳位置，進而實現(xiàn)分區(qū)，或者確定各水源供水范圍。另外，也可以最短路徑算法為基礎(chǔ)，通過壓力均衡性確定分，或者通過管道介數(shù)中心性選定閥門、水表位置，以實現(xiàn)分區(qū)。

在復(fù)雜網(wǎng)絡(luò)聚類中，同一聚類內(nèi)節(jié)點連接緊密，而不同聚類間節(jié)點連接相對稀疏，這與管網(wǎng)分區(qū)的內(nèi)在要求一致。相應(yīng)聚類算法包括計算機科學(xué)中的圖劃分和社會學(xué)中的社團發(fā)現(xiàn)。圖劃分將復(fù)雜網(wǎng)絡(luò)聚類轉(zhuǎn)換為優(yōu)化問題，如Nardo等人使用多層次遞歸二分法自動獲得規(guī)模均等的分區(qū)布局。社團發(fā)現(xiàn)則將分區(qū)問題轉(zhuǎn)換為模塊度等啟發(fā)式規(guī)則的設(shè)計問題，其中刁克功等在管網(wǎng)分區(qū)中首次引入社區(qū)發(fā)現(xiàn)貪心算法進行給水管網(wǎng)分區(qū)。Giustolisi等引入管道權(quán)重提出了給水管網(wǎng)設(shè)施模塊度，可以發(fā)現(xiàn)更小規(guī)模的結(jié)構(gòu)。另外，也有其他相似度的度量方式用于給水管網(wǎng)分區(qū)，如按照節(jié)點位置信息采用K-均值聚類，以此為基礎(chǔ)形成供水管網(wǎng)規(guī)劃方案，或者按照節(jié)點水壓波動相似性分區(qū)，確定最優(yōu)壓力監(jiān)測點。

筆者提出一種基于復(fù)雜網(wǎng)絡(luò)譜聚類和圖論算法的給水管網(wǎng)分區(qū)方法。目的是在盡量降低分區(qū)不利影響的前提下，根據(jù)給水管網(wǎng)拓撲結(jié)構(gòu)，利用數(shù)據(jù)挖掘發(fā)現(xiàn)隱含在其中的結(jié)構(gòu)聚類信息，確定節(jié)點聚類，繼而實現(xiàn)滿足要求的分區(qū)。

1.給水管網(wǎng)分區(qū)方法

所提出的分區(qū)流程主要包含3個部分：

1）數(shù)據(jù)輸入：管網(wǎng)分析與模擬，確定分區(qū)數(shù)量，建立權(quán)重矩陣。

2）實現(xiàn)分區(qū)：圖拉普拉斯矩陣求解，根據(jù)第二特征向量，采用多路圖劃分確定各分區(qū)內(nèi)節(jié)點聚類，即確定分區(qū)范圍。

3）確定閥門、水表位置：PageRank算法確定每個分區(qū)中心節(jié)點，水源到該節(jié)點的最短路徑中確定水表位置，其他分區(qū)間連接管道則為閥門位置。

1.1給水管網(wǎng)分區(qū)數(shù)量的確定

給水管網(wǎng)分區(qū)數(shù)量需要根據(jù)分區(qū)目的、系統(tǒng)規(guī)模、分區(qū)大小、成本等綜合確定。本方法旨在通過發(fā)現(xiàn)給水管網(wǎng)內(nèi)在聚類結(jié)構(gòu)，實現(xiàn)分區(qū)設(shè)計，因此，在獲得指定數(shù)量的分區(qū)時，每個分區(qū)的規(guī)模不是嚴格相同。

1.2規(guī)范化拉普拉斯矩陣

譜平分法利用第二小特征值對應(yīng)的特征向量實現(xiàn)兩個分區(qū)的優(yōu)化劃分。如果需要得到多個分區(qū)，則需要對子分區(qū)重復(fù)該方法。為了提高分區(qū)效率，采用NJW多路譜算法，即根據(jù)多個第二最小特征向量，通過聚類算法直接獲得指定數(shù)量的分區(qū)。矩陣E的最大特征值為1，其他特征值均小于1。對于社團結(jié)構(gòu)比較明顯的管網(wǎng)，有些特征值接近于1，其對應(yīng)的第二特征向量中，同一社團內(nèi)部節(jié)點的值接近。對于社團結(jié)構(gòu)不明顯的一般給水管網(wǎng)，少量第二特征向量也可獲得良好分區(qū)。第二特征向量確定方法如下：

K均值算法取決于初始化聚類中心，是一種局部優(yōu)化算法。為了實現(xiàn)最優(yōu)化分區(qū)，采用遺傳算法優(yōu)化聚類中心。種群中每個個體對應(yīng)于各個聚類中心，以SSE最小化為目標(biāo)函數(shù)，通過線性排序確定個體適應(yīng)度，交叉、變異逐漸產(chǎn)生新的子代。為了提高搜索速度，在每次得到聚類劃分后，用校正后的聚類中心代替?zhèn)€體中原來的聚類中心。

1.4確定閥門、水表位置

在確定分區(qū)范圍后，接下來要確定水表和閥門的位置。在每個分區(qū)中均存在中心節(jié)點，一般是拓撲連接緊密的節(jié)點，即度較高的節(jié)點，這意味著該節(jié)點是流量的樞紐節(jié)點，則水源到該樞紐節(jié)點的最短供水路徑應(yīng)該是該分區(qū)的主要供水路徑，主要供水路徑必經(jīng)過分區(qū)間連接管道，則這個管道即為進水點，也就是水表位置，其他連接管道則為閥門位

1.6分區(qū)間運行關(guān)系

DMA按進水點數(shù)量和流量關(guān)系可分為單進口、多進口和串聯(lián)DMA，如圖1所示，其中，DMA2和DMA3為單進口類型，DMA4為多進口，上述3個分區(qū)共同特征是均只有流量流入而無流出。而DMAl除滿足本區(qū)用水外，還需向DMA2供水，因此，DMAl為串聯(lián)類型，有流量的流人和流出。目前的分區(qū)方法為了方便管理并減少計量誤差，一般DMA設(shè)計優(yōu)先選擇單進口、無流出類型。但DMA設(shè)計影響因素多、情況復(fù)雜，有時難以滿足上述原則，同時單進口DMA也存在系統(tǒng)彈性能力降低、難以滿足消防流量要求和末端水質(zhì)下降等問題，因此，根據(jù)具體情況也可選擇多進口DMA，但進水口數(shù)量不宜太多，否則進水點處減壓閥會引起壓力波動可采用主、副進水口設(shè)計，即在正常供水時只開啟主進水口，而當(dāng)高峰用水或消防時，可開啟副進水口。當(dāng)遠離干管的DMA其供水路徑需要經(jīng)過其他分區(qū)時，或者管理、技術(shù)等多因素綜合比較后串聯(lián)DMA具有優(yōu)勢時，也可選擇串聯(lián)類型DMA。

2.分區(qū)實例

以圖2所示環(huán)狀給水管網(wǎng)為例驗證所提分區(qū)方法的有效性。該給水管網(wǎng)含有1個水源，36個用水點，58根管道，具有復(fù)雜的環(huán)狀結(jié)構(gòu)。設(shè)定分區(qū)數(shù)量為4個。

4個分區(qū)的方案如圖2所示。每個分區(qū)的規(guī)模可見表1，從表中可知每個分區(qū)的規(guī)模與平均規(guī)模有一定偏差。如前所述，如果分區(qū)時強調(diào)每個分區(qū)應(yīng)含有相同的規(guī)模（用水量），則必將破壞給水管網(wǎng)內(nèi)部的聚類結(jié)構(gòu)。而依據(jù)聚類算法，屬性相似的節(jié)點組成一個分區(qū)，這可從整體上降低分區(qū)對給水管網(wǎng)結(jié)構(gòu)的影響。分區(qū)后的壓力分析見表2。由表2可知，每個分區(qū)壓力范圍相似，平均壓力有微小差別。壓力均衡性較好，PU值均低于平均壓力的10%，說明分區(qū)后管網(wǎng)性能沒有明顯降低，對系統(tǒng)性能的影響較小。

K均值算法是局部優(yōu)化方法，遺傳算法是一種全局優(yōu)化方法，二者結(jié)合將增加收斂速度，由圖3可知，經(jīng)過25次進化后種群即實現(xiàn)收斂。另外，每一代的最佳個體都能搜索到最佳聚類。

在確定分區(qū)邊界后，需要確定每個分區(qū)的進水點和設(shè)置閥門的管道。為此根據(jù)PageRank算法分析每個節(jié)點的中心性，給水管網(wǎng)末端節(jié)點中心性較

利用最短路徑算法可得每個分區(qū)水表位置，其他分區(qū)邊界管道則為閥門位置。由圖2分區(qū)結(jié)構(gòu)可知，基于譜聚類的分區(qū)方法將干管節(jié)點也納入分區(qū)，因此，DMAl和DMA4具有流量流人流出，為串聯(lián)分區(qū)，DMA2和DMA3則為單進口分區(qū)。串聯(lián)分區(qū)結(jié)構(gòu)的引人，使得DMAl和DMA4內(nèi)節(jié)點分區(qū)前后水流路徑不變，分區(qū)對這些節(jié)點沒有影響。

3.結(jié)論

提出了基于譜聚類的給水管網(wǎng)分區(qū)方法，同時可確定每個分區(qū)的進水點和閥門位置，并以一個真實給水管網(wǎng)說明本分區(qū)方法的可行性。本方法將給水管網(wǎng)拓撲結(jié)構(gòu)通過譜方法映射到高維向量空問，并依據(jù)聚類將拓撲相似節(jié)點劃分到一個分區(qū)，遺傳算法與K均值算法相結(jié)合提高了算法效率，同時，本方法具有較強的健壯性，可根據(jù)要求實現(xiàn)不同規(guī)模的分區(qū)設(shè)計。

本文中不僅確定了分區(qū)邊界，也給出了進水點位置，下一步工作可在此基礎(chǔ)上通過優(yōu)化進水點減壓閥，將各分區(qū)內(nèi)壓力控制在合理范圍，從而在整體上降低漏損。