基于蟻群優(yōu)化K-medoids的變電站特性聚類研究

劉建華 孟 穎 譚 智

（1.長沙理工大學(xué)電氣與信息工程學(xué)院，長沙 410114；2.長沙理工大學(xué)計算機與通信工程學(xué)院，長沙 410114）

眾多文獻(xiàn)研究表明負(fù)荷特性對于電力系統(tǒng)運行，特別是電力系統(tǒng)的動態(tài)行為有很大的影響[1]，電力負(fù)荷模型準(zhǔn)確與否直接影響到電力系統(tǒng)仿真結(jié)果的準(zhǔn)確性[2-3]。建立精確的負(fù)荷模型用于電力系統(tǒng)的規(guī)劃、設(shè)計、運行和研究越來越成為電力系統(tǒng)工程實際和學(xué)術(shù)研究的基本需要[4]。但是由于負(fù)荷自身的特殊性，建立精確的電力系統(tǒng)負(fù)荷模型非常困難。

隨著對負(fù)荷建模研究的逐漸深入，負(fù)荷特性的分類與綜合問題正在受到重視。電力系統(tǒng)負(fù)荷變化的規(guī)律性使負(fù)荷數(shù)據(jù)呈現(xiàn)出可分類的特點[5-6]。文獻(xiàn)[7]中提出了基于改進(jìn)K均值(K-Means)的負(fù)荷聚類算法對電網(wǎng)進(jìn)行仿真分析。文獻(xiàn)[8]中提出了模糊等價關(guān)系和模糊C均值(Fuzzy C Means，F(xiàn)CM)兩種負(fù)荷聚類方法。文獻(xiàn)[9]提出了基于自適應(yīng)FCM聚類的電力負(fù)荷動特性分類方法。文獻(xiàn)[10]提出了基于數(shù)據(jù)挖掘的多層次細(xì)節(jié)分解負(fù)荷聚類算法。

本文提出了一種蟻群優(yōu)化 K-medoids綜合算法（下文簡稱綜合算法），并將其應(yīng)用于變電站負(fù)荷特性聚類中，通過K-medoids算法對蟻群的歷史最優(yōu)位置進(jìn)行聚類分析，將此位置代替K-medoids算法的參考點，作為新的聚類中心，數(shù)據(jù)可以自適應(yīng)的加入到適合它的聚類當(dāng)中。

1 基本原理

1.1 蟻群算法

蟻群算法是Colorni和Dorigo等人在90年代初期提出的一種新型智能模擬仿生優(yōu)化算法[11]。蟻群算法由于具有正反饋、分布式計算以及貪婪啟發(fā)式搜索等特點，成為人工智能領(lǐng)域的一個研究熱點。目前對蟻群算法的研究已經(jīng)滲入到多種不同的應(yīng)用領(lǐng)域，如旅行商問題（TSP）、二次分配問題（QAP）、任務(wù)調(diào)度問題（JSP）等。

蟻群算法的基本原理是[12]，螞蟻在運動過程中會釋放一種信息素（pheromone）的物質(zhì)，螞蟻個體之間是通過該信息素進(jìn)行運動方向的信息傳遞的，即螞蟻不僅在所經(jīng)過的路徑上沉積了該種物質(zhì)，而且螞蟻在運動過程中能夠感知這種信息素物質(zhì)。因此，由大量螞蟻組成的蟻群行為便表現(xiàn)出一種信息正反饋和相互協(xié)作的機理：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大，即運用群體信息素來作為引導(dǎo)它們運動軌跡方向的依據(jù)，最后螞蟻能找到一條從蟻巢到食物源的最短路經(jīng)，這就是整個群體得以完成復(fù)雜優(yōu)化行為的實質(zhì)問題。即使遇到障礙物情況，該基本原理仍然是不變的，只不過是在運動的途徑上會增加沉積信息素的中間狀態(tài)點來解決，信息交換構(gòu)成一個正反饋過程仍是不變的。

1.2 K-medoids算法

K-medoids聚類算法[13]的基本策略是通過首先任意為每個聚類找到一個代表對象而首先確定n個數(shù)據(jù)對象的k個聚類；其他對象則根據(jù)它們與這些聚類代表的距離分別將它們歸屬到各相應(yīng)聚類中。而如果替換一個聚類代表能夠改善所獲聚類質(zhì)量的話，那么就可以用一個新對象替換舊聚類對象。這里將利用一個基于各對象與其聚類代表間距離的成本函數(shù)來對聚類質(zhì)量進(jìn)行評估。為了判定一個非代表對象Orandom是否是當(dāng)前一個代表對象Oj的好的替代，對于每一個非中心點對象p，下面的4種情況被考慮。

第一種：p當(dāng)前隸屬于中心點對象Oj。如果Oj被Orandom所代替作為中心點，且p離一個Oj最近，i≠j，那么p被中心分配給Oi。

第二種：p當(dāng)前隸屬于中心點對象Oj。如果Oj被Orandom代替作為一個中心點，且p離Orandom最近，那么p被重新分配給Orandom。

第三種：p當(dāng)前隸屬于中心點Oi，i≠j。如果Oj被Orandom代替作為一個中心點，而p仍然離Oj最近，那么對象的隸屬不發(fā)生變化。

第四種：p當(dāng)前隸屬于中心點Oi，i≠j。如果Oj被Orandom代替作為一個中心點，且p離Orandom最近，那么p被重新分配給Orandom。

每當(dāng)重新歸類時，平方誤差E所產(chǎn)生的差別對成本函數(shù)有影響。因此，如果一個當(dāng)前的中心點對象被非中心點對象所代替，成本函數(shù)計算平方-誤差值所產(chǎn)生的差別。替換的總成本是所有非中心點對象所產(chǎn)生的成本之和。如果總成本是負(fù)的，那么實際的平方誤差將會減小，Oj可以被Orandom替代。如果總成本是正的，則當(dāng)前的中心點Oj被認(rèn)為是可接受的，在本次迭代就無需變動。

2 蟻群優(yōu)化K-medoids綜合算法

2.1 基本思想

綜合算法的基本思想：從蟻群中隨機選取m個對象，計算任意兩個對象之間的距離，確定蟻群間的距離和最初的聚類中心，并將此中心作為蟻群的歷史最優(yōu)位置，使用K-medoids算法對歷史最優(yōu)位置進(jìn)行聚類分析，找到新的聚類中心，來代替蟻群算法逼近優(yōu)化的中心點。首先，螞蟻之間在利用螞蟻釋放的信息素，確定蟻群在可行解范圍內(nèi)的相對位置，實現(xiàn)螞蟻之間的信息交換；其次，根據(jù)螞蟻所在蟻群中心提供的信息素，擴大螞蟻的搜索空間，從而避免螞蟻陷入局部最優(yōu)，加強算法對聚類所在空間區(qū)域的局部搜索能力；最后，從整個蟻群的角度出發(fā)，由于每只螞蟻的搜索范圍都集中于新的聚類所形成的區(qū)域，重新計算任意螞蟻之間的距離，確定最終的聚類中心。

2.2 實現(xiàn)過程

1）流程圖（如圖1）

圖1 綜合算法流程圖

2）實現(xiàn)步驟

設(shè) X={Xi=(xi1，xi2，…，xim)，i=1，2，…，N}是待進(jìn)行聚類分析的數(shù)據(jù)樣本的集合。

Step1 對蟻群進(jìn)行初始化操作，選擇螞蟻數(shù)目為m，NC-max為最大迭代次數(shù)，m個螞蟻作為初始中心點，設(shè)初始中心點為（M1，M2，…，Mm）。

Step2 定義dij為Xi到Xj之間的加權(quán)歐氏距離

式中，P為權(quán)因子，可根據(jù)各分量在聚類中的貢獻(xiàn)不同而設(shè)定。

設(shè)r為聚類半徑，τ ij ( t)為t時刻數(shù)據(jù)樣本Xi到樣本Xj路徑上殘留的信息數(shù)量（Pheromone Quantity，PQ）PQ，設(shè) τ ij ( 0)=0，即在初始時刻各路徑上的PQ相等且為0。路徑ij上PQ由式（2）給出

而Xi是否歸并到Xj由式（3）給出

式中， p ij ( t)表示Xi歸并到Xj的概率，若 p ij( t)≥p0，（0≤p0≤1），則Xi歸并到Xj領(lǐng)域。其中，p0為一概率常數(shù)。S={Xs|dsj≤r，s=1，2，…，j，j+1，…，N}；η為局部的啟發(fā)函數(shù)，表示由數(shù)據(jù)樣本i轉(zhuǎn)移到數(shù)據(jù)樣本j的期望程度。α，β分別表示螞蟻在運動過程中所積累的信息素及啟發(fā)函數(shù)在樣本轉(zhuǎn)移路徑的過程中所起的不同作用。

根據(jù)加權(quán)歐氏距離式（1），計算每只螞蟻之間的距離dij，然后由式（3）計算 p ij( t)判斷PQ，確定蟻群間的最優(yōu)路徑和聚類中心，并將此中心作為蟻群的歷史最優(yōu)位置。

Step3 根據(jù)K-medoids算法對蟻群的歷史最優(yōu)位置進(jìn)行新的聚類分析。以ACO算法的歷史最優(yōu)位置作為K-medoids算法中的代表對象Oj，確定每只螞蟻所在的聚類以及類與類之間的中心點。

Step4 對形成的新蟻群按照Step2的方法，計算每只螞蟻代表的最優(yōu)解，更新蟻群的歷史最優(yōu)位置和全局最優(yōu)解。

Step5 重新計算任意螞蟻之間的加權(quán)歐氏距離dij，確定新的聚類中心，找到最優(yōu)路徑。

Step6 定義Dj為第j個聚類的偏離誤差，ε為聚類分析的總體誤差。

式中，cjk為第j個聚類中心的第k個分量。

判斷ε是否在規(guī)定范圍內(nèi)，如在規(guī)定范圍內(nèi)，聚類終止，否則轉(zhuǎn)向Step3繼續(xù)迭代。

Step7 達(dá)到終止條件，聚類結(jié)束，取得最優(yōu)聚類中心。

3 聚類實例

3.1 聚類數(shù)據(jù)

取文獻(xiàn)[14]中福建省電力調(diào)度通信中心EMS提供的2005年夏季的典型電網(wǎng)變電站負(fù)荷構(gòu)成數(shù)據(jù)進(jìn)行聚類分析。矩陣U為變電站負(fù)荷構(gòu)成參數(shù)，待分對象：U={u1，u2，u3，…，u44}為44個220kV變電站負(fù)荷構(gòu)成參數(shù)；列對象參數(shù)：ui={uil，ui2，ui3，ui4}為各變電站的工業(yè)、農(nóng)業(yè)、商業(yè)、城鄉(xiāng)居民及其他4類典型行業(yè)負(fù)荷的構(gòu)成比例。本文把變電站聚為4類。

3.2 聚類結(jié)果

如表1和表2所示，將綜合算法與單一的FCM的聚類結(jié)果進(jìn)行比較，以驗證其聚類的效果。同時列出兩種方法的聚類中心矩陣CFCM和C綜合。

表1 FCM法的聚類結(jié)果

聚類中心矩陣為

表2 綜合算法的聚類結(jié)果

聚類中心矩陣為

3.3 類間距離和類內(nèi)距離比較

聚類結(jié)果的好壞要看是否有較高的類內(nèi)相似性，較低的類間相似性。本文可以對它們的類間距離和類內(nèi)距離進(jìn)行比較，一般來講，聚類中心的間距越大，樣本與其所屬中心的間距越小，聚類效果更好。因此，我們只列出它們的類間距離和類內(nèi)距離進(jìn)行比較。

1）類間距離：由聚類中心矩陣可以求得類間距離矩陣，取矩陣中的每個元素的平均值作比較，較大者則認(rèn)為聚類效果比較好，反之亦然。如表3所示。

表3 類間平均距離比較

2）類內(nèi)距離：類內(nèi)平均距離比較如表4所示。

表4 類內(nèi)平均距離比較

3.4 結(jié)果分析

1）如表3和表4所示，綜合算法的類間距離有所變大，類內(nèi)距離有所變小，可知綜合算法在變電站的聚類中取得了較好的效果。

2）對聚類中心矩陣與變電站負(fù)荷構(gòu)成數(shù)據(jù)進(jìn)行比較，基于綜合算法的聚類結(jié)果是有效和合理的。例如第一類，工業(yè)用電約占55%，商業(yè)用電約占43%，農(nóng)業(yè)和城鄉(xiāng)居民及其他各約占1%，基本上反映了第一類各變電站的綜合靜態(tài)負(fù)荷特性構(gòu)成。聚類中心矩陣中可以較好地體現(xiàn)出每類變電站的綜合靜態(tài)負(fù)荷特性。

3）由聚類結(jié)果和中心矩陣可得出安裝負(fù)荷測辨裝置的變電站數(shù)量和具體位置，即負(fù)荷裝置布測點的個數(shù)為聚類數(shù)，理想的安裝測點是與聚類中心負(fù)荷構(gòu)成特性最為接近的典型變電站。

4 結(jié)論

負(fù)荷特性分類與綜合是實現(xiàn)負(fù)荷模型實用化的關(guān)鍵，為了建立合適的變電站負(fù)荷模型，本文將聚類方法引入到負(fù)荷特性分析，提出了基于蟻群優(yōu)化K-medoids綜合算法的電力負(fù)荷聚類。綜合算法是PAM算法對蟻群的歷史最優(yōu)位置進(jìn)行了聚類分析，ACO具有良好的正反饋性能、較強的魯棒性、易于與其他算法結(jié)合等特點，使綜合算法能更好地獲得全局最優(yōu)解，從而克服了PAM算法易陷入局部最優(yōu)的缺點，并降低了對初始值的敏感度，提高了聚類的準(zhǔn)確率。通過變電站特性聚類實例，將綜合算法與FCM法聚類結(jié)果進(jìn)行比較，證明了綜合算法在電力系統(tǒng)負(fù)荷聚類的優(yōu)越性。同時基于綜合算法的負(fù)荷聚類為沒有安裝布測點的變電站建立實用模型提供了有效途徑，因此，文中所得到的聚類結(jié)果和聚類中心矩陣為進(jìn)一步開展負(fù)荷建模實用化工作提供了重要的參考依據(jù)。

[1]李娟,丁堅勇.電力系統(tǒng)負(fù)荷建模和算法的研究及進(jìn)展[J].高電壓技術(shù),2008,34(10):2209-2215.

[2]李培強,李欣然,林舜江.電力負(fù)荷建模研究評述[J].電力系統(tǒng)及其自動化學(xué)報,2008,20(5):57-64.

[3]鞠平,謝會玲,陳謙.電力負(fù)荷建模的發(fā)展趨勢[J].電力系統(tǒng)自動化,2007,31(2):1-4.

[4]賀仁睦.電力系統(tǒng)精確仿真與負(fù)荷模型實用化[J].電力系統(tǒng)自動化,2004, 28(16):4-7.

[5]章健,沈峰,賀仁睦.電力負(fù)荷模型結(jié)構(gòu)的樣條函數(shù)描述[J].電力自動化設(shè)備,2007,27(7):5-8.

[6]黃梅,賀仁睦,楊少兵.模糊聚類在負(fù)荷實測建模中的應(yīng)用[J].電網(wǎng)技術(shù),2006,30(14):49-52.

[7]白雪峰, 蔣國棟.基于改進(jìn) K-means聚類算法的負(fù)荷建模及應(yīng)用[J].電力自動化設(shè)備,2010,30(7):80-83.

[8]李培強, 李欣然,陳輝華,等.基于模糊聚類的負(fù)電力負(fù)荷特性的分類與綜合[J].中國電機工程學(xué)報,2005, 25(24):73-78.

[9]楊浩,張磊,何潛,等.基于自適應(yīng)模糊C均值算法的電力負(fù)荷分類研究[J].電力系統(tǒng)保護(hù)與控制,2010,38(16): 111-115.

[10]張智晟,孫雅明,張世英,等.基于數(shù)據(jù)挖掘多層次細(xì)節(jié)分解的負(fù)荷序列聚類分析[J].電網(wǎng)技術(shù),2006,30(2):51-56.

[11]周申培,嚴(yán)新平.遺傳蟻群融合算法及在不確定性無功優(yōu)化中的應(yīng)用研究[J].電力系統(tǒng)保護(hù)與控制,2010,38(24):120-123.

[12]孫雅明,王晨力,張智晟,等.基于蟻群優(yōu)化算法的電力系統(tǒng)負(fù)荷序列的聚類分析[J].中國電機工程學(xué)報,2005,25(18):40-45.

[13]朱明.數(shù)據(jù)挖掘[M].合肥:中國科技大學(xué)出版社,2008.11.

[14]鞠平, 陳謙, 熊傳平,等.基于日負(fù)荷曲線的負(fù)荷分類和綜合建模[J].電力系統(tǒng)自動化, 2006, 30(16):6-9.